|
|
There can't be -1, because you can always choose path k->2k->3k->k Which algorithm?? Help I need help also. As i see you have solved it. Could you please help me? Does anyon know, what is the longest test? I check a couple of numbers,with k= 99998 execution was the longest, but i'm not sure. UPD: I check (write k=99998 instead a reading number), and if WA#1 said truth, i reach the answere in 0,71. But this decision is still have TLE#41 :( Maybe, there is a harder 'k' for this task? Edited by author 07.08.2018 11:17 Edited by author 07.08.2018 11:17 You can try to binary search the test case. Put somewhere in your program the following if (clock() >= 0.9 * CLOCK_PER_SEC) { assert(K <= BINARY_SEARCH_MIDDLE); } You need to include <cassert> and <ctime> for these to work. Now (double)clock() / CLOCK_PER_SEC gives you program execution time in seconds. clock() >= 0.9 * CLOCK_PER_SEC checks that your program runs more than 0.9 seconds, in other words, approaching TL of 1s. This 'if' allows to execute code that will probably work only on 41th test case. assert( boolean expression ); exits with non-zero value if condition is not met. You could also do if (K <= BINARY_SEARCH_MIDDLE) { exit(your favourite non-zero number); } So, you can start with assert(K <= 100000 / 2) and so on. If you program fails on 41th test with RE instead of TL you change the bin search value. I don't know what is the fastest way to solve this, but I think mine is more complicated than it can be. I've keeped a vector for each remainder i mod k and i*i mod k, to quickly find the numbers which give remainder r. Then you can add edge by edge in graph and use union-find algo to check for cycles. Maybe there is a faster math solution? Yep, graph is very sparse. Almost always (without several trivial cases) you can consider only range [0..2*k]. To avoid any kinds of checking simply get n = max(10, 2*k). For each number in [1..n] try to find cycle with previous ones. Use e.g. disjoint sets for simplicity. Note, that solution always exists! Almost always (without several trivial cases) you can consider only range [0..2*k]. To avoid any kinds of checking simply get n = max(10, 2*k). Is there any mathematical proof for this? if k=1 =>ans is 3 if k=2 =>ans is 5 if k>2 => you can take numbers 1, k-1, 2*k-1, and it will be a cycle I saw many guys got AC very fast,is there any way to work the problem out other than just find-cycle? Could anybody correct answers given by my Wa program: 1 3 2 5 3 5 4 7 5 7 6 8 7 10 8 12 9 13 10 13 11 14 12 15 13 17 14 19 15 20 16 23 17 21 18 22 19 15 20 24 21 26 22 18 23 30 24 32 25 32 26 31 27 23 28 33 29 13 30 35 31 37 32 39 33 29 34 42 35 43 36 44 37 43 38 44 39 45 40 46 41 47 42 48 43 34 44 39 45 54 46 56 47 58 48 48 49 27 50 57 Here are the correct answers: 1 3 2 5 3 5 4 7 5 6 6 8 7 10 8 12 9 11 10 11 11 8 12 15 13 14 14 17 15 20 16 23 17 18 18 20 19 15 20 24 21 24 22 18 23 21 24 32 25 19 26 27 27 23 28 31 29 13 30 35 31 22 32 39 33 29 34 35 35 40 36 44 37 30 38 33 39 42 40 44 41 31 42 45 43 32 44 39 45 50 46 43 47 44 48 60 49 27 50 39 Thank! Debugging in range[1..50] was enough for AC. Edit: Nevermind Edited by author 03.12.2009 01:15 Edited by author 03.12.2009 01:15 Does anyone know what is test 12? Subj I've been thinking on this problem for several days,but I still can't find such algorithm( Edited by author 05.03.2009 19:59 Just emulate the professor's operations using some precalculation... I think my program works well,but I get wa on 31#,could you help me? my algorithm is that: if a conect to b,and b conect to c,so a%n==c%n; that means c=a+n;and the first cycle will happen at max(b+n,a+n); if a conect to a+n, ans the first cycle will happen at a+2*n; so there is no way to output -1, Am i right? I can't even past the 3th testcase. I had WA 31 too. You have to check where you use square of variables to except overflow. Edited by author 01.03.2009 20:02 Thanks,And I have got accept now. I get wrong answer because I used longint while I use square of variables. I have an O(n) algrithm,but I wonder if there is a math algrithm. Edited by author 02.03.2009 15:11 |
|
|