yutaka1999's blog

By yutaka1999, history, 2 months ago, In English,

Hello Everyone!

The 19th Japanese Olympiad in Informatics Final Round Online Contest will be held on February 9. (01:00 — 05:00 GMT).

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

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

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

»
7 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

[Reminder] The contest will begin in 30 minutes!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the idea for D finding $$$O(N)$$$ interesting edges to test naively or is there a different way?

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

    That's what I've done.

    O(M log M) idea
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to solve the mentioned problem from JAG Practice Contest?

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    If you're still interested, I have a solution in $$$\mathcal{O}(n^3 + m\log m)$$$ (or $$$\mathcal{O}(n^3 + m)$$$, negligible). It passed on oj.uz in 96ms, so it's probably a fine (not too tight) solution:

    Solution
»
7 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

Btw, problems were very nice. It will be good for preparing the IOI. Thanks to the author!

»
7 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

I submited my solution and i got 100/100 points but for my current score is 0 and in ranking it is 0 points, what is going on?

»
7 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve problem 5 — Fire ?

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

    Please somebody, i can't understand the codes.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Basic Idea: For each index $$$i$$$ let $$$prev[i]$$$ denote the largest index less than $$$i$$$ such that $$$a[prev[i]] > a[i]$$$ (-1 if does not exist). Build the forest $$$prev[i] \rightarrow i$$$. Solve the queries offline and build the tree from left to right. Note that the nodes in the forest are labelled in dfs-order. For each edge in the forest, label it with the absolute difference in values (in array $$$a[]$$$) of its endpoints. Then, you can write the answer to a query as the sum of edge weight multiplied by min(subtree size of the child of the edge + some constant, T) where $$$T$$$ depends on query. This can be handled using several fenwick trees.

    Here's my submission: link

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me the solution of problem C?

  • »
    »
    6 weeks ago, # ^ |
    Rev. 3   Vote: I like it +18 Vote: I do not like it

    1) Note that at any moment the set of visited cities is equal to some circular segment.

    2) You may assume that at any moment you are currently in one of the ends of that segment.

    Using these observations, we can solve the problem in $$$O(n^2 \cdot T)$$$ time using $$$dp_{l,r,where,time}$$$, where $$$l \ldots r$$$ denotes the circular segment of currently visited cities and $$$where$$$ is $$$0$$$ if you are currently at $$$l$$$ and $$$1$$$ if you are currently at $$$r$$$, and $$$time$$$ is the current time, and the value of this DP is the largest number of stamps that you can collect.

    After that, you can optimize this DP by changing the state of DP and the value, to optimize $$$O(n^2 \cdot T) \to O(n^3)$$$.

    Final DP will be $$$dp_{l,r,where,cnt}$$$ is the minimum time in which it is possible to be in the state $$$(l,r,where)$$$ as described before and collect $$$cnt$$$ stamps.