|
|
Give me a test or something... I am getting WA in 22nd case! I cant find my mistake. Can someone help me ? Try this: 20 1 00000000100000000001 Answer: 0 1 15 I couldn't understand why my program got WA in test 22. Can anyone give me some help. Thanks I have the same problem Even i have the same problem! Can someone tell me what the mistake might be ? 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 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 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 |
|
|