### Prabowo's blog

By Prabowo, history, 12 days ago,

Hello Codeforces community,

Similar to last year, we are excited to invite you to TOKI KSN Open Contest 2020 -- an online mirror contest for Indonesia national olympiad in informatics. This national olympiad is one of the stages required for our students to qualify to represent Indonesia in the International Olympiad in Informatics (IOI).

The contest is similar to IOI: 2 competition days (+ 1 trial session), each consisting of 3 IOI-style (partial, subtasks) problems to be solved in 5 hours. The schedule is as follows:

Each contestant can select any 5-hour window within the time range to do the contest for each competition day. Each contestant may start the contest any time within the time range, by clicking the "start" button.

All three contests are now available on TLX. Please register in those contests. You may need to register for a TLX account if you do not have one.

For more detailed information and rules, see our official website.

UPD Thanks to everyone who participated! Our top 3:

1. rama_pang (564 points)
2. wiwitrifai (559 points)
3. MarcoMeijer (556 points)

The rest of the scores can be found here.

You can upsolve the problems here.

We thank everyone who are involved:

We hope we can conduct the open contest again, and see you next year!

• +125

 » 12 days ago, # |   +7 Inb4 0A is Hello World
 » 12 days ago, # | ← Rev. 2 →   0 Never mind, saw past problems
•  » » 12 days ago, # ^ |   +16 As this is an early stage of our IOI selection, the tasks are expected to be simpler from IOI. This round will select around 30 people to advance to the next stage of the selection.And as of other OI type contests, it is intended to participate in the contest as an individual.
 » 9 days ago, # |   0 A friendly reminder that you can already start your 5-hour virtual of the Day 1 competition
•  » » 9 days ago, # ^ |   +3 Will there be editorials available after the contest ?
•  » » » 8 days ago, # ^ |   +8 YesYou can also discuss the problems after each day of the contest is over
•  » » » » 4 days ago, # ^ |   0 When exactly will the editorial become available? I want to ensure that I'm not going to miss it, as everything else is already published.
 » 8 days ago, # |   0 The second day of the contest will be available in 30 minutes
 » 8 days ago, # |   0 Why I can not register in TLX?
•  » » 8 days ago, # ^ |   0 If you were trying to register for the day 1 contest, unfortunately, the registration is already closed. Only day 2 is currently available.
•  » » » 8 days ago, # ^ |   0 I mean I can not create an account in TLX.
•  » » » » 8 days ago, # ^ |   0 Could I have more details on this? What error did you encounter when registering?
•  » » » » » 8 days ago, # ^ |   0 I press "register",but it has no respond.
•  » » » » » » 8 days ago, # ^ |   0 PM-ed you.
 » 8 days ago, # |   0 Any ideas/hints on how to solve Problem 3 (Maintaining Distance) from Day 1 for max constraints ?
•  » » 8 days ago, # ^ |   0 HintTry to use backtracking
•  » » » 8 days ago, # ^ |   0 This is my first time encountering a DP problem with backtracking , can you explain a little more or if its a common technique/optimization could you link to some resource.
•  » » » 8 days ago, # ^ |   0 This is also my first time encountering a pure DP problem that doesn't need to output the backtrack but using backtracking observation.
•  » » 8 days ago, # ^ | ← Rev. 3 →   +32 Problem link First stepWe will describe the $O(NK^2)$ solution first.We define $dp[N][K]$ as the minimum number of group that can be created, if the groups are people from number $1..N$ and we will exclude $K$ people from the queue.Let $left[N][k]$ be the minimum number of people left, if we tried to exclude $k$ people from the last group. Then, $dp[N][K] = \min(dp[left[N][i]][K - i]), \forall i ≤ K$This means we will try to form a group if we try to exclude $0, 1, \dots, K$ people from the last group.It is possible to compute all values of the table $left[N][K]$ in $O(NK)$ by maintaining the occurrences of each distinct element, and the number of unique elements with occurrences $≥ M$.Therefore, the whole $dp$ values can be computed in $O(NK^2)$. Next stepWe define $excluded[N][K]$ as the number of people excluded in the last group of the queue in the optimal grouping of $N$ people and excluding at most $K$ people. The values of $excluded$ can be computed with the help of $dp$: If the value of $dp[N][K] = dp[N-1][K]$, then $excluded[N][K] = excluded[N-1][K]$. This means the $N$-th person is included in the last group, and hence no additional group is required. If the value of $dp[N][K] = dp[N-1][K-1]$, then $excluded[N][K] = excluded[N-1][K-1] + 1$. This means the $N$-th person is excluded from the queue If the value of $dp[N][K] = dp[N-1][K] + 1$, then $excluded[N][K] = 0$. This means a new group is formed for the $N$-th person. Using the facts above, we will make use of their converses and compute the value of the $dp$ using $excluded$: The $N$-th person is included in the last group. This can be checked by the equality $dp[ left[N][excluded[N-1][K]] ][ K - excluded[N-1][K] ] + 1 = dp[N-1][K]$. Then $dp[N][K] = dp[N-1][K]$ The $N$-th person is excluded from the queue. This can be checked by the equality $dp[ left[N][excluded[N-1][K-1] + 1]][K - excluded[N-1][K-1] - 1] + 1 = dp[N-1][j]$. Then $dp[N][K] = dp[N-1][K]$ A new group is formed for the $N$-th person. This case is reached when the above two cases failed. Then $dp[N][K] = dp[N-1][K] + 1$ Total complexity: $O(NK)$
 » 7 days ago, # |   0 Can anyone give me a hint on problem 1A?
