Hello, Fastest editorial of 2022 :)

I hate problem B

problems are good but im noob lol Happy new year!

Problem D was nice

How excellent the problem B is！

Can anyone help me with B ?

Small typo on tutorial for problem E : It can be easy done with prefix sum arrays. --> It can be easily done with prefix sum arrays.

Is there any chance you could include the model solutions for our reference? Links to submissions would suffice. Thanks

I'm curious how you found the solution for problem D? For me, I tried to analyze the problem but got nothing. But since I saw so many people pass this problem, I started to guess some random strategies and verify them manually. But this doesn't seem plausible, so I'm curious if there's some more plausible way to get the solution?

For problem E, how do you compare averages : convert them to doubles or convert them to fractions (p and q) ?

In this contest, (and the previous one) I knew the solution (as far as it is covered by the editorial) to problem C after like ten minutes. And then was not able to implement it until end of contest.

Now, the question is, isn't that implementation part the interesting one (at least in such problem), the one that should be covered by the editorial?

I mean, this observation that there are cycles in a permutation is fairly trivial. I don't think that like 20k partitipants did not solved it because they did not had that idea.

Could you tell me what's wrong in my solution for task B? 141567260

I tried to maintain 5 values: the leftmost number, cost of optimal line containing it, the rightmost number and cost of optimal line containing it, and the flag — are these lines same.

tourist's solution to E is so genius, even cleaner than the editorial.

Just throw everything into a segtree then forget about casework.

In problem D, it took me about 30 minutes just to prove the following case doesn't exist

:(

Could you PLEASE show the solution(code) for B? Have been trying to solve it for hours...

Video Tutorial B:https://www.youtube.com/watch?v=D4Jmm1Q9rF0

Can anybody show the solution for problem a in java? I don't know why mine is wrong. I used prettt much the same logic in the editorial

I literally got the exact solution described in the editorial for B and got WA on 2. What was B?

Can someone point out my mistake on B? 141546457

I liked C — interactive problems without binary search have become extinct nowadays. My solution is very short and the problem involved reasonable amount of thinking.

On the other side, D is not a great problem. I couldn't come up with the solution during the contest (or, to be correct, I came up with it, but it seemed to me totally wrong). However, the problem is ad-hoc and it is not very beautiful.

E was merely an implementation task. I think it's rather good problem. The detail about $$$m \le n$$$ (not $$$m = n$$$) was unexpected and confusing, though.

How do you calculate the number of increasing subsequences that starts in $$$a_i$$$ and ends in $$$a_{x_{y'}}$$$ in G? For me, it was the most difficult thing in it. Am I missing something? We have $$$O(n)$$$ different start points ($$$a_i$$$) and also $$$O(n)$$$ different end points ($$$a_{x_{y'}}$$$) and how we calculate all the numbers fast?

Alternative solution for 1621E - New School

If you fix the student to remove, you can check if the answer is 1 with the following algorithm:

• Keep a multiset of teachers, for each group of students assign them the teacher with the minimum value $$$\geq$$$ to the average of the group and remove the teacher from the multiset. The answer is 1 if there is always an available teacher.

The key observation is that the algorithm works for any order of the groups of students. So, if you want to check the answer for all the students of a group, you can insert the other groups first, then try to remove each student from that group.

Now, we want to solve this problem:

• For each group, find the result of the algorithm if you consider all the groups except that one.

This can be solved in $$$O(n \log^2 n)$$$ with D&C (similar to offline deletion). The D&C looks like

solve(l, r) { // for each i in [l, r], find answer if you remove group i
    if (l == r) { // you've inserted all groups except l, so you can check students of group l
        check(l); return;
    }
    m = (l + r) / 2;
    insert(m + 1, r); // assign a teacher to groups in [m + 1, r]
    solve(l, m);
    rollback(m + 1, r); // undo the assignments
    insert(l, m);
    solve(m + 1, r);
    rollback(l, m);
} 

Implementation: 141541065

Is the answer to the bonus part of A: $$$\binom{n-k+1}{k}^2$$$ ?

Basically, there are $$$\binom{n-k+1}{k}$$$ ways to choose the rows containing a rook, and $$$\binom{n-k+1}{k}$$$ ways to choose the columns containing a rook, independently, such that the arrangement is stable.

Problem B goes to show many people are brick at implementation.

In Problem C, is there any specific theorem of any kind or its just based on observation??

I undertand it, pass me!

why Problem D can't acts like the following e.g

for simplify e.g, set i = 10e9

