Hello!

Indonesia will hold 2017 National Olympiad in Informatics next week (July 3rd — July 5th 2017) in Pekanbaru, Indonesia. It is a competition for Indonesian high school students as one of the preliminary round of Indonesian IOI selection.

And this is the third year for Indonesia (2016, 2015) to invite everyone around the world to try solving the problems by participating the Open Contest! The contest will be conducted on TLX Online Judge. You may need to register for a TLX account if you do not have one. If you have a TLX account, you can login and go to the contest link to register for the contest.

There will be three different contests, one for each day. You may participate them separately (e.g. only participate in Day 1 and Day 2, but not in Day 0), but we expect you to join them all. The Open Contest will start after an hour from the real contest. Here are the schedule and details for the Open Contest:

- Day 0 (Practice Contest): Monday, July 3rd 15.30 — 24.00 (UTC +7). Register here.
- Day 1: Tuesday, July 4th 09.30 — 14.30 (UTC +7). Register here.
- Day 2: Wednesday, July 5th 09.30 — 14.30 (UTC +7). Register here.

The rules of this contest are

- There will be 3 IOI-style problems for each competition day.
- Problem statements will be provided in English and Bahasa Indonesia.
- You can only submit at most 50 submissions for a problem.
- You will get full feedback for each submission.
- For each problem, there are several subtasks:
- For each subtask, there are points assigned to it.
- Each subtask contains several test cases.
- You get the points from that subtask if the program passes all the test cases in that subtask.
- The score of a submission is the sum of all the points that you get from completing subtasks.
- The final score for a problem is the maximum of all the submission scores for that problem.
- Only C++11, C, and Pascal are allowed.
- You will need to read the input from standard input and print the output to standard output.
- You can submit clarification requests in either Bahasa Indonesia or English.
- No medals/certificates will be awarded to Open Contest participants.

NOTE : TLX uses a standard `diff`

to check contestant's output. Therefore, contestant's output must be exactly the same as expected output. (e.g. no extra/missing spaces, no extra/missing newline, etc.). Make sure to print a newline after the last output.

We invite everyone to participate in this contest. See you at the leaderboard.

2017 Indonesian National Olympiad in Informatics Committee

**UPD**: The problems are available for upsolving here

Just a note for those red coders who are looking for challenge (or maybe IOI warmup) :

This contest is one of the first round in choosing Indonesian IOI 2018 team. We still have like around 90 people and we will choose the medalists (around 30 people) to advance to the next round. Thus, the problems on this contest may not be as challenging as you think. As a comparison, this contest is expected to be easier than the recent TOKI Open 2017

We will usually have harder problems for later rounds of selection, but unfortunately we don't normally open those contests for public except the the last contest of our selection, which is TOKI Open in around May.

Auto comment: topic has been updated by jonathanirvings (previous revision, new revision, compare).Auto comment: topic has been updated by jonathanirvings (previous revision, new revision, compare).BUMP! 2017 National Olympiad in Informatics Open Contest day 1 will be started in 10 minutes :)

Is there a public scoreboard, after the contest ends?

There will be a scoreboard after the second day of the competition.

BUMP! 2017 National Olympiad in Informatics Open Contest day 2 will be started in 45 minutes :)

How to solve problem C of day 2?

I can proudly say that I am the author of this problem :) This is the hardest and (IMHO) coolest problem in the problemset.

We will try to post the contest editorial in a few days. Meanwhile, I can give you several observations that might help :

We can check the case where the resulting A and B is the exactly same sequence quite easily. For the case where the resulting A and B is not the same :

How to solve B for 100pts?

Dynamic programming.

First assume that in our solution string there will be no intersection of prefix

sand suffixt. We can use the following state:dp_{t}(i,j,k) means that there is a way to visit some cells from (i,j) such that the resulting string ist_{k},t_{k + 1},t_{k + 2}, ...,t_{lt}(wherel_{t}is the length oft). We can do a similar thing fordp_{s}, but we should reversesfirst.This means that we can find two cells (

i,j) and (i',j') wheredp_{s}(i,j, 1) anddp_{t}(i',j', 1) are true. Then a valid solution is "start somewhere and end in (i,j), go to (i',j'), and end somewhere" and this string will containssas a prefix andtas a suffix.We can compute

dp_{s}(i,j,k) anddp_{t}(i,j,k) inO(nm(l_{s}+l_{t})); details are not very complicated, for example here is recurrence fort(g_{i, j}is the cell at (i,j)):So, now all we have to do is "link" two cells where

dp_{s}(i,j, 1) anddp_{t}(i',j', 1) are true using the minimum number of cells. So we should find the "closest pair of cells" (i,j) and (i',j') (i.e. where |i-i'| + |j-j'| are minimum) wheredp_{s}(i,j, 1) anddp_{t}(i',j', 1) are true. We can do this using some sort of binary search in ; basically, list down all the values of (i,j) wheredp_{s}(i,j, 1) is true and then binary search, for eachi, the closestjto (i',j') for all (i',j') wheredp_{t}(i',j', 1) is true. Probably there are some better ways to do it but this is the easiest. Take the one with the smallest |i-i'| + |j-j'|, saya, then the answer is (a- 1) +l_{s}+l_{t}(l_{s}is length ofs,l_{t}is length oft).Now, what happens if our answer has prefix

sand suffixtoverlapping? Then we will miss the optimal answer. You can see it by testing this solution on the test case given in subtask 2; the optimal answer is but this solution will give .The remedy to this is surprisingly simple. Look for all

usuch thats_{l - u - 1},s_{l - u},s_{l - u + 1}, ...,s_{l}andt_{1},t_{2},t_{3}, ...,t_{u}are equal. You can do it inO(l_{s}^{2}), no need for any fancy algorithms 'causel_{s}is very small. This lets us find all the "cutting points" whereswill overlaptin our solution.Now we simply look for all pairs (

i,j) wheredp_{s}(i,j, 1) is true and check ifdp_{t}(i,j,u+ 1) is also true (basically skippingt_{1},t_{2},t_{3}, ...,t_{u}, since they are already covered bys) for some cutting pointu(just check all up tol_{s}cutting points). You can then recover the answer in this case inO(nml_{s}).In total, it runs in and it passes all subtasks.

The part of finding closest pair of cells can be done in

O(n*m) by doing BFS to find the shortest distance from a cell (x,y) any cell (i,j) such thatdp_{s}(i,j, 1) =true, and then iterate over all cell (i',j') such thatdp_{t}(i',j', 1) =trueand update the answer.Makes sense. That's a pretty neat trick!

Auto comment: topic has been updated by jonathanirvings (previous revision, new revision, compare).The official 2017 National Olympiad in Informatics result will be announced tomorrow. The scoreboard of the 2017 National Olympiad in Informatics Open Contest will be published shortly after that. Please be patient :)