E869120's blog

JOI 2024/2025 Final Round Online Contest
By E869120, 6 weeks ago, In English

Hello, everyone!

The 24th Japanese Olympiad in Informatics (JOI 2024/2025) Final Round will be held from Sunday, February 02th, 10:00 UTC to Monday, February 03th, 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 03th, 10:00 UTC, if you start the contest after Monday, February 03th, 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 12 hours.
UPD2: The contest is started.
UPD3: The contest is ended. Thank you for your participation.

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

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

bump

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

How to solve the

$$$1, 1, \dots , n - 1$$$

case in P5?

My solution for the 12 points was some simulation. In each moment of time, I move the package at the post office which is furthest from its destination. My intuition for this was that it would maximize the number of simultaneous movements that happen, but I can't prove it formally lol

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

    The proof of your claim is also pretty intuitive. Notice that when two packages meet, they will follow the same path until one of them reaches its destination. If we decide to let the one that has a shorter path go first, then the other one will still have at least 2 edges to pass through after the first one arrives at its destination.

    From that greedy solution, we can make another claim: for an edge, the last time some package passes through it is only dependent on the distances of packages passing through this edge.

    The intuition here is that all the edges before will "sort" those packages the same way as the current edge will. Packages that end before that edge will have a lower priority than all the other ones, so they won't change the order in which packages come to this edge.

    To calculate the answer on each edge, we can store the distances on a segment tree. If you handle distance offsets well, the cycle becomes a simple sweepline. Tree parts of the graph work similarly but require small-to-large merging of those segment trees.

    → Reply
»
6 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Where can I find the editorials?

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

How to solve P4

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can get 46pts using bitmask dp.

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

      Can you elaborate? Maybe implementation?

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

        Note that it can always be done with 21 ties, even if we don't ignore any of the audience numbers: assign each tie to one of 1, 2, ..., 21, and for each audience number, only make moves to the tie we assign to that number.

        Then, for each index $$$i$$$ in the numbers $$$A_i$$$ called out by the audience, we can figure out the possible sets of all lengths of ties after that number is called. The answer, then, is after $$$A_n$$$ is called out, the set with the least number of 1 bits. This will take $$$2^{\max A_i}$$$ for each index, for a complexity of $$$O(2^{\max A_i} \cdot n)$$$.

        → Reply
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +7 Vote: I do not like it
        Definition of the dp
        Base Case
        Calculating dp
        Final answer
        → Reply
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          To optimize this, note the for each mask, only the largest $$$n$$$ that $$$dp(n,mask)=1$$$ is important, so record $$$f(mask)$$$ as the largest $$$n$$$, and you can do the transition in $$$O(na+2^aa^2)$$$.

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

            $$$f(mask)=max f(new mask)$$$

            Now let's say $$$n = f(mask)$$$

            if $$$a[n + 2]$$$ is in $$$mask$$$, $$$f(mask) += 2$$$

            if $$$a[n + 1]$$$ is in $$$mask$$$, $$$f(mask) += 1$$$

            And we repeat until one of them holds.

            How this is it most $$$O(na)?$$$

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

              record $$$next_1(p,x)=$$$ minimum $$$p'>p$$$ that $$$a_{p'}=x$$$, and $$$next_2(p,x)=$$$ minimum $$$p'\geq p$$$ that $$$a_{p'}=a_p$$$ and $$$a_{p'+1}=x$$$.

              → Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

.

→ Reply
»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Where can I upsolve?

→ Reply
»
5 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

My code (joi25*.cpp)

→ Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Are test data and standard programs available?

→ Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Could you explain your solutions for problems even for 1-st problem?

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it 
    using 0-based indexing.
Let c = a + b[1:] (excluding the first index)
sort c.


We have got recursion, g[i][j] = max(g[i][j-1],g[i-1][j]) where i>0 and j>0, if we look at carefully,

a[0] b[1] b[2] .. 
a[1] max(a1,b1)  max(max(a1,b1),b2)
a[2] max(max(a1,b1),a2)  max(max(a1,b1),max(a2,b2))

We can observe that g[i][j] = max ( max(a[1],a[2],..,a[i]) , max(b[1],b[2],..,b[j])) for i>0 and j>0.
if we compute prea[i]=max(a[1],a[2],..,a[i]) and preb[j] = max(b[1],b[2],..,b[j]) then g[i][j]=max(prea[i],preb[j]) for i>0 and j>0.

f(x) = number of (i,j) such that g[i][j]<=x.
computing f(x) is very easy by using prea and preb, just binary search the maximum index of prea and preb with value <=x , let it be cnt1,cnt2 then the answer is cnt1 + cnt2 + values in c <=x.
now for each value x in c get cnt by f(x)-f(x-1) and print maximum count and the maximum value with the count.

Time: O(n*lg(n))
    → Reply
»
5 weeks ago, # |
  Vote: I like it +47 Vote: I do not like it

For problem D, I wrote a brute force bitmask dp ($$$O(n2^a)$$$), and deleted all states that will not contribute to the answer. That is to say, if there are two states $$$S_1,S_2$$$ with the same number of $$$1$$$, and for every $$$k$$$, the $$$k-$$$th highest $$$1$$$ of $$$S_1$$$ is always not smaller than $$$S_2$$$, then we can delete $$$S_2$$$. The check was simply brute force, so the complexity is $$$O(nk^2a)$$$ where $$$k$$$ is the maximum number of states at a single position. However, it passed all the tests with a maximum time of only 1 second. Can anyone prove that the number of states is small or give a hack to this solution?

→ Reply
»
5 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Will there be analysis mode?

→ Reply