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.

- The
**problem statements**will be available in both**English and Italian**. - Tasks will be
**IOI-like**(with graders and subtasks) and you will have**5 hours**to solve them. - The only language allowed is
**C++**. - 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. - 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:

- Visit the contest website: https://mirror.oii.olinfo.it
- Click the link "register", fill out the form and then click on the register button and then "back to login"
- You can now log in with the same username and password you used to sign up
- 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)
- When the contest starts, you will see a red button. Click it when you want to start your 5 hour time window!
- 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).

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.The names of the problems have been leaked, my disappointment is unmeasurable and my day is ruined.

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.

Picture from the statementI’m sure davi_bart will win again!

Thanks, but I think Virv will get first place this year!

Thanks, but I believe TheScrasse is going to win!

Nah, I will continue my Fibonacci streak (21st place -> 13th place -> 8th place).

rocks03 will win.

Idk i don't trust orange plebs

i'm sure taulant will win! GL to everyone!

Mmmmh... Imo lorenzoferrari has more chances. Btw i can't wait to see the problems!!

I think lorenzoferrari will AK in less than 4 hours

Once a wise man said that

"weak testcases are our strength"... I'll lamer my best, but still believe franfill is going to winbruh I'm too old to participate; I think the winner will be either Virv or davi_bart, and I really hope that lolcat will win a gold medal ❤️.

glhf lolcat ❤️

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.

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

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

SpoilerIs this just a pretext to bump the blog?

How can one get those 2 extra points in B?

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).

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

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.

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.

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

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

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

Are the results of the official contest available?

Provisional top 10:

1) Davide Bartoli (davi_bart) — 392

1) Filippo Casarin (Virv) — 392

3) Valerio Stancanelli (TheScrasse) — 369

4) Francesco Cerroni (ErCierony) — 342

4) Franceso Lugli (franfill) — 342

6) Lorenzo Ferrari (lorenzoferrari) — 293

7) Carlo Collodel (collodel) — 239

8) Laura Acinapura (aci) — 211

9) Nicolas Albani — 200

10) Massimiliano Foschi (MassimilianoF) — 180

Sono felice di questi bei problemi, grazie!

Prego!

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...

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 onlymaximalprefix 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 beenveryconcise. If we ever write down the editorial for the problems in english (rather unlikely) I will link it here.Thanks for the description. Amazing problem. Can you link the editorial in Italian?

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

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?

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 substringsThis 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 substringsThis 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 ofStep 2). This part is not hard if one has a clean idea of what to do inStep 2."Compiti" is closer to "homework" / "assignments" than to "tasks". We usually just say "problemi".

Thanks, fixed :)

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:

Thank you very much for the updates. Don't forget to make the mirror contest problems available for upsolving too.

How about the practice problems?

They are also available on the same training website:

Please put the author :D

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

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

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