Think about O(N) solution, task much easier than is looks like. I use queue and got AC despite my solution probably has O(N * queue_work_complexity), not clearly O(N) Any hints for solution? I am completely stuck at TLE. On 21 th test N=100000 R=0 Edited by author 24.08.2012 18:03 I write algorithm on o(n), but wa# 15.... I can`t find out the reason who can give me some hint ? thanks Edited by author 22.12.2008 05:23 try this test 6 2 1 3 4 5 6 7 it should be 3 trips. i have write NlogN algo - TLE 21 then i rewrite it in N*sqrt(N) - TLE 21 maybe something wrong with this test? Strange.... My solution which got AC in contest gets TLE 21 too. Besides my solution is O(n log k) Where k is number of "run" in the market. The correct solution is O(N). Try to find it. ln N is just 17 Less then 2 million iterations. O(n lg n) also should pass TLE. Why my O(n lg n) solution passed during contest? Edited by author 16.10.2007 03:39 maybe you are right and there is O(n) solution but my NlogN and NsqrtN should pass any test with n <= 100000 so i think this file is empty and i got TL when read as scanf("%d", &n); Edited by author 14.10.2007 11:29 when i use vector<vector<int>> it was TL but if use vector<myvector>> i got Ac 0.203 it is strange... At the contest I was a bit lucky to make a solution O(n*m) where m is the number of groups and it passed... My first solution was n*log(n ) but it was TL :( This problem can be solved using 1 array of integers and a few variables in O(n) time (one "for" loop, actually). Try to find it, it is more interesting than optimizing your obvious N*logN solutions. I understand you, there is an O(N) solution. but i cant see it can we talk about in ICQ (my icq is 410673122) I have an O(n) solution but it works about 0.5 sec... Why? Don't forget, that reading about 1MB of input also requires a lot of CPU time. Now so fast, but AC with O(NlgN). Just used myvector as inner container and some optimization on function calls. Really strange.. O(4N) is possible I have Accepted for my solution, complexity O(n * log(n)) written in Java without any optimization with time 1.5 sec. Mates! I finded O(N) solutions in my 16 years! So use your brain and find it too! P.S. 0.093 sec, but 2 592 КБ memory... Edited by author 22.10.2007 02:55 Maybe you mean solution using unintersectable sets? It's really fast and you don't have to use additional memory. My solution O(N) took 0.421 and 7 969 КБ because I used dinamic structures with pointers to next nodes. :) N*log(N) - 0.187 sec. Did not optimize anything, but stored amount for same-size coats. O(N) - AC in 0.109 sec O(N*logN) AC 0.234 Brilliant problem! Solved in O(N) with 3 lines of creating chains and bit more lines for printing results. Fist tried to solve it as 1533 (Fat Hobbits), but it is much easier Why WA 15? Help me please. import java.util.Arrays; import java.util.Scanner; public class Timus1579 { public static void main(String[] args){ Scanner in = new Scanner(System.in); int n=in.nextInt(),r=in.nextInt(); Shub[] a=new Shub[n]; Xod[] x=new Xod[n]; int ix=1,im=0,gt=0; a[0]=new Shub(in.nextInt(),0); x[0]=new Xod(a[0].size); for(int i=1; i<n; i++){ a[i]=new Shub(in.nextInt(),i); if(x[im].size+r<a[i].size){ x[im].size=a[i].size; x[im].amount++; a[i].num=im; im=(im+1)%ix; }else{ a[i].num=ix; x[ix]=new Xod(a[i].size); ix++; } } System.out.println(ix); Arrays.sort(a); for(int i=0; i<ix; i++){ System.out.print(x[i].amount+" "); while((gt<n)&& (a[gt].num==i)){ System.out.print((a[gt].num2+1)+" "); gt++; } System.out.println(); } } } class Shub implements Comparable{ int num,num2,size; public Shub(int s, int n) { num=0; size=s; num2=n; } public int compareTo(Object o) { Shub a=(Shub)o; if(num==a.num){ return num2-a.num2; }else return num-a.num; } } class Xod{ int size,amount; public Xod(int i) { size=i; amount=1; } } just check your program on these tests ---------- 4 3 1 5 8 10 answer: 1 8 5 10 wrong answer: 1 5 8 10 ---------- 4 2 3 5 7 10 answer: 5 10 3 7 wrong answer: 7 10 5 3 That's helped me with wa#9: 9 0 1 1 6 6 23 35 36 38 40 Right answer has 2 trips. O(N*logN) AC 0.234 hint: lower_bound STL What's the test 15?Can somebody tell me? Thank you. Here is my code with O(N) soulution which is get WA on #15 program coats; const maxn=200100; var g,next,t:array [0..maxn] of int64; l,a:array [0..maxn] of int64; i,k,m,n:longint; r:int64; procedure init; begin read(n,r); for i:=1 to n do read(a[i]); end; procedure solve; begin m:=1;k:=1; next[n]:=g[1];g[1]:=n;l[1]:=a[n];t[1]:=1; for i:=n-1 downto 1 do begin if l[k]-a[i]>r then begin next[i]:=g[k];g[k]:=i;l[k]:=a[i];inc(t[k]); inc(k);if k>m then k:=1; continue; end; inc(m);next[i]:=g[m];g[m]:=i;l[m]:=a[i];t[m]:=1; end; writeln(m); for i:=m downto 1 do begin write(t[i]); r:=g[i]; while r<>0 do begin write(' ',r); r:=next[r]; end; writeln; end; end; begin assign(input,'coats.in');reset(input); assign(output,'coats.out');rewrite(output); init; solve; close(input);close(output); end. Please help! Nothing serious.Just a big and hidden mistake in my program. Thank you anyway. In russian: "должен превосходить размер меньшей более, чем на величину R". May be "должен превосходить размер меньшей не менее, чем на величину R"? In english the same statement. No, the statement is correct. For example, for test 2 5 1 6 the coat of size 6 can't be put on over the coat of size 1, so the minimal number of trips is 2 Thank you, this is my error #include <fstream> #include <stdio.h> #include <vector> using namespace std; int n, r, num = 0, g; int arr[100100] = {0}; vector <int> v[100100]; bool can[100100] = {0}; int pr[100100] = {0}; int pr_val[100100] = {0}; int nm[100100] = {0}; int fset (int x) { int i; /*for (i = x; i > 0; --i) { if (!can[i]) { return i; } } return 0;*/ if (!can[x]) { return x; } int t = pr[x]; pr[x] = fset (t); return pr[x]; ++g; } int main () { //freopen ("a.in", "r", stdin); //freopen ("a.out", "w", stdout); int i, j = 0, t; scanf ("%d%d", &n, &r); arr[0] = -110000000; for (i = 1; i <= n; ++i) { scanf ("%d", &arr[i]); while (arr[i]-arr[j] > r) { ++j; } --j; pr[i] = i-1; pr_val[i] = j; } for (i = 1; i <= n; ++i) { j = pr_val[i]; g = 0; t = fset (j); if (t == 0) { num++; v[num].push_back (i); nm[i] = num; } else { can[t] = true; v[nm[t]].push_back (i); nm[i] = nm[t]; } } printf ("%d\n", num); int col = 0; for (i = 1; i <= num; ++i) { printf ("%d ", v[i].size()); for (j = 0; j < v[i].size()-1; ++j) { printf ("%d ", v[i][j]); ++col; if (v[i][j]+r >= v[i][j+1]) { int q = 1; q = q/(1-q); } } printf ("%d\n", v[i][v[i].size()-1]); ++col; } if (col != n) { int q = 1; q = q/(1-q); } return 0; } Edited by author 18.10.2007 02:24 I had WA 22 using 'long' type. When I used 'long long' I got AC. Denis, It is siple!!!!! Change string arr[0] = -110000000; on arr[0] = -1100000000; and be happy=) My program give answer on test in sample: 3 4 1 4 6 8 3 2 5 7 1 3 But i have wa #1 It's wrong? 4 1 4 6 8 Last two numbers gives us: 13-10 = 3 The differece between sizes is 3, R is also 3. However: "A larger coat can be put on over a smaller one if the size of the larger coat exceeds the size of the smaller coat by more than R." So diffrence must be at least 4. I found my mistake... But its not enough... Edited by author 18.10.2007 01:20 Edited by author 18.10.2007 01:20 Can we consided the problem as optimal sheduling task raplacing a value ak with interval [ak.ak+R) and applying greedy algotithm. Yes! Dilworth applying. Having confirmed by Dilworth optimal number M it is simply to find O(n) of right dividing: 1,2,3,1,2,3,1,2,3.. if M==3. My O(n) 0.125Ac one of the best, but respect to them who have 0.03 because they can build quick implementation of simple processes. Edited by author 17.10.2007 14:38 Edited by author 18.10.2007 10:36 Edited by author 18.10.2007 10:36 Edited by author 18.10.2007 11:03 Why I WA TEST 13 !! I write an O(N) program but why I wa test 13?? |
|