pllk's blog

By pllk, history, 6 years ago, In English

The final round of the Finnish Olympiad in Informatics (Datatähti) will take place tomorrow, and after the official contest, there will be an international online contest.

The online contest will be available at CSES:

https://cses.fi/

The length of the contest will be 5 hours, and there will be 7 tasks of varying difficulty. The contest will follow the IOI rules: full feedback and no penalty for multiple submissions. Available languages are C++, Java, Pascal and Python.

The online contest will be a virtual contest, which means that you can start the contest at any time between 17 Jan 2019, 20:00 and 20 Jan 2019, 15:00 (UTC).

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

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

The contest has now started!

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

Reminder: You have 24 hours time to start the contest.

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

Will where be an editorial for F and G?

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

    We can discuss the problems here after the contest.

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

how did you guys solve F and how to solve G? ainta pwild

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

    The contest is still running, so let's wait some more hours before discussing. (The scoreboard was misconfigured and was revealed for a short while, sorry for that.)

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it
    Solution for F
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest has ended and the results are here:

https://cses.fi/231/scores/

Congratulations to pwild for winning the contest!

This year's contest was difficult, as you can see in the scoreboard. In the official contest, the maximum score was only 412.

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

Is this E? Also, why so low constrains on A when there exists an O(1) solution?

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

Thanks for the contest, problems were cool =) I liked D very much.

Will there be an editorial or sketch of solutions?

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

How to solve G?

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    My solution was very complicated, hopefully there exists a simpler one.

    100p solution

    For the last subtask, my idea was to add four characters ABCD, that will cover the last four repetitions of the pattern. They have rules A00 -> 0A0, A01 -> 0A1, A10 -> 1A0, A11 -> 1A1 to move them to the end, keeping a spacing of one character, and rules B1A -> A1B and so on to put them in the correct order.

    To make use of these, first I got a symbol S marking the start of the string to the start of the string, and then two rules S0 -> ESABCD and S1 -> FSABCD process the first repetition of the pattern, while creating symbols to cover the latter repetitions.

    Say our pattern is 010. Then the string is 010010010010010. After this phase it looks like this: EFESA0A1A0B0B1B0C0C1C0D0D1D0

    The next step is to turn A0 -> G, A1 -> H for A and C, and B0 -> E, B1 -> F for B and D. Now the string looks like this: EFESGHGEFEGHGEFE

    Now we need an end-symbol, let's call it X. Also, move the start symbol to the start. SEFEGHGEFEGHGEFEX.

    Then we just need to finish. Add the rules EX -> IX, EI -> IE, FI -> IF, and GI -> K. Do similarly for J, K and L. This makes the appearances of E move to the beginning of their repetition of the pattern, and then check that the last letter of the previous repetition is the same as the last letter of this repetition. If it is, they next process the previous pattern in the same way. If it isn't, the letter gets stuck here, and will never be removed.

    A couple intermediate steps: SEFEGHGEFEGHGEFIX SEFEGHGEFEGHGIEFX SEFEGHGEFEGHKEFX SEFEGHGEFEKGHEFX SEFEGHGEFIGHEFX and so on.

    So after this phase the string will look like this: SIJIX. Then the rules SI -> S and same for JKL, and SX -> _ finish the algorithm.

    To solve the third subtask, add ABC instead of ABCD. Similarly for the first, add A instead of ABCD.

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

      Well, indeed the model solution seems quite complicated, but pwild's solution sounds like magic to me. Thank you very much for the contest!

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

Thanks for the contest, I really liked the problems. Interesting choice to have two constructive tasks for the hardest problems.

Here's what I did for G: Put k extra symbols in front of the string, then move them to the right in steps of 1,2,..,k until the string is split into k parts of equal length. Now "consume" these k parts one bit at a time until the string is empty while checking that the removed bits are equal.

While solving this problem, one often needs to relay information from one part of the string to another. This can be done with rules of the form X0 -> 0X, X1 -> 1X and the information can be encoded in the symbol.

Here's an annotated solution for the case k=3. I numbered the comments to show the order of execution:

Spoiler

And here it is in action:

Spoiler