dario2994's blog

By dario2994, history, 3 years ago, In English

For the sixth time, the Italian national contest (valid for the selection of the Italian IOI team) will be mirrored into an online contest. Everyone is welcome to participate! There are both easy subtasks (div2A) and very hard ones (div1D+), so it can be enjoyable both for newcomers and for very high rated contestants.

  1. The problem statements will be available in both English and Italian.
  2. Tasks will be IOI-like (with graders and subtasks) and you will have 5 hours to solve them.
  3. The only language allowed is C++.
  4. The time window for the practice contest (featuring original problems) will start on 2021 November 13th, 08:00 CET and will end on 2021 November 15th, 23:59 CET.
  5. The time window for the main contest will start on 2021 November 16th, 15:00 CET and will end on 2021 November 17th, 15:00 CET.

The contests' timing will be USACO-like: you can decide when to start your 5-hours time window (after the login), but the contest will end at the given time regardless of your time window.

If you want to participate, you must:

  1. Visit the contest website: https://mirror.oii.olinfo.it
  2. Click the link "register", fill out the form and then click on the register button and then "back to login"
  3. You can now log in with the same username and password you used to sign up
  4. If the login is successful you will be ready to participate, just wait for the contest to start! (And maybe save the page in your bookmarks, so that you can quickly get back to it when the contest begins)
  5. When the contest starts, you will see a red button. Click it when you want to start your 5 hour time window!
  6. Good luck and have fun!

Ranking: The ranking of the online contest will be available at https://mirror.oii.olinfo.it/ranking when the contest starts.

Upsolving: After the end of the contest, tasks will be uploaded in the italian training website (localised also in English), section "task & quiz archive", where they will be available for online evaluation (after registering to the website).

  • Vote: I like it
  • +247
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it +87 Vote: I do not like it

Virtual scavenger hunt: Find the names of the practice problems!

Bonus 1: Translate them into English (or your native language).

Bonus 2: Guess the problems based on the names.

Bonus 3: Solve all the problems ahead of time and AK during the first minute of the practice mirror.

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

    The names of the problems have been leaked, my disappointment is unmeasurable and my day is ruined.

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

    I see that problem 2 is "Allenamento su ChinaForces" which seems to translate to "Training on ChinaForces".

    Expecting either some crazy math problem or horrible constant time speedups.

»
3 years ago, # |
  Vote: I like it +37 Vote: I do not like it

I’m sure davi_bart will win again!

»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Update: Less than 10 hours remaining before the end of the time window for the practice contest.

Remember that at the end of the time window the contest will finish even if your 5 hours have not elapsed, so you shall start the contest before 19:00 CET if you want to have 5 hours.

»
3 years ago, # |
  Vote: I like it +74 Vote: I do not like it

Warning! This post is being bumped. Please don't interfere with the process and upvote.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +46 Vote: I do not like it

    The practice has finished! Congratulations to everyone! You can now discuss the problems.

    Spoiler
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

