Hello Everyone!
The 18th Japanese Olympiad in Informatics Final Round Online Contest will be held on February 10. (01:00 — 05:00 GMT).
The contest duration is 4 hours. There are five problems, which are the same as the 18th JOI Final Round. Problem statements will be provided both in Japanese and English.
The registration page will be announced 30 minutes before the contest start.
You can see details in the contest information page.
How to solve E?
A brief solution:
Let D1 and D2 be endpoints of a diameter. Let's start Depth-first-search from D1. While traversing, maintain a set S of vertices and keep the following invariant: when you go back from a vertex x to its parent vertex, S is the set of unique vertices for the vertex x which lie on the path between D1 and x. In addition, when you choose a subtree to go down, choose the highest subtree. Now it can be shown that the number of increases and decreases of elements of S is O(N). Start the same DFS from D2 and the problem can be solved in O(N) time.
Why didn't I see this in recent actions >:( Why didn't you make a reminder comment before a day like others does >:( Missed the contest for not getting the news earlier. Do JOI have some kind of newsletter system to notify interested participants about future contests? Or is the schedule published somewhere (Like USACO Schedule)?
What is the intended solution for Problem 3? Is it O(n3) DP with lot of optimization? My states are (position, last used character, number of A used, number of B used), where A, B are two characters with minimum number of occurrences. I got AC with loop-unroll but TLE in last subtask without that.
The O(n^2) solution I came up with doesn't seem to be intended as it passes with 0.02s/0.5s and 400kb/1gb.
dp[prefix considered][bitmask of colors of some suffix][length of the suffix][color before the suffix]
https://ideone.com/rmvMsI
Can you explain what your transitions are in the dp? Also, did you prove that the optimal answer for some prefix is part of the optimal answer for the whole problem, or just used dp by intuition?
In case it helps, I posted my solution to this problem (and also the code) here :)
You can solve all problems here: https://oj.uz/problems/source/373