4
0 0 0 0 i i i i
0 0 0 0 i i i i
0 0 0 0 i i i i
0 0 0 0 i i i i
i i i i 2 0 2 2
i i i i 1 6 2 1
i i 3 4 2 4 7 4
i i 2 i 2 0 1 6

in this case, I think friends can move by (8, 3) -> (7, 3) -> (7, 4)

did I ignore something?

B was a hell

Why does solution to E work in time?

We check the removal of each of the 1e5 students. Foreach one its group will move some positions (i to j). We recheck all groups in range (i,j). i,j is not bounded, the dist can be also 1e5.

So how is this not O(n^2)?

Here's a more complex but IMO more intuitive solution to E, which I believe was used by a lot of other participants in contest.

It's possible to assign teachers to groups if for every value v, there are more or equal teachers of age at least v compared to groups with average age of at least v. It's easy to see that this is equivalent to the original condition.

Let diff[i] be the (number of teachers with age >= v — number of groups with average age >= v). Then, the condition means for all i = 1...1e5, diff[i] >= 0, or min(diff[i]) for all i = 1...1e5 >= 0.

It's easy to see adding a teacher of age v will add diff[v], diff[v + 1], ..., diff[1e5] by 1, and a group with their rounded up average v will reduce diff[v], diff[v + 1], ..., diff[1e5] by -1. With this, the problem becomes a straightforward lazy segment tree problem: we add all teachers, then add all groups, when we remove a member of a group we temporarily change it's average, and then change it back. All in all, it uses about n + 4 * m segment tree operations, which is far fast enough to AC.

Video Editorial for Problem B: Integers Shop

I use 3 pair data structures, instead of 6 variables as mentioned in the editorial, in order to reduce the length of the code and make it easier to understand.

You can do problem I in $$$O(n \log \log n)$$$ time (linear time per op)! Code: 141611373

We need 3 additional observations. First, we rephrase the copy operation into something a little simpler. Then, we complete the analysis of part 3 of the editorial to find a closed form for whether the the smallest subarray starts at $$$c_l$$$ or $$$c_k$$$. Finally, we show a linear time algorithm for finding the lexicographically smallest suffix of each prefix based on Duval's algorithm for Lyndon factorization.

The copy operation

First, let's rephrase the copy operation. If, in the $$$i$$$th operation, we find the smallest substring of length at least $$$i$$$ starts at index $$$j \le n-i$$$, then $$$D_{i} = (D_{i-1}[1:n-i] + D_{i-1}[j:n])[1:n] = (D_{i-1}[1:n-i] + D_{i-1}[j:n-i] + D_{i-1}[n-i+1:n])[1:n]$$$ (here, we use inclusive substrings). In other words, we insert the string $$$D_{i-1}[j:n-i]$$$ (which is a possibly-empty suffix of $$$D_{i-1}[1:n-i]$$$) directly after the $$$n-i$$$th character, and then we truncate the result to the first $$$n$$$ characters. Then, there are a few useful observations:

• Picking the smallest substring is equivalent to picking the possibly-empty suffix $$$D_{i-1}[j:n-i]$$$ of $$$D_{i-1}[1:n-i]$$$ (with $$$j \le n-i$$$) that minimizes the result $$$D_{i-1}[j:n-i] + D_{i-1}[n-i+1:n]$$$. Furthermore, note that $$$D_{i-1}[1:n-i]$$$ has not been modified before this step, so this is equivalent to $$$D_0[1:n-i]$$$.
• With this definition, it's easy to see that we don't actually need to truncate the $$$D_i$$$ to the first $$$n$$$ characters; it's fine to let them grow.
• We can reindex slightly so that $$$D_i = D_{i-1}[1:n-i] + D_{i-1}[j:n-i+1] + D_{i-1}[n-i+2:n]$$$. In this formulation, we need to pick a nonempty suffix $$$D_{i-1}[j:n-i+1]$$$ of $$$D_{i-1}[1:n-i+1]$$$ to replace $$$D_{i-1}[n-i+1]$$$ so the result is minimized. Once again, $$$D_{i-1}[1:n-i+1] = D_0[1:n-i+1]$$$.

From here on, let $$$A_i$$$ denote the suffix of $$$D_0[1:n-i]$$$ we inserted in the $$$i$$$th step, and let $$$B_i$$$ denote the suffix of $$$D_0[1:n-i+1]$$$ which we substituted for $$$D_{i-1}[n-i+1]$$$, so that $$$B_i = A_i + D_0[n-i+1]$$$. Part 3 of the editorial showed that $$$B_i$$$ is either the minimum suffix of $$$D_0[1:n-i+1]$$$, of it's the maximum number of copies of the minimum suffix. We make a few more observations:

