|
|
you can easily find the solution with O(nk^3) but it will give u tle after optimization with cumulative sum array it will be O(nk^2) What is in test 4? I have WA and I dont know what is wrong. Personally I had problem with modular arythmerics Could you please provide more tests. I have WA#2 No idea why! although all the tests in the other discussions succeeded including the original test case Answer for #2 is P. So have to be carefull not to print ( sol + 1 ) % P. You have to print just sol + 1 because months are numbered from 1 to P. Tests: 20 30 1000 ans: 177 41 56 23 ans: 12 10 5 1000 ans: 185 Can this solve with complexity lower than O(N*k^2)? Could somebody give me any additional test cases? For example, 4 3 1000000 5 6 1000000 3 3 20 = 7 is covered in the problem itself, but here are two more: n k p result 1 1 30 2 1 2 12 3 Edited by author 13.04.2011 22:35 Thanks, 1 1 30 helped a lot :) Some additional tests: 4 3 1000000 73 5 6 1000000 4369 1000 200 777 141 Can somebody explain why 7 is the result of the given test? What is wrong with the following list of tuples: 1. 1 1 1 2. 1 1 2 3. 1 1 3 4. 1 2 1 5. 1 3 1 6. 2 1 1 7. 3 3 3 In this list of tuples, there is no tuple where all 3 elements have the same salary as before Edited by author 18.04.2011 09:13 I think you're missing a few, for example: 2 2 2 1 3 2 etc. The robot can't pay with rank1<rank2<rank3 & payment1>payment2>payment3 but he can do it if rank1<rank2<rank3 & payment1<payment2>payment3. Basically, for the 7 3 example you can do all permutations with repetition except for 3 2 1 so its 2 to the power of 3 minus 1. I can see why 3 2 1 is not allowed (constraint rank1<rank2<rank3 & payment1>payment2>payment3) and that is fine. But why 2^3? You have 3 options for salary for each of 3 robots, I would say it is 3^3 - 1? Yes, the count of allowed configurations of salaries is 26. So the accountant-robot will rust in 27th month, i.e. in 7th month of the year. That's why the answer is 7. thanks! Pardon, it was a typo, I meant 3^3-1. :) I have TL#4 and I don't know how optimize my solution. There are many DP schemes for this problem but only rather good help to avoid TL. 1:) Is it actually only (n-1) robots? (One for the accountant) 2:) What's the salary arrangement of the first 6 months in the sample? 3:) Is p always larger than the answer? What if not? 4:) What's the answer for the test 4 3 100? Thanks for answering. Somebody please answer these questions. I don't understand the problem. |
|
|