Блог пользователя yutaka1999

Автор yutaka1999, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +138
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

This is the best valentines gift someone could gave me.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Has anyone logged in the contest page?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
      Проголосовать: нравится +46 Проголосовать: не нравится

    Here's a solution using only standard data structures.

    Step 1.
    Step 2.
  • »
    »
    3 года назад, # ^ |
    Rev. 5   Проголосовать: нравится +19 Проголосовать: не нравится

    (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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will the test data for the problems be released?

»
3 года назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Could anyone explain their solution to Problem 4? Thanks!