• Because of the replacement scheme, our final result is $$$D_n = (B_n + B_{n-1} + \cdots + B_2 + B_1)[1:n]$$$. Thus, it suffices to find the $$$B_i$$$.
• We can consider 2 consecutive steps at once with our 2 indexing ways: $$$D_{i+1} = D_{i-1}[1:n-i] + B_{i+1} + A_{i} + D_{i-1}[n-i+1:n]$$$, where $$$A_{i}$$$ is a possibly empty suffix of $$$D_0[1:n-i]$$$ and $$$B_{i+1}$$$ is a nonempty suffix of $$$D_0[1:n-i]$$$ chosen to minimize the result $$$B_{i+1}+A_{i}+D_{i-1}[n-i+1:n]$$$. This is convenient because $$$B_{i+1}$$$ and $$$A_{i}$$$ are both (almost) minimal suffixes of the same string!

Closed form for which suffix

Now, using the last observation, we can classify whether $$$B_{i+1}$$$ starts at $$$c_l$$$ (the minimum suffix of $$$D_0[1:n-i]$$$) versus $$$c_k$$$ (the maximum number of copies of the minimum suffix of $$$D_0[1:n-i]$$$): $$$B_{i+1}$$$ starts at $$$c_l$$$ if $$$A_i$$$ is empty, and $$$c_k$$$ otherwise. Note that $$$A_i$$$ is empty iff $$$B_i$$$ has length $$$1$$$.

The proof of this is pretty similar to the analysis in part 3 of the editorial. Let $$$S$$$ be the minimum suffix of $$$D_0[1:n-i]$$$, and let $$$E = D_{i-1}[n-i+1:n]$$$. Then, either $$$A_i$$$ is empty, or $$$A_i$$$ starts with $$$S$$$, and $$$B_{i+1} = S$$$ or $$$B_{i+1} = S^l$$$ for some $$$l$$$ (this denotes $$$S$$$ repeated $$$l$$$ times). Then, note that $$$A_i + E < S + A_i + E$$$ iff $$$S + A_i + E < S^2 + A_i + E$$$ iff $$$S^2 + A_i + E < S^3 + A_i + E$$$ and so on, so we should take $$$B_{i+1} = S$$$ iff $$$S + A_i + E < S^l + A_i + E$$$ iff $$$A_i + E < S + A_i + E$$$.

Now, because $$$A_i$$$ is optimal on the $$$i$$$th step, we must have $$$A_i + E < P + E$$$ for any other prefix $$$P$$$ of $$$D_0[1:n-i]$$$. In particular, if $$$A_i$$$ is empty, then $$$A_i + E < S + E = S + A_i + E$$$, so we should take $$$B_{i+1} = S$$$. Otherwise, $$$A_i$$$ starts with $$$S$$$, so $$$A_i + E < A_i[len(S)+1:] + E \implies S + A_i + E < A_i + E$$$, so we should take $$$B_{i+1}=S^l$$$.

Thus, we've proven that $$$B_{i+1}$$$ is the minimum suffix exactly when $$$B_{i}$$$ has length $$$1$$$.

Fast algorithm for min suffix

Finally, we sketch a linear time algorithm to find the minimum suffix of each prefix of $$$D_0$$$ (and the max number of copies).

