yutaka1999's blog

By yutaka1999, history, 4 years 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

| Write comment?
»
4 years 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).

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

[Reminder] The contest will begin in 30 minutes!

»
4 years 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?

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

    That's what I've done.

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

      How to solve the mentioned problem from JAG Practice Contest?

  • »
    »
    4 years 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
    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I'm very late, but there is a lemma that somehow works (utility is significantly reducing coding time):

      • The number of edges (u,v) with weight w [reversed to (v,u)] where dist(1,v) + w + dist(u,N) < dist(1,N) OR dist(N,v) + w + dist(u,1) < dist(N,1) is O(N).

      Is there a reason for this or is it just weak test data?

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
4 years 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!

»
4 years 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?

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve problem 5 — Fire ?

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

    Please somebody, i can't understand the codes.

  • »
    »
    4 years 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

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

    My Solution is not the same as zscoder, but hope you understand it :)

    click

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

      Hm cool , you post solutions only to relativelly difficult problems? or to easy ones too?

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

        I very recently (read: a week back) started posting solutions. So ill just post the ones which i have solved, which ranges from easy to hard.

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

Can someone explain me the solution of problem C?

  • »
    »
    4 years 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.