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:
- Day 0: 12 October 2020 09:00 — 21:30 UTC (trial session)
- Day 1: 13 October 2020 06:30 — 21:30 UTC
- Day 2: 14 October 2020 06:30 — 21:30 UTC
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.
See you on the leaderboard!
UPD Thanks to everyone who participated! Our top 3:
- rama_pang (564 points)
- wiwitrifai (559 points)
- Meijer (556 points)
The rest of the scores can be found here.
You can upsolve the problems here.
We thank everyone who are involved:
- Yoshiyuki, prabowo, AMnu, hocky, rfpermen, wijayareynaldo as Scientific Committee
- fushar, nathanchrs, aguss787 as Technical Committee
- AMnu, rfpermen, prabowo, AVM.Martin, Yoshiyuki as problem authors
- malfple, Klungs as testers
- ya_ for helping me with this open contest
We hope we can conduct the open contest again, and see you next year!
Inb4 0A is Hello World
Never mind, saw past problems
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.
A friendly reminder that you can already start your 5-hour virtual of the Day 1 competition
Will there be editorials available after the contest ?
Yes
You can also discuss the problems after each day of the contest is over
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.
prabowo Is it only me who can't see the editorial or has it either not been created or not been uploaded yet? From what I have just noticed, there was no editorial last year whatsoever despite it being promised. I hope it won't be the case this year.
There was an editorial for last year's contest, here is the link.
Sadly, it's written in Indonesian and there are no translations of it AFAIK.
There is no official editorial yet, sadly. However, we decided to make our own unofficial version, read more about it here.
The second day of the contest will be available in 30 minutes
Why I can not register in TLX?
If you were trying to register for the day 1 contest, unfortunately, the registration is already closed. Only day 2 is currently available.
I mean I can not create an account in TLX.
Could I have more details on this? What error did you encounter when registering?
I press "register",but it has no respond.
PM-ed you.
Any ideas/hints on how to solve Problem 3 (Maintaining Distance) from Day 1 for max constraints ?
Try to use backtracking
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.
This is also my first time encountering a pure DP problem that doesn't need to output the backtrack but using backtracking observation.
Problem link
We 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)$$$.
We 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$$$:
Using the facts above, we will make use of their converses and compute the value of the $$$dp$$$ using $$$excluded$$$:
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]$$$
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]$$$
This case is reached when the above two cases failed.
Then $$$dp[N][K] = dp[N-1][K] + 1$$$
Total complexity: $$$O(NK)$$$
Can anyone give me a hint on problem 1A?
I think you have to solve them all individually
With some kind of brute force in the bigger ones?
This is how I did it:
The 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.
Will problems be available for upsolving?
Yes, all open contest results will also be available once our closing ceremony is over tomorrow
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)$$$.
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
Auto comment: topic has been updated by prabowo (previous revision, new revision, compare).