|
|
Show all threads Hide all threads Show all messages Hide all messages | WA #12 | anisca22 | 1611. Decimation | 22 Feb 2017 23:51 | 1 | WA #12 anisca22 22 Feb 2017 23:51 Give me a test or something... | WA #22 | TR Sriram | 1611. Decimation | 16 Dec 2016 18:58 | 2 | WA #22 TR Sriram 8 Sep 2015 20:27 I am getting WA in 22nd case! I cant find my mistake. Can someone help me ? Re: WA #22 Tolstobrov Anatoliy[Ivanovo SPU] 16 Dec 2016 18:58 Try this: 20 1 00000000100000000001 Answer: 0 1 15 | WA #22 | Try_to_try | 1611. Decimation | 8 Sep 2015 20:26 | 3 | WA #22 Try_to_try 30 Oct 2011 15:59 I couldn't understand why my program got WA in test 22. Can anyone give me some help. Thanks Even i have the same problem! Can someone tell me what the mistake might be ? | Need Help | Destyon | 1611. Decimation | 26 Sep 2012 16:12 | 5 | Give me some test please i have WA13 Try: 90 6 111110111110111110111110111110111110111110111110111110111110111110111110111110111110111110 One of correct answers is: 5 6 78 79 86 87 88 89 | Recursion | marat | 1611. Decimation | 26 Apr 2011 15:12 | 1 | It's not difficult to prove that if you optimally solved the problem with n conductors, n-1 conductors should be solved optimally too. Let a(n,k) be minimal total number of fined fare dodgers and good conductors. Then a(n,k) = MIN i FROM 0 TO k OF { a(n-1,i) + (n+k-[n is not a good conductor])/10 - (n-1+i)/10 } Details: Given k friends we should divide them into two parts. The first part should go and safe n-1 conductors and the second should stay between n-1 and n conductors. All we have to do is to count amount of fined friends in the second part + a(n-1,the first part) + whether n-th conductors is fined(1 or 0). [logical expression A] = 1, if A is true 0, otherwise What concerns test try these ones: ------------------------ 10 2 1110001011 possible answer: 0 2 2 1 ------------------------ 10 3 0001111111 possible answer: 1 0 ------------------------ 10 0 0001110001 possible answer: 1 0 ------------------------ 20 5 11111001110001110001 possible answer: 0 3 3 2 1 | What is complexity of your algo? | Vedernikoff Sergey | 1611. Decimation | 21 Oct 2010 23:18 | 5 | During the OpenCup I've accepted the problem with complexity O(N*K^2), but here, on timus, only optimizations helped me to beat timelimit with this algo. At the same time, some people have AC-times 0.015 or something like that. Is it possible to solve the problem with more efficient algo? O(N*K) my implementation is not so fast because of recursion O(N*K). Are you sure it's still O(N*K) with recursion? I could adopt only O(N*K*10) in DP I got confused. My program is very short and the complexity is O(N*K). I didn't find anything hard when solving this. I think you must have made it harder in thought. BTW, not O(N*K*M), but O(N*K). M is the modulo(10 here). Edited by author 21.10.2010 23:19 Edited by author 21.10.2010 23:19 | Also WA13. What to do? Some tricky tests? (-) | AlMag | 1611. Decimation | 28 Aug 2008 11:51 | 1 | |
|
|
|