Note that the minimum suffix of a string $$$S$$$ is exactly the final Lyndon word in the Lyndon factorization of $$$S$$$. Furthermore, the maximum number of copies is the number of equal Lyndon words at the end of the factorization of $$$S$$$. (This is pretty trivial/uninteresting statement, but it's useful terminology/framing.)

We can find both using an algorithm similar to Duval's algorithm for Lyndon factorization (emaxx writeup), which is itself similar to KMP. I'll refer to terms from the writeup, so please read that first. In essence, we build the KMP failure function to compare the string to its suffixes, but if the suffix is smaller than the whole string, then the suffix is part of a later Lyndon word, so we can cut off and output some prefixes as a maximal Lyndon word.

In this case, we need to modify it slightly. Duval's algorithm is already almost online, so we're pretty close being able to find the Lyndon factorization of every prefix. First, we'll modify it to be a little more online and less amortized: in the case where our next character is small and we want to cut a pre-simple string $$$ww\ldots w\overline{w}$$$ down to $$$\overline{w}$$$, the algorithm typically resets the state all the way back to an empty string and reprocesses $$$\overline{w}$$$. Instead, note that $$$\overline{w}$$$ is a prefix of $$$w$$$, so we can just store our current pre-simple string in a stack and pop all the way down to $$$\overline{w}$$$. (This adds linear memory, which is why it's probably not used in normal Duval's).

Now, to find the "tail" of the Lyndon factorization of a prefix, we need to process up to that prefix, and then append a terminator with value $$$-\infty$$$. Note that this will cause a series of cuts from $$$ww\ldots w\overline{w}$$$ to $$$\overline{w}$$$, each of which jumps back to some smaller stack size. The last cut we do is the tail of identical strings in the Lyndon factorization. Thus, we can just precompute the final cut starting at each location: it's just the final cut of the location you would jump to.

Thus, we have a linear time algorithm for finding all minimum suffixes of each prefix of $$$D_0$$$.

I think that Problem E has a serious problem: Nobody has the age of 1e5

can someone please explain problem 'c' in detail i am unable go through the editorial ?

are there are any prerequisite for that question ?

Hi everyone, can anyone provide me a edge case for my code for problem C? CODE Thank You.
My implementation has same logic as the editorial has but I'm not able to find why I'm failing at test 2 subtest 34.

If you are looking for video solutions, HERE they are(for A-D)

what is wrong in this implementation for problem B. I tried to implement the same logic as is given in the editorial but could not get it right?

void solve() {

int n;
cin >> n;

pair<int, int> arr[n];
int cost[n];

for (int i = 0; i < n; i++)
{
    cin >> arr[i].first >> arr[i].second >> cost[i];
}

int mi = 0, ma = 0, len = 0, costlen = 1e9 + 1;
// mi for min index.
// ma for max index.
// len for max length.
// costlen for cost of max length.
cout << cost[0] << endl;

for (int i = 1; i < n; i++)
{
    if (arr[i].first < arr[mi].first)
    {
        mi = i;
    }
    if (arr[i].second > arr[ma].second)
    {
        ma = i;
    }
    if (arr[i].first == arr[mi].first && cost[i] < cost[mi])
    {
        mi = i;
    }
    if (arr[i].second == arr[ma].second && cost[i] < cost[ma])
    {
        ma = i;
    }
    if (len < arr[i].second - arr[i].first + 1)
    {
        len = arr[i].second - arr[i].first + 1;
        costlen = 1e9 + 1;
    }
    if (len == arr[i].second - arr[i].first + 1)
    {
        costlen = min(costlen, cost[i]);
    }

    if (len == arr[ma].second - arr[mi].first + 1)
    {
        cout << min(cost[mi] + cost[ma], costlen) << endl;
    }
    else
        cout << cost[mi] + cost[ma] << endl;
}

}

int main() { int t = 1; cin >> t; while (t--) solve(); }

Here's another (more systematic) way to arrive at what you want to compute in G.

Let $$$X_i$$$ be the indicator variable such that $$$X_i = 1$$$ if and only if $$$i$$$ (by index) is included in an increasing sequence and there exists $$$x$$$ such that $$$a_x > a_i$$$ and $$$x$$$ is past the end of the sequence. If $$$tot$$$ is the number of total increasing sequences of the array, we are interested in computing $$$tot \cdot E[X_1 + \cdots + X_n]$$$ by definition.

Let's focus on the $$$E$$$ term. By linearity, this collapses to $$$E[X_1] + \cdots + E[X_n]$$$. Note since $$$X_i$$$ are all indicator variables, $$$E[X_i] = P(X_i)$$$.

Let $$$lst_i$$$ be the largest index such that $$$a_{lst_i} > a_i$$$ (similar to editorial). Then,

If $ $$$tot_i$$$ denotes the total number of sequences including $$$a_i$$$, and $$$tot_{il}$$$ is the number of sequences including $$$i$$$ and $$$lst_i$$$ then this value is just

Proceed as mentioned in the editorial to find $ $$$tot_i$$$ and $$$tot_{il}$$$, and don't forget to multiply the entire sum by $$$tot$$$.

Here's my implementation (a bit messy).

This idea of assigning indicator variables to compute what we want works on a lot of mathy problems like these, especially on AtCoder. Also, excuse the wonky latex (was being annoying when typing this up).

The proof in $$$D$$$ may not be convincing much as we still can move the columns $$$[1, N]$$$ one by one through the $$$2^{nd}$$$ column for example. Although will not be able to complete the solution, this does not pass through the mentioned $$$8$$$ points in the first operations.

Another proof that we must always pass by at least one of the mentioned $$$8$$$ points:

For the points $$$(n+1, n+1)$$$, $$$(n+1, 2n)$$$, $$$(2n, n+1)$$$, and $$$(2n, 2n)$$$ to be filled, they have to be filled from the bottom-right corner itself, as any filling from the other $$$3$$$ corners would pass through one of the mentioned $$$8$$$ points. Now let's try to fill one of the $$$4$$$ points, we will notice that any shifting in the bottom-right corner to fill one of those $$$4$$$ points will result in emptying another one of them, and this will just go indefinitely.

EDIT: It seems that the editorial's proof is complete as well. We can never make a first move with a row/column having one of the $$$4$$$ points $$$(1, 1)$$$, $$$(1, n)$$$, $$$(n, 1)$$$, or $$$(n, n)$$$ without moving another one of them to one of the $$$8$$$ mentioned points.

Can anybody please tell me what's wrong with my solution for problem C? :( code-attempt-wa-testcase2

Can anybody help me to find out where my solution to B (using ordered set) is failing in test 2? I tried many random generated small test cases with correct output. Didn't able to find any failure test case. :( https://codeforces.com/contest/1621/submission/141576936

Can someone please help me figure out a test case on which my code will fail for problem B. 141637071

Some hints for people stuck at debugging problems B and C (as per the comments above).

avkonyahin

1
3
1 1 1
2 3 1
1 3 1

1
2
1

1
2
2

practice_52

1
3
2 3 2
1 3 3
1 2 2

2
3
3

2
3
4

pks18

1
3
1 1 2
2 3 3
1 3 3

2
5
3

2
5
5

Abhishek357

1
3
1 1 2
2 3 3
1 3 3

2
5
3

2
5
5

Mysticode

1
3
1 2 1
1 3 3
2 3 1

1
3
2

1
3
3

_s_h_n_

1
3
2 3 2
1 3 3
1 2 2

2
3
3

2
3
4

AnestheticCoder

1
2
1 2 1
1 2 2

1
1

1
2

Blinding_Lights

Alternative solution to G:

If $$$a_{x}$$$ affects the weight of a subsequence $$$a_{i_1},...,a_{i_k}$$$, then this subsequence doesn't maximize the value of $$$i_{k}$$$ across all increasing subsequence containing $$$a_{x}$$$. We can also see that the latter implies the former.

So if we can count the number of increasing subsequence starting in $$$a_i$$$ and maximize the position of the rightmost element, we can solve the problem. It turns out that it is possible in $$$O(n log n)$$$ using segment tree.

Implementation

Could you please tell me, why my code for problem B (Integer Shop) is wrong. Here is the implementation 141707198

Thanks in advance!!

[Edit: Resolved]

I have an interesting idea in problem C:

When the change $$$q_{i}'=q_{p_i}$$$ turn into $$$q_i'=q_{q_i}$$$ ,How to solve the problem?

PS: It's also the mistake I made in the contest

Hi — I'm pretty sure I have a solution to problem E but i'm not sure it works, and I do not want to implement it right now. Maybe someone could read the following and comment.

After sorting as in the editorial (in decreasing order), we first check if before removing anyone, it's possible to start lessons.

• If yes, the only way to make the lessons not possible is to remove a student with a lower value than the average of his group, which will make the average larger and move that group to the left in the sorted array. Then either that group itself is larger than teacher, or one of the shifted (shifted to the right) groups are larger than the corresponding teacher. Since each group can only move 1 index to the right, we will denote an index as bad if when moved one to the right, it will be bigger than the teacher. Suppose I remove a student and group is moved from index 9 to index 3, the only question is — is there a bad index between 3 and 8? And that's a very easy thing to answer, all you have to do is save the closest bad index to the left of each index. if the closest bad index to 9 is for example 7, then we know there is a bad index between 3 and 8. If the closest bad index to the left is 2, we know there isn't.

• If no, it's simpler. Look at the set of all indices violating the conditions of being smaller than their teacher. If there is an index in the set such that moving it to the left doesn't fix the condition, it's never possible. Assuming that moving each of them one index to the left fixes the condition, the only way to make the lessons possible, is to move the entire set of these indices one index to the left. Note it's enough to look at the min and max of that set. Say the set includes 3,6,8,11. Then you just need to make sure to move the segment [3,11] to the left, and you fixed the condition (assuming of course that the moved group doesn't ruin it itself). So you just have to go over the groups 0,1,2 (i.e. the ones less than the minimum in the set), and see if removing a student moves the group to an index >= 11.

Of course some details are missing, but that's pretty much it. Thinking about it — it might've been faster coding it than describing it ^_^.

Thanks for the editorial mate :)

A bonus harder version of problem F: Solve if no two consecutive operations can have same type (instead of same parity, so types 1 and 3 can be consecutive).

Additional restriction on binary string s will be that the first and last characters must be one.

This can also be solved with a similar solution to the intended one, but with slightly more casework.