jonathanirvings's blog

Invitation to 2017 Indonesian National Olympiad in Informatics Open Contest
By jonathanirvings, history, 7 years ago, In English

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:

  1. Day 0 (Practice Contest): Monday, July 3rd 15.30 — 24.00 (UTC +7). Register here.
  2. Day 1: Tuesday, July 4th 09.30 — 14.30 (UTC +7). Register here.
  3. 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

  • Vote: I like it
  • +70
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +30 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by jonathanirvings (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by jonathanirvings (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Is there a public scoreboard, after the contest ends?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +24 Vote: I do not like it

How to solve problem C of day 2?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +30 Vote: I do not like it

    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 :

    1. There exists an optimal solution which only uses the type-3 operation once.
    2. Suppose cntA is the number of operations (only consider type-1 operation) needed to make the sequence A arithmetic and cntB is the number of operations (only consider type-2 operation) needed to make the sequence B arithmetic. Then the answer is either cntA + cntB — 1 or cntA + cntB.
    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B for 100pts?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Dynamic programming.

    First assume that in our solution string there will be no intersection of prefix s and suffix t. We can use the following state:

    dpt(i, j, k) means that there is a way to visit some cells from (i, j) such that the resulting string is tk, tk + 1, tk + 2, ..., tlt (where lt is the length of t). We can do a similar thing for dps, but we should reverse s first.

    This means that we can find two cells (i, j) and (i', j') where dps(i, j, 1) and dpt(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 contains s as a prefix and t as a suffix.

    We can compute dps(i, j, k) and dpt(i, j, k) in O(nm(ls + lt)); details are not very complicated, for example here is recurrence for t (gi, j is the cell at (i, j)):

    So, now all we have to do is "link" two cells where dps(i, j, 1) and dpt(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) where dps(i, j, 1) and dpt(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) where dps(i, j, 1) is true and then binary search, for each i, the closest j to (i', j') for all (i', j') where dpt(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'|, say a, then the answer is (a - 1) + ls + lt (ls is length of s, lt is length of t).

    Now, what happens if our answer has prefix s and suffix t overlapping? 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 u such that sl - u - 1, sl - u, sl - u + 1, ..., sl and t1, t2, t3, ..., tu are equal. You can do it in O(ls2), no need for any fancy algorithms 'cause ls is very small. This lets us find all the "cutting points" where s will overlap t in our solution.

    Now we simply look for all pairs (i, j) where dps(i, j, 1) is true and check if dpt(i, j, u + 1) is also true (basically skipping t1, t2, t3, ..., tu, since they are already covered by s) for some cutting point u (just check all up to ls cutting points). You can then recover the answer in this case in O(nmls).

    In total, it runs in and it passes all subtasks.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      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 that dps(i, j, 1) = true, and then iterate over all cell (i', j') such that dpt(i', j', 1) = true and update the answer.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Makes sense. That's a pretty neat trick!

        → Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Auto comment: topic has been updated by jonathanirvings (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply