E869120's blog

By E869120, 9 months ago, In English

Hello, everyone!

The 23nd Japanese Olympiad in Informatics (JOI 2023/2024) Final Round will be held from Sunday, February 04th, 10:00 UTC to Monday, February 05th, 10:00 UTC. The contest information is as follows:

  • Contest duration: 4 hours (You can choose start time freely in 24-hour window)
  • Number of tasks: 5 tasks
  • Max score for each task: 100 points
  • Style: IOI-Style (There may be some partial scores)
  • Problem Statement: Japanese & English

Note that since the contest ends at Monday, February 05th, 10:00 UTC, if you start the contest after Monday, February 05th, 06:00 UTC, the duration will be shorter than 4 hours.

The registration page and live scoreboard will be announced 30 minutes before the contest starts. Details are available in the contest information page.

We welcome all participants. Good luck and have fun!

UPD1: The contest will start in 24 hours.
UPD2: Now the contest is started, so good luck and have fun. Note that you can start any time in 24-hour window.
UPD3: The contest is ended. Thank you for your participation.

Tags joi, ioi
  • Vote: I like it
  • +290
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

anyone know how to solve problem 3 and 5 ?

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

    For problem 3, first consider how to answer one question. Balls at the same position can be merged, then consider the entire process in reverse order, The last ball collected must be one of the balls on left or right side of the end point, and the last $$$k$$$ balls collected must form an interval. Enumerate the last ball collected(at most 2 different balls possible), the observation leads a DP that $$$f_{l,r}$$$ indicates if we collect the balls between $$$l$$$-th to the $$$r$$$-th position at the end of entire process, what is the minimal time to collect them. It answers a question in $$$O(n^2)$$$ time, where $$$n$$$ is the different places that have balls. If we calculate all $$$n$$$ beginning position, we can answer a question in $$$O(\log n)$$$ time.

    Another observation is that if we have $$$n$$$ different positions that have balls, the minimal time is at least $$$n^2/2$$$, so we only need to solve the task for $$$n\le 1000$$$, previous $$$O(n^3)$$$ solution works.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to prove that the last ball collected is the leftmost or rightmost ball ?

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Assume you pick up anything in the middle right now, but you will pass this point atleast once more (when you go from leftmost to rightmost or vice versa), its just optimal to pick it up then.

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

Problems were entertaining; btw when will the upsolving open?

»
9 months ago, # |
  Vote: I like it +41 Vote: I do not like it

Hello!

There is something about JOI rounds that makes me particularly sad, that being the absence of English editorials.

JOI problems are really helpful for people that try to reach high levels, and I am sure that the release of English editorials will make a really big change in something I like to call the "JOI Effect" (positive effect of solving past JOI problems).

I heard the fact that one of the main reasons why the Chinese people are so good is because there are tons of high quality editorials for problems, on websites like Luogu and other Chinese OJ's. As a person that wants the best for future generations, I feel like this thing should also happen with English editorials, as translating an editorial using online services can often times be inaccurate and mislead into a wrong understanding of a solution.

I hope for future English editorials!

Cristofor

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it is a shame that your comment gets downvoted, growing up something i loved about contests and olympiads was that editorials and model solution were written with the actual desire to educate people, but unfortunately i see more and more people approving this mindset of not explaining the approach in a written format.

    even having explanations in comments would be great, they don't have to be official or anything of sorts, i guess community written comments would be just as good too.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Gonna make one for the problems and subtasks I solved, Not the best but it can help anyway.

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

What algorithms are needed to fully get The second problem? I only got the $$$N <= 50$$$ $$$N <= 3000$$$ and using 2 dijkstras.

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

    Then you can do binary search!

    First you need to do 2 dijkstras from $$$T.$$$ and $$$S.$$$ node.

    Then, suppose we went $$$u.$$$ node from $$$S.$$$ node with $$$x$$$ time, we need to go $$$v.$$$ node from $$$T.$$$ node with $$$K - (x + L)$$$.

    (Because we can construct a road between $$$u$$$ and $$$v$$$.)

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      damn, thanks! I thought it had to do with some complex solution because of the subtasks lol.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have some trouble implementing this solution, How can I avoid counting same pair of (u, v) twice?

      For example, if both S and T can reach u and v, and you can build a bridge from (u, v) and (v, u), then pair (u, v) will be count twice.

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 5   Vote: I like it +3 Vote: I do not like it

        You need to do some easy examples:

        Suppose you built a road between $$$u$$$ and $$$v$$$ and your road is $$$S \rightarrow u \rightarrow v \rightarrow T$$$: You went $$$u$$$ from $$$S$$$ within $$$x$$$, went $$$v$$$ from $$$T$$$ within $$$y$$$. And if we went within $$$x + y + L$$$ and $$$x + y + L \le K$$$.

        Suppose you built a road between $$$u$$$ and $$$v$$$ and your road is $$$S \rightarrow v \rightarrow u \rightarrow T$$$: You went $$$u$$$ from $$$T$$$ within $$$a$$$, went $$$v$$$ from $$$S$$$ within $$$b$$$. And if we went within $$$a + b + L$$$ and $$$a + b + L \le K$$$.

        $$$IF$$$ $$$x + y + L \le K$$$

        $$$&$$$ $$$a + b + L \le K$$$

        $$$\rightarrow$$$ $$$x + a \le K$$$ (or $$$y + b \le K$$$)

        And the answer is all edges — $$$n * (n - 1) / 2$$$.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Alright, thank you very much!

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is it true that you solved the problem using a dynamic lazy segment tree?

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

Anyone know how to get 100 pts on problem 4?

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    For a better understanding of my approach, let's represent each person $$$i$$$ as a segment $$$(B_i, A_i)$$$. So now for every query, we need to find out whether there is a permutation $$$p$$$ of left bounds such that all segments will stay valid $$$(B_{p[i]} < A_i)$$$ and all left bounds will change their position $$$(p[i]!= i)$$$.

    The first thing that you have to notice is that you can't rearrange left bounds correctly if there is a segment that doesn't intersect with anyone else. In other words, all positions the segment covers are covered only by that segment. Otherwise, there is a strategy to arrange them. The straight-forward check of that condition takes $$$50$$$ points.

    In order to get $$$100$$$ points, we need to precompute the following for every segment:

    1. $$$lb_i$$$ is the closest segment that intersects with the $$$ith$$$ segment in the array from the left: $$$(lb_i < i)$$$.

    2. $$$rb_i$$$ is the closest segment that intersects with the $$$ith$$$ segment in the array from the right $$$(rb_i > i)$$$.

    Both things can be precomputed by a segment tree with an assignment on segment. To be specific, we iterate from left to right, and for every position $$$x$$$, we maintain $$$tr[x]$$$, the $$$max$$$ index of the segment that covers $$$x$$$ ($$$tr[x] < i)$$$. Than, to find $$$lb_i$$$, we just take $$$max$$$ on the interval $$$[B_i, A_i]$$$ in the seg-tree.

    Finally, both arrays help us respond to the queries offline. Here we iterate from left to right, and on each iteration we respond to queries with the right bound equal to $$$i$$$. To respond to each query quickly, we have to maintain another array $$$f$$$, where $$$f_j$$$ initially points to $$$lb_j$$$, but when $$$rb_j <= i$$$, $$$f_j$$$ becomes $$$+\infty$$$. This structure helps us to respond to each query in $$$O(logn)$$$ as the task is reduced to $$$min$$$ on segment.

    I hope I explained it in enough detail; feel free to ask.

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

How to solve E?

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

    I'm yet to implement it, but probably this will work.

    • Note that the problem is about intervals (for each connected component, only its row sets are interesting)
    • We denote the "local" intervals as the component given in a query and the "global" intervals as the whole component set. I will only solve one queries for the time being.
    • You have to find the subset of points that "stabs" all local intervals (intervals have at least one point from the subset), and they are "connected" by global intervals (sort the subset, for each adjacent one, there exists some global interval that contains both)
    • The above constraint is mostly like $$$p_{i + 1} - p_i \le f(p_i)$$$, since the above two constraint limits how further you can get from the current point.
    • If you do DP on the position, you can solve in $$$O(N^2)$$$ time, and can optimize this to $$$O(N)$$$ time using monotone queues.
    • Let's do DP on the cost instead. For each cost $$$X$$$ compute the rightmost point you can reach with such costs. There is two transitions: Use the rightmost $$$c_i = 1$$$, or the rightmost $$$c_i = 2$$$. Also gives $$$O(N)$$$ time, with simpler DP.
    • Now the queries: If the current DP position is within some local interval, you can just do naively as each transition skips at least one local intervals and you can't skip too much as a whole. So the problem is to pass through global intervals quickly, possibly with some precomputation. Use sparse table: $$$nxt[i][j]$$$ denotes the position you can reach with cost $$$(2^j-1, 2^j)$$$. Transition: $$$(k-1) + (k) \rightarrow (2k-1), (k) + (k-1) \rightarrow (2k-1), (k) + (k) \rightarrow (2k), (k-1) + (2) + (k-1) \rightarrow (2k)$$$. Using this sparse table, pass through global intervals, while being careful to not touch any local intervals within the process.
»
9 months ago, # |
  Vote: I like it +26 Vote: I do not like it

I upsolved everything, including the solution to E, in the way I described above.

code

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

When we can upsolved it ?

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

ojuz Any plans on adding them to your website?

Or is there another place where they are already added with English statements? I saw Atcoder has them but the translation is pretty bad IMO.

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

    We'll try to upload it when Spring Camp materials are available (I just want to do it simultaneously for efficiency, sorry)

    Anyway, you could use https://www.acmicpc.net/category/detail/4176 instead. You can use English UI by clicking "English (Beta)" at the bottom.

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

    You can also download the statements from the website (they are available both in English and Japanese), and submit on AtCoder, if it's the translation that's bugging you.