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:
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).
The contest has now started!
Reminder: You have 24 hours time to start the contest.
Will where be an editorial for F and G?
We can discuss the problems here after the contest.
how did you guys solve F and how to solve G? ainta pwild
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.)
Is the contest over?
This problem is solvable for all cases except 4 × 4.
The important thing in the problem is to notice that there exists a structure that allows us to visit every cell of a 3 × 4 (or 4 × 3) rectangle and finish in a cell that is opposite to the starting cell. This can be seen in the following image, which is a solution for the 4 × 6 case:
And as can be seen in a solution of a 6 × 6 grid, this structure can be made higher:
And they can be put next to each other:
So now we can solve cases where n ≡ 2 (mod 4) or m ≡ 2 (mod 4). We still need a solution for the case n ≡ 0 (mod 4) or m ≡ 0 (mod 4). This can be solved by using the same structure as before, but this time making it wider and reducing this back to m ≡ 2 (mod 4) case:
And now we can combine all this into a 100p solution.
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.
Is this E? Also, why so low constrains on A when there exists an O(1) solution?
Thanks for the contest, problems were cool =) I liked D very much.
Will there be an editorial or sketch of solutions?
How to solve G?
My solution was very complicated, hopefully there exists a simpler one.
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 rulesB1A -> 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
andS1 -> FSABCD
process the first repetition of the pattern, while creating symbols to cover the latter repetitions.Say our pattern is
010
. Then the string is010010010010010
. After this phase it looks like this:EFESA0A1A0B0B1B0C0C1C0D0D1D0
The next step is to turn
A0 -> G
,A1 -> H
for A and C, andB0 -> 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
, andGI -> 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 rulesSI -> S
and same for JKL, andSX -> _
finish the algorithm.To solve the third subtask, add ABC instead of ABCD. Similarly for the first, add A instead of ABCD.
Well, indeed the model solution seems quite complicated, but pwild's solution sounds like magic to me. Thank you very much for the contest!
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:
And here it is in action: