If you got problems with WA 20 (new test), just know - it is because of precision issue. Not use double or long double - only long integer arithmetic or integer modular arithmetic. P.S. authors of new tests - it is not good to add tests to the OLD task after 23 years of time passed. It is so strange. Why authors of solutions must return to the OLD task and resolve it again??????? Thanks LLI! By the way, I used integer modular arithmetic in the first place, and still got WA 20 after rejudge. After some debugging I realize I checked the linear independency incorrectly (in particular, I did the row echelon form wrongly). Here is the test case helped me find out the bug: Input: 5 4 1 2 3 4 2 4 5 9 3 6 7 1 1 1 1 9 3 2 1 9 1 2 3 4 5 Expected output: 10 1 2 3 4 New tests were added. All accepted solutions were rejudged, ~60% of them lost their Accepted status. When will new contests be added as well? If you got problems with WA 20 (new test), just know - it is because of precision issue. Not use double or long double - only long integer arithmetic or integer modular arithmetic. I get access violation with Test#3 failing ? I can't recreate it with sample input given in problem. Can someone help me with this. Thanks Edited by author 01.09.2012 15:01 Edited by author 01.09.2012 15:01 Consider a failing scenario which is like 3 2 1 0 0 0 1 0 1 1 0 1 2 3 I got AC with incorrect checker of linear independence. Please, add this test: 6 3 6 0 0 3 0 0 0 5 0 0 2 0 0 0 4 0 0 1 6 5 4 3 2 1 Lukyanov Alexandr [Yaroslavl SU] WA4 [3] // Problem 1041. Nikifor 6 Aug 2007 19:50 Who can take test me? i use sort(price, position)+gaus. try test: 11 10 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Out: 10 1 2 3 4 5 6 7 8 9 10 Edited by author 17.07.2010 23:05 Is it has this tase case? It's pretty hard to solve T_T test: 3 2 0 1 2 0 1 0 10 10 10 answer: 20 1 2 lexicographic means input order, not coordinates. I was beaten by newtesrmakers having gauss solution in __int64- overflow. Rewrited the same program in my long arithm. 300- digits- MLE 200-digits-not enough. 270- digits- AC. Some new tests and the problem will become unsolvable. You can use gauss over prime modular ring instead of long arithmetics Just select lucky module =) Thanks Godz my ID at Valladolid is prime! :D Great idea) I used ortogonalization over prime module) Thanks. I do calculations on a ring of integers modulo (big prime). If i change the prime number sometimes i get WA on test 9. Any suggestions? ..... Got AC. Edit: Found a silly mistake. I thought is about the prime, but it wasn't. Edited by author 08.04.2011 06:41 I use Gauss But wa at #9 i tried to mod a bigprime but it doesn't work Help! and i want someone AC's code Please caocao9926@163.com Thanks You can use Gram-Schmidt process for checking linear independency and try 1999. May be anybody knows, what is specific of the second test? All my examples work correctly, but the second test...... }:-/ I've solved this problem and got WA after rejudge. And I have one question: does the word "lexicographic" mean it's usual meaning for sets (e.g. set A lexicographically smaller than set B if there exists some i that i-th element is in A, but no in B, and for all j < i j-th element is both in A and B). Or it means something else? Yes, "lexicographic" has its usual meaning. in 12 3 .... 12 linearly independent vectors 1 1 ... 1 1 out 3 1 10 11 Yes? Firstly, there are no linearly independent vectors 12 in three-dimensinal. :-) Secondly, I think right answer is 3 1 2 3 many people get WA at #9 Could anybody give me #9 testcase or give me an AC program caocao9926@163.com I use Gauss Maybe I get wrong because of eps I've passed it at Pku ,but I can't AC here. Thanks The trouble really can be in preсision. If you use simple Gauss with type "long double" you'll always get WA. Do calculations in long integer numbers or modulo big prime number. If you want, i can send you some my solutions, WA 9, WA 17, AC. Yeah I want your program Please : caocao9926@163.com I've tried to module big prime but it doesn't work and how to do calculations in long integer? Thanks Edited by author 05.10.2008 09:45 I got WA on test 3 ! Some one can send me a testdata. thx! Email:31898890@qq.com Output 0 if number of vectors purchased is <n Hi all. I tried to solve this problem many years ago and now returned to it with new knowledge and forces. Then i used pascal and now use Java. For others, who would try to solve this problem in java i has two hints. 1) Do not use long. Use int instead - or you get TL9. Prime number about 5-6k is ok since 6000^2*50<MAX_INTEGER 2) It is very strange, but creators of tests thought that it is smart enough to give you a 0-vector in 10-th test. It is totally incorrect to do so,... But it is proved that you can throw this vector away. ... Oh - one, more hint - 6000 is small enough to precalculate all reverse values and put them to source - about 40kb. Good luck. Questions to kluchnikovs on mail server mail.ru Edited by author 22.07.2008 00:50 You've described very scary way of solving this problem (with 0-vectors and reverse values) =) All you need to do in this problem is Gaussian elimination. Well-realized by some large modulo, it'll give you right answers with high probability and without any precalculations and 0-vectors checkings (by the way, I don't understand why giving 0-vectors is incorrect if not forbidden by the problem statement?) Indeed I used Gaussian elimination but with small modulo. But on first phase of solution, when i need to gather some basis I used "half-Gaussian" which considered permutation matrix -> so when I was looking for first non-zero vector element I got OutOfBoundsException. Reverse precalculation I used to reduce chances of second TLE (Java is times slow than c++/pascal). By the way. I've did some more thoughts experiments and found that my solution is incorrect, but tests are too weak to find that. For example for input: 6 3 6 0 0 3 0 0 0 5 0 0 2 0 0 0 4 0 0 1 6 5 4 3 2 1 My solution responds: 11 1 3 6 It is all because I throw away "bad" vectors on first stage which could get be in use in right solution. I suspect it can be not only in my solution, so TESTS MUST BE STRENGTHENED! Edited by author 22.07.2008 14:37 Edited by author 22.07.2008 14:37 Just a moment ago had rewritten my algo - now it doesn't use gaussian elimination at all, only Sherman-Morrison formula. So it need no permutation matrix, etc =) Well, there are many people who had problem with this case... i use duoble's in c++, for my gaussian elimination, and i tried many EPS but i still get WA... Something strange, is that i got AC in PKU OJ. And i suppose its because there few difficult cases there. I would like hear if someone can give me some hint, recommendation. I think it may be useless to use long long, because a hard case can overflow it. And anyway, some people seems to have gotten it AC with real's. Thanks, Eric. Edited by author 14.04.2008 07:43 Well you can use a kind of gaussian elimination mod P with a prime P not very big ( to avoid TLE ). Thanks to Minilek. gl! Eric. Edited by author 14.04.2008 23:52 I use Greedy Algo. My Email: panyong0202@yahoo.com.cn My mail: ttxxli@163.com program ex; const maxn=2000; maxm=50; zero=1e-15; var g: Array[0..maxn, 1..maxm] of extended; cost: Array[1..maxn] of longint; from: Array[1..maxn] of longint; n, m: longint; ans: longint; num: Array[1..maxm] of longint; tot: longint; kk: Array[1..maxn] of longint; procedure init; var i, j: longint; begin read(n, m); for i:=1 to n do for j:=1 to m do read(g[i, j]); for i:=1 to n do begin read(cost[i]); from[i]:=i; end; end; procedure qsort(l, r: longint); var i, j: longint; x, y: longint; t: longint; begin i:=l; j:=r; x:=cost[(l+r) shr 1]; y:=from[(l+r) shr 1]; while i<=j do begin while (cost[i]<x)or(cost[i]=x)and(from[i]<y) do inc(i); while (cost[j]>x)or(cost[j]=x)and(from[j]>y) do dec(j); if i<=j then begin g[0]:=g[i]; g[i]:=g[j]; g[j]:=g[0]; t:=cost[i]; cost[i]:=cost[j]; cost[j]:=t; t:=from[i]; from[i]:=from[j]; from[j]:=t; inc(i); dec(j); end; end; if j>l then qsort(l, j); if i<r then qsort(i, t); end; function can(x: longint): boolean; var i, j: longint; len1, len2: extended; sum: extended; co: extended; tt: extended; temp: Array[1..maxn] of extended; begin for i:=1 to tot do begin sum:=0; len1:=0; len2:=0; for j:=1 to m do begin sum:=sum+g[x, j]*g[i, j]; len1:=len1+g[x, j]*g[x, j]; len2:=len2+g[kk[i], j]*g[kk[i], j]; end; len1:=sqrt(len1); len2:=sqrt(len2); if abs(len1)<=zero then exit(false); co:=sum/len1/len2; tt:=len1*co; for j:=1 to m do temp[j]:=g[kk[i], j]*tt/len2; for j:=1 to m do g[x, j]:=g[x, j]-temp[j]; end; for j:=1 to m do if abs(g[x, j])>zero then exit(true); exit(false); end; procedure solve; var i: longint; begin qsort(1, n); tot:=1; num[1]:=from[1]; ans:=ans+cost[1]; kk[1]:=1; for i:=2 to n do if can(i) then begin inc(tot); kk[tot]:=i; num[tot]:=from[i]; ans:=ans+cost[i]; if tot=m then exit; end; end; procedure print; var i, j: longint; t: longint; begin if tot<m then writeln(0) else begin writeln(ans); for i:=1 to m do for j:=i+1 to m do if num[i]>num[j] then begin t:=num[i]; num[i]:=num[j]; num[j]:=t; end; for i:=1 to m do writeln(num[i]); end; end; begin init; solve; print; end. for (int z = i+1; z < n; z++) { __int64 r = (((__int64)a[j][z])*a[d][i] - ((__int64)a[j][i])*a[d][z]); a[j][z] = mod(r); } a[j][i] = 0; for (int z = i; z < n; z++) { __int64 r = (((__int64)a[j][z])*a[d][i] - ((__int64)a[j][i])*a[d][z]); a[j][z] = mod(r); } first get AC, but second WA9 by the way, mod(0) == 0 const int P = (1<<30)-17; int mod(__int64 x) { int r = x % P; if (r < 0) r += P; return r; } Edited by author 05.05.2007 18:49 n = 2 i = d = 0 j = 1 a: 1 1 1 1 First result: 1 1 0 0 Second result: 1 1 0 1 Who have the test case? MAIL ME: sunzheng.david@163.com I've got AC. The tests are very difficult. REMEMBER: The epsilon should be very small!!! I made eps=1e-10 and got ACed |
|