How can one get those 2 extra points in B?

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it +28 Vote: I do not like it

    For each position, find the nearest smaller element and the nearest larger element on the left and on the right.

    Start from $$$[1, n]$$$, count the subarrays that contain the maximum of the current subarray ($$$a_m$$$), then solve recursively for $$$[l, m-1]$$$ and $$$[m+1, r]$$$.

    If you fix the maximum, and you also fix either the minimum in $$$[x, m]$$$ or the minimum in $$$[m, y]$$$, you can easily count valid subarrays $$$[x, y]$$$ in $$$O(1)$$$. If you always iterate over the minimums in $$$[x, m]$$$, the worst case is $$$O(n^2)$$$: the idea is to choose either $$$[x, m]$$$ or $$$[m, y]$$$ to minimize the "candidate" minimums (that can be found by using the precalculated nearest smaller elements).

    The complexity is $$$O(n)$$$ (it's not trivial to prove). Intuitively, it's much better than the $$$O(n \log n)$$$ with small to large (by iterating over either $$$x$$$ or $$$y$$$, instead of either the minimum on the left or the minimum on the right).

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

      how do you prove that this runs in $$$O(n)$$$

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

        Let's modify slightly the algorithm. Instead of choosing $$$[x, m]$$$ iff the suffix minimums of $$$[l, m]$$$ are less than the prefix minimums of $$$[m, r]$$$, let's choose $$$[x, m]$$$ iff the minimum of $$$[l, r]$$$ is in $$$[m, r]$$$. Moreover, let's do D&C in reverse order (let's process $$$[l, m-1]$$$ and $$$[m+1, r]$$$, then $$$[l, r]$$$.)

        Lemma 1 (quite obvious): in the new algorithm, there aren't in total less candidate minimums than in the previous one.

        Lemma 2: in the new algorithm, each $$$A_i$$$ can be a candidate minimum at most twice (once as a prefix minimum, once as a suffix minimum).

        Proof of Lemma 2: let's assume that the minimum of $$$[l, r]$$$ is in $$$[m, r]$$$ (the other case is symmetric). If $$$A_i$$$ is a suffix minimum of $$$[l, m]$$$, it can't be a suffix minimum of any interval that contains $$$[l, r]$$$. So, $$$A_i$$$ will never be visited anymore as a suffix minimum after processing $$$[l, r]$$$.

        Therefore, both the algorithms visit $$$O(n)$$$ candidate minimums in total.

»
3 years ago, # |
  Vote: I like it +60 Vote: I do not like it

The practice contest has finished, we hope you liked the problems.

In less than 5 hours, the time window of the mirror of the official contest will start.

We invite everyone to take part in the mirror of the official contest. There are both easy subtasks (div2A) and very hard ones (div1D+), so it can be enjoyable both for newcomers and for very high rated contestants.

»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Less than 5 hours remaining to participate in the mirror of the official contest!

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

    Where can we upsolve? The problems for the mirror of the practice contest aren't in the link given above.

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

      Tonight or tomorrow the problems will be uploaded for upsolving and I will make a comment about it.

»
3 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Are the results of the official contest available?

»
3 years ago, # |
Rev. 2   Vote: I like it +60 Vote: I do not like it

