I am trying to solve Problem M: Counting Marbles. I am writing an editorial in case somebody might need it after me, and I am also trying to ask for help in spotting the error in my code.
Editorial:
We are essentially trying to write the smallest base-365 number with the marbles. So we must minimize the earlier digits as much as possible.
Use a priority queue with the tops of the stack, and whenever you use a marble, remove it from the priority queue and put the next element in the queue instead. Please see my solution for one such implementation.
Help: My solution is able to run on the sample test cases, but I'm getting WA (could somebody take a look at this)?
My solution: https://www.ideone.com/VnKScW
Problem Statement: http://codeforces.com/gym/101889/attachments/download/7471/statements-2017-latam-regional.pdf
EDIT: This editorial is incorrect.
Auto comment: topic has been updated by proofbycontradiction (previous revision, new revision, compare).
Your code produces different outputs for
and
Because the priority queue just doesnt know which stack to start removing the 3 (you would have to see the next contents of it — the official solution is more complicated)
Ah, damn, you're right of course. I don't know how I managed to convince myself that this was not a problem.
Do you have a link to the official solutions?
This is the official after-contest presentation with the solutions. But is in portuguese :(
Maybe you can get a hint translating it
Auto comment: topic has been updated by proofbycontradiction (previous revision, new revision, compare).
If I remember well in that problem you need to sort the suffixes of the stacks lexicographically, and if a suffix is the prefix of another suffix then the longer suffix should be ranked first. This can be done concatenating all stacks using 301 as a separator character between them and at the end, and then you run an efficient suffix array algorithm. You can debug your solution with the official tests cases which can be found here: http://maratona.ime.usp.br/resultados17/M/
Btw, I used an O(n log n) implementation of the suffix array algorithm which uses radix sort instead of std::sort for sorting, I tested my solution with the official test cases and it gets all answers right and in less than 3 seconds, but in live archive I always get TLE. Did someone get accepted? Do I have to use O(n) suffix array implementation instead?
Thanks. I resolved the problem with that idea.
Some online judges have shitty TL for some problems. This might be the one of those cases. One of the teams passed the problem using O(nlog^2n) suffix array using hash for sorting so O(nlog^2n) or O(nlogn) suffix array without hash should be enough.
Try submitting in the Gym. The actual TL was 1 second for 1 test case. Live Archive for some reason used multiple test cases with 3s time limit
Yay, I got accepted in the Gym. Thanks :)
WA means for some test case, you are getting wrong answer.
No shit Sherlock
you son have too much free time!