joisino's blog

By joisino, history, 4 months ago, In English,

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.

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

»
4 months ago, # |
  Vote: I like it +19 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I'm very curious. How you came up to this idea? What is author solution, btw?

»
4 months ago, # |
  Vote: I like it +13 Vote: I do not like it

You can solve all problems here: https://oj.uz/problems/source/373