|
|
вернуться в форумIn fact many of you got AC with O(N1*N2) solution. Some new tests were added and some more will be added soon. This problem had very simple O(N) and O(N*log N) solutions but unfortunately very weak tests. 756 authors had already lost their AC. Extra tests were added and Time Limit was decreased to 1 second. Because of limitations [-32768, 32767] some O(N^2) solutions still have AC, but these limitations will not be changed. Investigation is finished. :) Are the limits the same? I have O(n1+n2) and TLE#8 Is it too slow?! Your algo is correct. Sorry for wrong verdict. This was a system bug. I use binary search. But I have WE on test 5. What's problem? Solution complexity is O(n+m). On 3rd test my program get time 0.14 but system says "Time limit exceeded".. Is this a bug? I try pass problem again, and got AC... Edited by author 26.03.2007 23:29 My solution got AC by tnow it TL on 4 test Thise code for those who can answer to my problem var a:array[1..50001]of integer; n,i,j,k,m:longint; begin read(n); for i:=1 to n do read(a[i]); read(m); for i:=1 to m do begin read(k); for j:=1 to n do if (a[j]+k=10000) then begin write('YES'); halt(0); end; end; write('NO'); end. Your solution complexity is O(N*M), which is too slow. Try to find a better algorithm. Good luck! i got one with O(nlogn) but what the O(n) one ? you mean that we use hash to search ? Just use array of bool using a bool array of length 65000 will solve it very very fast.//idea of bucket sort Edited by author 13.06.2008 02:08 here is my code and i've time limit test 10. begin read(n); for i := 1 to n do read(a[i]); q := false; read(m); q1 := true; read(x); if x+a[n]<10000 then q1 := false else begin i := n; repeat if x+a[i]=10000 then q := true; i := i - 1; until (i=0) or (x+a[i]<10000); end; if q1 then begin for j := 1 to m-1 do begin read(x); i := n; repeat if x+a[i]=10000 then q := true; i := i - 1; until (i=0) or (x+a[i]<10000); end; end else for j := 1 to m-1 do read(x); if q then write('YES') else write('NO'); end. who can give me more correct than mine, pls!! your solution is too slow there is O(n + m) solution for example 4 5 7 10 15 5 [and some numbers] at first you can read first group of 4 numbers (5, 7, 10,15) and while you read second group you can easy check is it 9995, 9993, 9990, 9985 or not after reading next integer from second group you dont need to check all 4 numbers. you can do it fast just using array of boolean thanks!!, but I find new algo begin read(n); for i := 1 to n do read(a[i]); q := false; j := 0; read(m); repeat inc(j); read(x); i1 := 1; ni := n; if (a[i1]+x<=10000) and (a[ni]+x>=10000) then begin i := 0; repeat inc(i); if a[ni div 2]+x<=10000 then i1 := ni div 2 else ni := ni div 2; until (i=10) or (ni-i1<=3); for i := i1 to ni do if a[i]+x=10000 then q := true; end; until (q) or (a[n]<=10000) or (j=m); if q then write('YES') else write('NO'); end. but i've WA#3 now!! |
|
|