| ENG RUS | Timus Online Judge |
Discussion of Problem 1867. NanotechnologiesVavan WA 4, WA 5, WA 35 [14] // Problem 1867. Nanotechnologies 18 Oct 2011 01:23 test 4 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 test 5 5 0 2 2 2 2 2 0 4 8 4 2 4 0 4 8 2 8 4 0 4 2 4 8 4 0 What is in test #35????? ;) Edited by author 18.10.2011 01:30 svr Re: WA 4, WA 5, WA 35 [12] // Problem 1867. Nanotechnologies 18 Oct 2011 09:48 It was enough 5 tests for me. In first algo I used double and couldn't fly over test 5. Based on my fail on 5 test I remade algo radically, excluded doubles and got Ac 0.078. So, 5 tests are enough for debugging. Vavan Re: WA 4, WA 5, WA 35 [11] // Problem 1867. Nanotechnologies 19 Oct 2011 00:01 Did you use __int64 or long arithmetic??? 4 0 550934784 999950884 449016100 550934784 0 449016100 999950884 999950884 449016100 0 550934784 449016100 999950884 550934784 0 Edited by author 19.10.2011 01:00 svr Re: WA 4, WA 5, WA 35 // Problem 1867. Nanotechnologies 19 Oct 2011 02:07 If d=a^2+b^2 and d<=10^9=> a,b<=32000 that short int is enough. Also brute force(main clue for integers) for solving triangle in int coordinates. IgorKoval(from Pskov) Re: WA 4, WA 5, WA 35 // Problem 1867. Nanotechnologies 21 Oct 2011 00:41 4 0 550934784 999950884 449016100 550934784 0 449016100 999950884 999950884 449016100 0 550934784 449016100 999950884 550934784 0 0 0 0 23472 -21190 23472 -21190 0 Edited by author 21.10.2011 00:44 morbidel Re: WA 4, WA 5, WA 35 [8] // Problem 1867. Nanotechnologies 21 Oct 2011 17:02 @Vavan: What did you do between WA8 and WA35? Thanks. Edited by author 21.10.2011 19:56 molphys fti UFU Re: WA 4, WA 5, WA 35 [7] // Problem 1867. Nanotechnologies 21 Oct 2011 18:25 if you have WA8, it will very likely caused by an invalid enumeration on brute force of triangle in whole numbers. for x**2+y**2 x = 0, y = floor(sqrt(D)) downto floor(sqrt(D / 2)) you should firstly to increase x, rather than y. morbidel Re: WA 4, WA 5, WA 35 [6] // Problem 1867. Nanotechnologies 21 Oct 2011 20:15 I'm not sure I understand what you mean. Currently I enumerate the pairs (i, j) with for (i = 0; i * i <= n; i++) { j = (int) sqrtl(n - i * i); if (i <= j && j * j + i * i == n) { ... valid (i, j) pair... } } molphys fti UFU Re: WA 4, WA 5, WA 35 [5] // Problem 1867. Nanotechnologies 21 Oct 2011 23:36 it shuld be faster signed x = 0; signed M = SQRT(D / 2); for (signed y = SQRT(D); y >= M; y--) { unsigned Y = y * y; while (x * x + Y < D) { x++; } if (x * x + Y == D) { // valid (x, y) } } Edited by author 21.10.2011 23:43 morbidel Re: WA 4, WA 5, WA 35 [4] // Problem 1867. Nanotechnologies 24 Oct 2011 19:49 Well I also do a loop from 1 to sqrt() but without the while so I don't think that's faster. Anyway not the speed is the problem. I put a while(1); if some point exceeds 10^6 and if a D[i][j] value is incorrect so that a TLE should occur in these cases. I made a generator of tests and all looks OK. But WA #8... Any suggestions, tricky tests? Thanks Edited by author 24.10.2011 19:57 morbidel Re: WA 4, WA 5, WA 35 [3] // Problem 1867. Nanotechnologies 24 Oct 2011 23:28 I found my mistake. I was computing the first 3 points then thought the rest of them are uniquely determined. But this is false, for example if the first N-2 points are collinear, than the N-1 one could be, by symmetry, on two locations. By ignoring one of those solutions for N-1, the N-th point may not be determined and assume the current input is impossible to solve. Now I did a sort of backtracking with all solutions for each point but obviously got TLE 39. So work in progress :) PS: I've read in some other topic about writing the sqrt in assembly but I don't think that's the way of solving this problem :) Edited by author 24.10.2011 23:30 morbidel Re: WA 4, WA 5, WA 35 [2] // Problem 1867. Nanotechnologies 27 Oct 2011 21:01 AC, woo-hoo! Indeed, if the points 0..i-1 are fixed and collinear, the solution for the rest of the points is not unique because we have an axis of symmetry. Otherwise, if at least 3 points are non-collinear, the solution is unique. Edited by author 27.10.2011 21:09 aropan Re: WA 4, WA 5, WA 35 [1] // Problem 1867. Nanotechnologies 31 Oct 2011 10:23 I got wa32 and fixed to the test: 5 0 4 36 5 2 4 0 16 5 2 36 16 0 29 26 5 5 29 0 9 2 2 26 9 0 0 0 0 2 0 6 2 1 -1 1 and more: 5 0 4 25 16 100 4 0 9 36 64 25 9 0 81 25 16 36 81 0 196 100 64 25 196 0 0 0 0 2 0 5 0 -4 0 10 Orient Re: WA 4, WA 5, WA 35 // Problem 1867. Nanotechnologies 4 Jul 2014 22:09 Edited by author 01.05.2016 01:52 IgorKoval(from Pskov) Re: WA 4, WA 5, WA 35 // Problem 1867. Nanotechnologies 21 Oct 2011 00:43 test 4 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 test 5 5 0 2 2 2 2 2 0 4 8 4 2 4 0 4 8 2 8 4 0 4 2 4 8 4 0 answers: test 4 0 0 0 0 0 0 0 0 0 0 test 5 0 0 1 1 -1 1 -1 -1 1 -1 Edited by author 21.10.2011 00:44 198808xc TLE at 39 // Problem 1867. Nanotechnologies 26 Aug 2012 21:07 I got AC with a bruteforce (Depth First Search) algorithm in 0.218 sec. If you get TLE at test 39, it is something like this: N = 100 The element of A is all 0, except for a(99, 100) = a(100, 99) = 1. molphys fti UFU No subject [1] // Problem 1867. Nanotechnologies 21 Oct 2011 23:40 Edited by author 04.07.2014 21:32 molphys fti UFU No subject // Problem 1867. Nanotechnologies 22 Oct 2011 00:53 Edited by author 04.07.2014 21:32
|