### pllk's blog

By pllk, history, 2 years ago,

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

• +72

 » 2 years ago, # |   +37 The contest has now started!
 » 2 years ago, # |   +16 Reminder: You have 24 hours time to start the contest.
 » 2 years ago, # |   +8 Will where be an editorial for F and G?
•  » » 2 years ago, # ^ |   +16 We can discuss the problems here after the contest.
 » 2 years ago, # |   0 how did you guys solve F and how to solve G? ainta pwild
•  » » 2 years ago, # ^ |   +14 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.)
•  » » » 2 years ago, # ^ |   +1 Is the contest over?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +8 Solution for FThis 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.
 » 2 years ago, # |   0 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.
 » 2 years ago, # | ← Rev. 3 →   0 Is this E? Also, why so low constrains on A when there exists an O(1) solution?
 » 2 years ago, # |   +5 Thanks for the contest, problems were cool =) I liked D very much.Will there be an editorial or sketch of solutions?
 » 2 years ago, # |   +10 How to solve G?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +10 My solution was very complicated, hopefully there exists a simpler one. 100p solution#include #include #include using namespace std; vector res; void addMoves(char c) { string add[4] = {"?00 -> 0?0", "?01 -> 0?1", "?10 -> 1?0", "?11 -> 1?1"}; for (int i = 0; i < 4; ++i) { add[i][0] = c; add[i][8] = c; res.push_back(add[i]); } } void addSwaps(char a, char b) { string add[2] = {"?0_ -> _0?", "?1_ -> _1?"}; for (int i = 0; i < 2; ++i) { add[i][0] = a; add[i][2] = b; add[i][7] = b; add[i][9] = a; res.push_back(add[i]); } } void addEat(char a, char zt, char ot) { string add = "?0 -> _"; add[0] = a; add[6] = zt; res.push_back(add); add[1] = '1'; add[6] = ot; res.push_back(add); } int main() { int k; cin >> k; // 2 commands to move start marker to start res.push_back("0X -> X0"); res.push_back("1X -> X1"); // 16 move commands addMoves('A'); addMoves('B'); addMoves('C'); addMoves('D'); // 12 swap commands addSwaps('B', 'A'); addSwaps('C', 'B'); addSwaps('C', 'A'); addSwaps('D', 'C'); addSwaps('D', 'B'); addSwaps('D', 'A'); // 2 commands for building space if (k == 2) { res.push_back("X0 -> EXA"); res.push_back("X1 -> FXA"); } else if (k == 3) { res.push_back("X0 -> EXAB"); res.push_back("X1 -> FXAB"); } else if (k == 4) { res.push_back("X0 -> EXABC"); res.push_back("X1 -> FXABC"); } else if (k == 5) { res.push_back("X0 -> EXABCD"); res.push_back("X1 -> FXABCD"); } // 8 commands for eating nums addEat('A', 'G', 'H'); addEat('B', 'E', 'F'); addEat('C', 'G', 'H'); addEat('D', 'E', 'F'); // 2 commands to move start marker to start res.push_back("EX -> XE"); res.push_back("FX -> XF"); // 4 commands to move end marker to end res.push_back("YE -> EY"); res.push_back("YF -> FY"); res.push_back("YG -> GY"); res.push_back("YH -> HY"); // 8 commands for flipping res.push_back("EI -> IE"); res.push_back("FI -> IF"); res.push_back("EJ -> JE"); res.push_back("FJ -> JF"); res.push_back("GK -> KG"); res.push_back("HK -> KH"); res.push_back("GL -> LG"); res.push_back("HL -> LH"); // 4 commands for turning res.push_back("GI -> K"); res.push_back("HJ -> L"); res.push_back("EK -> I"); res.push_back("FL -> J"); // 4 commands to make end start chains res.push_back("EY -> IY"); res.push_back("FY -> JY"); res.push_back("GY -> KY"); res.push_back("HY -> LY"); // 4 commands to make start eat res.push_back("XI -> X"); res.push_back("XJ -> X"); res.push_back("XK -> X"); res.push_back("XL -> X"); // 2 commands to make start res.push_back("0 -> X0"); res.push_back("1 -> X1"); // 4 commands to make end res.push_back("E -> EY"); res.push_back("F -> FY"); res.push_back("G -> GY"); res.push_back("H -> HY"); // 1 command to have start eat end res.push_back("XY -> _"); // Print res cout << res.size() << '\n'; for (auto str : res) cout << str << '\n'; } 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: EFESA0A1A0B0B1B0C0C1C0D0D1D0The 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: EFESGHGEFEGHGEFENow 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.
•  » » » 2 years ago, # ^ |   0 Well, indeed the model solution seems quite complicated, but pwild's solution sounds like magic to me. Thank you very much for the contest!
 » 2 years ago, # |   +28 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# 9) reject the string using a Z to consume all bits (this may be buggy but worked on all cases) Z0 -> Z Z1 -> Z 0Z -> Z 1Z -> Z # 7) send the X or Y to the left, discard in case of a mismatch 0X -> X0 1X -> X1 0Y -> Y0 1Y -> Y1 0AX -> A 1AY -> A AX -> Z AY -> Z 0BX -> XB 1BY -> YB BX -> Z BY -> Z # 4) change F,G,H back to A,B,C by sending a Q from left to right Q0 -> 0Q Q1 -> 1Q QH -> C QG -> BQ F -> AQ # 3) move A,B,C to the right by 1,2,3 steps and change them to F,G,H C000 -> 000H C001 -> 001H C010 -> 010H C011 -> 011H C100 -> 100H C101 -> 101H C110 -> 110H C111 -> 111H # 5) C cannot be moved further and the string length is not a multiple of k, reject C0 -> Z C1 -> Z # 6) C reached the right end of the string, replace last bit by X or Y 0C -> XC 1C -> YC # 3) move A,B,C to the right by 1,2,3 steps and change them to F,G,H B00 -> 00G B01 -> 01G B10 -> 10G B11 -> 11G A0 -> 0F A1 -> 1F # 8) if there is only ABC left, accept ABC -> _ # 2) add ABC to the front of the string 1W -> W1 W -> ABC 0 -> W0 # 1) accept strings of the form (111)^n 111 -> _ And here it is in action: Spoiler110110110 11W0110110 1W10110110 W110110110 ABC110110110 AB110H110110 A11G0H110110 1F1G0H110110 1AQ1G0H110110 1A1QG0H110110 1A1BQ0H110110 1A1B0QH110110 1A1B0C110110 1A1B0110H110 1A101G10H110 11F01G10H110 11AQ01G10H110 11A0Q1G10H110 11A01QG10H110 11A01BQ10H110 11A01B1Q0H110 11A01B10QH110 11A01B10C110 11A01B10110H 11A0110G110H 110F110G110H 110AQ110G110H 110A1Q10G110H 110A11Q0G110H 110A110QG110H 110A110BQ110H 110A110B1Q10H 110A110B11Q0H 110A110B110QH 110A110B110C 110A110B11XC 110A110B1X1C 110A110BX11C 110A11XB11C 110A1X1B11C 110AX11B11C 11A11B11C 11A11B1YC 11A11BY1C 11A1YB1C 11AY1B1C 1A1B1C 1A1BYC 1AYBC ABC