proofbycontradiction's blog

WA in ACM ICPC Latin Regional Contest [Greedy][Editorial]
By proofbycontradiction, history, 6 years ago, In English

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://mirror.codeforces.com/gym/101889/attachments/download/7471/statements-2017-latam-regional.pdf

EDIT: This editorial is incorrect.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by proofbycontradiction (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      This is the official after-contest presentation with the solutions. But is in portuguese :(

      Maybe you can get a hint translating it

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by proofbycontradiction (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks. I resolved the problem with that idea.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

WA means for some test case, you are getting wrong answer.

→ Reply