•  » » 7 days ago, # ^ |   0 I think you have to solve them all individually
•  » » » 6 days ago, # ^ |   +8 With some kind of brute force in the bigger ones?
•  » » » » 6 days ago, # ^ | ← Rev. 2 →   +13 This is how I did it: SolutionsThe first two I just solved by hand.The third one has a width of one so it is just rectangles with a width of one on top of eachother.The fourth one has a width of $99999$, a height of $50000$, and rectangles with an area of $1...99999$. Becouse $1+99998=99999, 2+99997=99999, ..., 49999+50000=99999$ we can make $49999$ pairs of rectangles with a combined height of $99999$. We place all of these pairs of rectangles next to each other, and add the final rectangle of area $99999$.The fifth one is just $293×311$ rectangles with a width of $9973$ and a height of $99991$ placed next to each other in a grid.The sixt one has a width of $2$. So every rectangle is either in collumn $1$, in collumn $2$, or in both. Becouse rectangles of an odd area can't be in both, rectangles of odd size have $2$ options each, and rectangles of an even size have $3$ options each. This gives us $2^{10}*3^{10}=60,466,176$ ways of placing the rectangles in collumns. I brutforced through all the ways until I found one way such that each collumn has exactly $M$ squares occupied.The seventh one is simular to the sixt one, but this one has $100$ rectangles and a smaller value of $M$. I solved it by using dp. With $dp[i][j]$ = if it is possible to use at most $M$ squares in both collumns, where the first $i$ rectangles are already placed, and the first collumn has $j$ squares occupied.The eighth one is kinda hard to explain. But what you had to notice is that $N*M=2^{30}-1$. I made rectangles with a width of the bits values of $N$ and with a height of the bit values of $M$. For example, the binary representation of $N=4681$ is $1001001001001$ so I only made rectangles with a width of $1,8,64,512$ and $4096$. I did the same thing in the other Axis.The ninth one has a really nice solution. Lets say $A_i={B_i}^2$. Then $\sqrt{A_i}=\sqrt{A_{i-1}}+\sqrt{A_{i-2}}$ gives us $\sqrt{{B_i}^2}=\sqrt{{B_{i-1}}^2}+\sqrt{{B_{i-2}}^2}$ so $B_i=B_{i-1}+B_{i-2}$. $B_i$ is equal to the fibonacci sequence, so $A_i$ is equal to the squares of the fibonacci sequence. If you go to this page https://en.wikipedia.org/wiki/Golden_ratio#Relationship_to_Fibonacci_sequence you can see a picture of the 'fibonacci spiral'. The answer to this subtask is basically that for the first $23$ fibonacci numbers. A big hint that this would fit is that $N/M$ is equal to the golden ratio.For the last one I just made a greedy solution. Becouse it says the test case is randomly generated you can assume that the test case is really weak. What i did was make every rectangle $1$ wide, and just placed them were they fitted, starting from the biggest rectangles.
 » 7 days ago, # |   0 Will problems be available for upsolving?
•  » » 7 days ago, # ^ |   0 Yes, all open contest results will also be available once our closing ceremony is over tomorrow
 » 7 days ago, # |   +8 Can anyone check my solution to 2B? I messed up my implementation during the contest.We can think of start and finishing point as pillars too, with an upgrade cost of infinity. First we only think about horizontal movement. Suppose from a pillar $p_1$ we can reach $p_2, p_3, ...$. Then from there we reach some other nodes. If we keep doing this then we will visit a 'Horizontal Slice' of points. After processing all points, we will end up with some Slices, which are disjoint.We also do this for vertical movement, and create our 'Vertical Slices'. Now we create 2 nodes for each pillar, a horizontal and a vertical one. Suppose a point $p$'s horizontal node is $H(p)$ and vertical node is $V(p)$. For a horizontal node, We look at its horizontal slice, let the pillars be $p_1, p_2, ... p_c$. We add edges of weight 0 between every $H(p_i), H(p_{i + 1})$. Also do the same for every vertical nodes in their corresponding vertical slices. Finally add edges $H(p), V(p)$ with the weight equal to the cost of that pillar. Now answer is shortest path between $H(s)$ and $H(f)$ or $V(f)$.
•  » » 7 days ago, # ^ |   +8 I did the same and got accepted. But i made the upgrade cost of f equal to zero. This way the answer is the shortest path between H(s) and H(f). This is my code: https://pastebin.com/PjJquisX
 » 4 days ago, # |   0 Auto comment: topic has been updated by Prabowo (previous revision, new revision, compare).