By proofbycontradiction, history, 20 months ago, ,

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)?

EDIT: This editorial is incorrect.

• +4

 » 20 months ago, # |   0 Auto comment: topic has been updated by eigenvalue (previous revision, new revision, compare).
 » 20 months ago, # | ← Rev. 2 →   +8 Your code produces different outputs for 2 2 3 1 2 3 2 and 2 2 3 2 2 3 1 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)
•  » » 20 months ago, # ^ |   0 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?
•  » » » 20 months ago, # ^ |   +8 This is the official after-contest presentation with the solutions. But is in portuguese :(Maybe you can get a hint translating it
 » 20 months ago, # |   0 Auto comment: topic has been updated by eigenvalue (previous revision, new revision, compare).
 » 20 months ago, # | ← Rev. 2 →   0 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?
•  » » 20 months ago, # ^ |   0 Thanks. I resolved the problem with that idea.
•  » » 20 months ago, # ^ |   0 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.
•  » » 20 months ago, # ^ |   0 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
•  » » » 20 months ago, # ^ |   +7 Yay, I got accepted in the Gym. Thanks :)
 » 20 months ago, # |   -8 WA means for some test case, you are getting wrong answer.
•  » » 20 months ago, # ^ |   +8 No shit Sherlock
•  » » 18 months ago, # ^ |   0 you son have too much free time!