Sono felice di questi bei problemi, grazie!

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

    Prego!

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

      How to solve the hardest problem btw? It is scarily similar to D from this year's ICPC world finals, but the exact same solution wouldn't work. I know that for 92 points you can equip yourself with a 2D dp that takes longest odd antipalindrome at each step in the prefix or suffix, and for random sequences you can get away with cutting independently from front and back until the size is <= 1000.

      But how to get the remaining 8 points is a mystery to me...

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

        Yes, we knew about the similarity in the statement with ICPC-WF2021-D, but the solution is completely orthogonal (this one is much harder in fact).

        I will quickly describe a subquadratic solution (with complexity $$$O(n^{2-10^{-20}})$$$, that is to say that the complexity estimate is not good) which performs fast enough (it solves instances with $$$n=100\,000$$$ within the time limit, and it is not optimized at all). The general idea is similar to the one you outlined to tackle the random case, but much more ideas are required (and it is much harder to implement).

        A prefix move is a move on an odd antipalindrome prefix, a maximal prefix move is the prefix move on the longest antipalindrome prefix. The definitions are analogous for suffix moves.

        Observation 1: The optimal solution performs only maximal prefix or suffix moves.

        This observation is crucial also to get the quadratic subtask.

        Observation 2: The total size of maximal antipalindrome substrings is $$$O(n\log(n))$$$.

        This observation is necessary to perform some of the operation described below in pseudolinear time.

        Description of the solution: Let us iterate on the number of initial suffix moves performed by the optimal solution.

        After executing the suffix moves, we remain with $$$s[0, r]$$$. Let $$$r'$$$ be the center of the maximal antipalindrome suffix of $$$s[0,r]$$$. We may assume that the optimal solution now performs prefix moves until it performs a prefix move on a substring intersecting $$$[r', r]$$$ (otherwise it was convenient to perform one more initial suffix move).

        Then, we recur on the subproblem $$$s[l, r]$$$ which remains after performing the described amount of prefix moves. One can show that the total size of the problems we recur at depth $$$1$$$ is bounded by $$$2n$$$ and that all subproblems have size bounded by $$$\frac34 n$$$.

        What I have explained is really hard to implement in pseudolinear time (i.e., finding all the substrings one needs to recur on) but is possible.

        If we reach a substring with size $$$<L$$$, we change approach and we use the quadratic algorithm to solve the problem with complexity $$$O(nL)$$$ for all short substrings. Choosing $$$L$$$ appropriately yields a subquadratic algorithm and, more importantly, choosing $$$L\approx 200$$$ is sufficient to solve the problem.

        Final remark: I have been very concise. If we ever write down the editorial for the problems in english (rather unlikely) I will link it here.

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

          Thanks for the description. Amazing problem. Can you link the editorial in Italian?

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

            Currently it does not exist. If it will be written (which is likely to happen soon) I will link it here.

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

          What I have explained is really hard to implement in pseudolinear time (i.e., finding all the substrings one needs to recur on) but is possible.

          I wonder how can we find them quickly. Now I only have a stupid brute force method which can't fit TL if the testcase has much 000000... or 111111....

          It confused me a lot. Could you give me some hints?

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

            I will give an overview, without entering into details.

            Step 1: Assume that you can perform only maximal suffix moves. Find the sequence $$$r_0=n-1>r_1>r_2>\cdots>r_h=0$$$ such that if we apply the "only maximal suffix moves" algorithm we visit the substrings

            $$$ [0, n]\to [0, r_1]\to [0, r_2] \to \cdots \to [0, 0].$$$

            This is not hard to do in pseudolinear time if one has precomputed, for each position $$$p$$$, the longest antipalindrome with center at $$$p$$$.

            Step 2: For each $$$0\le r\le n-1$$$, assume that you can perform only maximal prefix moves on $$$[0, r]$$$. Find the sequence $$$0=l_0 < l_1 < \cdots < l_{k-1}=r$$$ such that if we apply the "only maximal prefix moves" algorithm we visit the substrings

            $$$ [0,r] \to [l_1, r]\to [l_2,r] \to \cdots [l_{k-1}, r]. $$$

            This is the hard part. In order to perform this in subquadratic time, one needs to keep the values $$$l_0<l_1<\dots<l_{k-1}$$$ in a set and to analyze in detail how they change when $$$r$$$ is incremented.

            Step 3: Assume that, when you perform $$$b$$$ suffix moves (remaining with the substring $$$[0, r]$$$), the sequence of maximal prefix moves to erase $$$[0,r]$$$ is given by $$$l_0, l_1, \dots, l_{k-1}$$$. The issue is that we do not have to perform all those prefix moves, but we have to stop as soon as one of the prefix moves intersect $$$[r',r]$$$ (as discussed in my previous comment). It turns out that one can keep a pointer to the first prefix move with such property and update it properly when updating the data-structure containing the values $$$l_0, l_1,\dots, l_{k-1}$$$ (which is the point of Step 2). This part is not hard if one has a clean idea of what to do in Step 2.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +24 Vote: I do not like it

    "Compiti" is closer to "homework" / "assignments" than to "tasks". We usually just say "problemi".

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

Thank you very much for taking parts in the mirror contest, we hope you liked the problems.

Here are the links to upsolve the problems:

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Thanks for the nice problems, I just managed to solve A and D, but thinking on B and C was enjoyable a lot :)

Also if there is anyone having problem with getting the idea of D (smaltimento), I think solving these two easier problems first would help, the procedure of solving these and smaltimento are kind of similar :

1-1407E - Egor in the Republic of Dagestan

2-346D - Robot Control

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

Is there a way I can view my submission?Thanks.

»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Bonus for armadio: find the sum of the answers for $$$1 \leq i \leq n$$$ ($$$n \leq 10^9$$$).