When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

yutaka1999's blog

By yutaka1999, history, 3 years ago, In English

Hello Everyone!

The 20th Japanese Olympiad in Informatics Final Round Online Contest will be held on February 14. (08:00-12:00 GMT).

The contest duration is 4 hours. There are five problems, which are the same as the 20th 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
  • +138
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

This is the best valentines gift someone could gave me.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Has anyone logged in the contest page?

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

    Sorry for disturbing,something strange happended to my chrome.Now it has recovered.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Has anyone else had problem with getting tle on about five cases of p4 robot, while the rest were well within limit? If so, what did you fix?

»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Great problems, thank you!

Especially the last problem seems interesting. How to solve it? I tried some cartesian-tree like approach but didn't get to the full solution.

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

    I didn't think it through too deeply, but can you explain which part of your solution you wasn't able to implement? I'm talking about storing euler tour in cartesian tree, then increase $$$u$$$ and updating euler tour accordingly, since there will be $$$O(n)$$$ link/cut operations. For fixed path from $$$s$$$ to $$$t$$$ then answer can be calculated as sum of answers on some subsegments, and for each subsegment the answer is either $$$(p_i - p_{i-1}) \cdot c_{i-1}$$$ when $$$c_i \leq c_{i-1}$$$ or $$$u \cdot c_1 + (p_2 - p_1) \cdot c_2 + \ldots + (p_{k-2} - p_{k-3}) \cdot c_{k-2} + (p_k - p_{k-2} - u) \cdot c_{k-1}$$$ when $$$c_i < c_{i+1}$$$ for $$$i < k - 1$$$ and $$$c_{k-1} \geq c_{k}$$$, which is a linear function of $$$u$$$ (which I hope is possible to maintain in cartesian tree via 2-3 types of lazy propagation).

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    Here's a solution using only standard data structures.

    Step 1.
    Step 2.
  • »
    »
    3 years ago, # ^ |
    Rev. 5   Vote: I like it +19 Vote: I do not like it

    (Haven't read the whole solution above yet, but I think this is different.)

    (oops is the spoiler below broken)

    Spoiler

    Code (needs C++17 ...)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the test data for the problems be released?

»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Could anyone explain their solution to Problem 4? Thanks!