IgorI's blog

By IgorI, history, 2 years ago, In English

Thank you for participation! Here is the editorial:

1621A - Stable Arrangement of Rooks

Editorial
Solution

1621B - Integers Shop

Editorial

1621C - Hidden Permutations

Editorial
Solution

1621D - The Winter Hike

Editorial
Solution

1621E - New School

Editorial
Solution

1621F - Strange Instructions

Editorial
Solution

1621G - Weighted Increasing Subsequences

Editorial
Solution

1621H - Trains and Airplanes

Editorial

1621I - Two Sequences

Editorial
Solution
Tutorial of Hello 2022
  • Vote: I like it
  • +104
  • Vote: I do not like it

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

Hello, Fastest editorial of 2022 :)

»
2 years ago, # |
  Vote: I like it +36 Vote: I do not like it

I hate problem B

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

    I hate test case 1

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

    Only B?

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

      After trying to solve it for 1.5 hours and submitting 5 almost correct solutions. I didn't had time to try any other problem.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it -18 Vote: I do not like it

        sounds like a you problem.

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

          I don't think I ever said it's -is-this-fft-'s problem or writer's problem. I know it's my problem that I'm not good enough but that being said my comment was simply his reply to why the OP only disliked B (like me). So, I replied and I don't think my original comment in any way says it's anyone else's problem.

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

    I do not understand at all what is wrong with problem B. After reading the reviews, I sat down and solved this problem in contest mode. She's great! There's a simple greedy idea in there. It is not another math puzzle. There is a place for a little coding in it.

    If you have difficulties with its implementation, it rather means that you need to write more code. I'm afraid this is one of the basic skills that you can learn from CP: to accurately and quickly implement simple logic. Do this in such a way as to minimize the number of special cases.

    The only minus of the problem is that it is a bit difficult for position B.

    I was lucky to solve it in without any debugging. And it's a nice feeling.

    My code
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -39 Vote: I do not like it

      I guess what most of us meant was that, it is slightly more tougher than the usual Bs!

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

      That means sir you are using multiple codeforces accounts....:)

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      Do you agree that hacking during div1 and div2 contests became obsolete after changing single test cases to packets of test cases? The amount of test cases increased and many corner cases are included.

      For example B and F could have smaller amount of pretests, then participants could search for incorrect solutions, and possibly that round would become no less interesting.

      How about splitting CF rounds (div1,div2 with uneven scores) into two variants: 1. Round without hacking (full tests) or hacking time 30 min.after solving time finishes, 2. Oldschool round: weaker pretests and hacking anytime (and possibly with novelty — progressive bounty for (un)successful hack).

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

    Can someone explain why my solution to B (141591638) is getting Runtime Error instead of WA (I'm not handling the case of using a single longest segment, but I don't see anything in my code that wouldn't work) ?

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

      NVM it's because 10^5 != 10000

»
2 years ago, # |
Rev. 2   Vote: I like it -17 Vote: I do not like it

problems are good but im noob lol Happy new year!

»
2 years ago, # |
Rev. 2   Vote: I like it -37 Vote: I do not like it

Problem D was nice

»
2 years ago, # |
  Vote: I like it -10 Vote: I do not like it

How excellent the problem B is!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me with B ?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Keep track of three values:
    i) Lowest cost of range with lowest integer value till now
    ii) Lowest cost of range with highest integer value till now
    iii) Lowest cost of range with both lowest and highest integer value till now
    
    Then answer is min(i + ii, iii) if iii exists else it is simply i + ii
    
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why do we need to maintain (iii) if we are already maintaining (i) and (ii) won't it lead to an optimal solution?

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

        `` Example

        1 5 10

        6 10 10

        1 10 18

        iii keeps track of last one else we may need to take 10 + 10 ``

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

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.

»
2 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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?

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

    At first I thought that the solution is to find the shortest path (the one with least snow to clean) from any of the top left squares to any of the bottom right. But there was no way to move the people along it without cleaning one of the 8 cells. Got AC but wasn't able to prove it throughout the competition. The fact that so many people had the problem, made me think of an easier solutin, otherwise I probably wouldn't have solved it.

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

    when I want to find a way to go from the left-top to right-bottom, I notice these 8 cells are special, because we cannot go to the right-bottom without passing one of them, after that, I found all friends can go to the right-bottom just using one of these cells.

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

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

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

    Doubles have precision issues, so it's better to compare them as fractions. A general trick to do the comparison $$$a/b < c/d$$$, is to multiply both sides by $$$b \times d$$$ (assuming $$$b, d >0$$$). Then you get $$$a \times d < c \times b$$$. These numbers could be big, so use long longs.

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

    You can even take ceil value of the division since it has to be greater than or equal to that

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

    I use double and Coordinate Compression, so you can only care about intergers with maxval = O(n)

»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

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

    C wasn't too bad to implement... 141526460

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

      Yes, I did inspect some solutions, looks like a three liner. Still there are a lot of partitipants not able to write down that (simple looking) lines of code.

      How is the process to come up with that? Which abstractions are usefull here, which are not?

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

        usually, when you can't implement a solution, it means that you don't actually (or deeply) understand the solution you have come up with :v 141527334 btw here is my implementation.

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

          I think the difficulty with typical implementation problems is more likely to confuse things, and simple off-by-one errors. The solution is then to use the right abstractions in the thought process and to sort them cleanly.

          The solution "I have to see it, its simple!" did not work for me in this problem, and actually does not in general.

          Edit: However, congrats to reaching a new color!

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

          Thanks for that implementation. I now understood it But why are you not printing cout.flush() after printing the query?

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

      Yes C was pretty easy to implement as compared to B in my opinion.

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

    Here is a simple implementation 141573460

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    Input
    Expected Output
    Your Output
    Comments
»
2 years ago, # |
  Vote: I like it +45 Vote: I do not like it

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

Just throw everything into a segtree then forget about casework.

»
2 years ago, # |
  Vote: I like it +72 Vote: I do not like it

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

:(

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

    I didnt realize this until now xD

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

    I am also thinking about the same case. can you pls provide your proof.

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

      lets see on 4 points (1,1),(1,n),(n,1),(n,n) when first of them moved one of them will go to one of 8 points mentioned in solution.

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

      Say, you want to take this path. This will result in

      Now, you want others to follow the same path for which you'll either do a column up or down, so that the element is placed on the same row (So that same path can be followed). This can be done on any column, either up or down.

      The problem is that, one element moves out of the first n*n square, and takes another path (B)

      So, the answer becomes Cost(A)+Cost(B) (for now). It will add up even more if you do the same with other columns. But, you can accomplish the same thing with only Path B too. So, that becomes the minimum cost path ( Cost(A)+Cost(B) > Cost(B) ). This way, all eight corners can be proved.

      PS. Sorry if this didn't explain the problem

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

    I only realized this in the last 2 minutes of the contest. Also couldn't implement C on time. :(

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

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

»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it
»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

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

    I don't know if anything else is wrong in your code but the first mistake i noticed is that you are taking k and n instead of n and k.

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

      Yes.. k for the size of board and n for the rooks. Btw thank you for the reply.. I forgot to put the continue; after 2nd if.. jsbsvajnfnn.. but i hope that's not the only error or else i wont sleep tonight.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone point out my mistake on B? 141546457

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

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?

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

    In G, fix the end point, and calculate the answer for all the starting point that corresponds to the current end point. We can just store the updates done to fenwick for current endpoint and undo them in the end.

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

      Ah, thanks a lot! I was missing the moment that no value (no $$$a_i$$$) can correspond to different endpoints. I thought it is somehow possible, so we need to consider $$$O(n)$$$ values for every endpoint. But actually it is $$$O(n)$$$ in summary :)

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

    How can you think that tasks where you just need to implement trivial idea are good, but tasks where you actually need to think — are bad. Do you think cp should become fast-typing competition?

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

      Yes, indeed it sounds strange.

      No, I don't think so. Competitive programming is solving problems and afterwards coding them. I don't like the problems that omit one or another part.

      The problem 1375C - Element Extermination is great example of creating a problem that involves pretty much thinking while the correct solution is so simple, that you can't believe in it. Well, to be objective, it is just simple. I am pretty sure that the majority of the participants, who solved it, just guessed the answer. I was one of them (the contest was about to end and I just had different tries). The process of solving the problem didn't get me much joy.

      I haven't solved the problem D from Hello 2022, but I think the problems are really similiar. The only difference is that it's harder to guess the answer in the problem you were talking about, while one-liner for 1375C - Element Extermination makes it somehow beautiful, while easier to guess the answer. (It is my personal opinion, I am not certain, what is more beautiful or more evident).

      The proportion (thinking : coding) is really unjust in such problems. You make some complicated thought process and afterwards submit quite easy code. The problem would look much better not here, on CF, but on some mathematical contest. Of course, with proof required.

      On the other side, in the E problem the proportion (thinking : coding) was the opposite. The implementation part was huge, and because of that I named it implementation task. However I don't think it was stupid straightforward implementation. The problem required some observations: {you can't dynamically move elements in the set and compare all of them to corresponding values in given array. However, here all the values move at most one position to the right, or one to the left. It wasn't obvious for me, while it wasn't difficult too}. It required some data structure to achieve 'range logical AND of boolean array' (prefix sums).

      Probably, it is too weak for global round E. Well, it may be too standard. However, I managed to mess up something in binary search (it was really disappointing), so it's not only about fingers speed, but also about correctly implementing the solution. Here coding mattered more than thinking, but I believe the proportion was fine.

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

        you can't dynamically move elements in the set and compare all of them to corresponding values in a given array

        $$$\pm 1$$$ shift observation lets you do prefix sum-style solution, but it was not necessary to make it. As long as the array $$$b$$$ is split into a constant number of parts one may apply a certain rmq-like structure with a log overhead.

        Specifically, for all segments $$$b[l..l+2^k)$$$ we can precompute the leftmost position $$$i$$$ such that $$$a_{i + j} \ge b_{l + j}$$$ for all $$$j \in [0, 2^k)$$$. Then we can compute the same position for any segment of $$$b$$$ with log overhead.

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

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

»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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.

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

    Close, but there are $$$k!$$$ ways to arrange the rook given the column and rows.

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    "permutation the way it is presented here , exists as a set of disjoint cycles"-> something which is useful here picked from Abstract Algebra

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

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?

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

    You ignored that one of the friends in the four corners must moved one cell out of the upper left quarter. There is simply no way to move them at all without doing this.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

B was a hell

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

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

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.

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

    Nice approach! But shouldn't the condition be min(diff[i]) for all i from 1...1e5 >= 0?

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

      Thanks for pointing that out. That was written in not the best of mental conditions.

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

    Alternatively, instead of using a lazy segment tree, you can use an ordinary segment tree which stores the sum and the minimum suffix sum in each node.

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

      I don't understand can you explain your idea bit more.

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

        (adding a teacher/group should actually add 1/-1 to diff[1..v], not diff[v..1e5] in the original solution)

        Let a[i]=diff[i]-diff[i+1]. Then what adding 1/-1 to diff[1..v] does is adding 1/-1 to a[v]. You can get the diff array from the a array by noticing that diff is just the suffix sum of a. So, when you're looking for the minimum value in diff, you're looking for the minimum suffix sum in a, which a segment tree can easily handle.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it +149 Vote: I do not like it

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

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

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

»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

are there are any prerequisite for that question ?

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    i have done like this(but after the contest). we can consider p array as directed graph. eg if p=[4,2,1,3] then the graph will be like this https://ibb.co/sJZ4tM2 now there are 2 type of edges, one is self loop. other is cycle. now what i do is, for every i in [1,n], i ask for the value at that index if i dont know p[i]. for every i, i ask multiple times, if corresponding values are equal, then it is a self loop and p[i]=i; else i ask q[i] until i see the complete cycle, lets say q1=a and q2=b, then p[q1]=q2.

    here is my code: https://codeforces.com/contest/1621/submission/141614438

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

      thanks! with an example i was able to see that elements present in a cycle simply exchange their positions as if they are in cycle .

      Can any explanation be provided about why this is happening ?

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

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.

»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it -27 Vote: I do not like it

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(); }

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

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,

$$$P(X_i) = P(i \ \text{is included}) \cdot P(\text{the sequence including} \ i \ \text{ends before} \ lst_i).$$$
$$$ = P(i \ \text{is included}) \cdot (1 - P(\text{the sequence including} \ i \ \text{includes } \ lst_i)).$$$

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

$$$P(X_i) = \frac{tot_i}{tot} \cdot (1 - \frac{tot_{il}}{tot_i}) = \frac{tot_i - tot_{il}}{tot}.$$$

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

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

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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    I didn't look into your code too much, but I found a testcase for which your code gives WA

    testcase
    expected output


»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

avkonyahin

Input
Expected Output
Your Output
Comments

practice_52

Input
Expected Output
Your Output
Comments

pks18

Input
Expected Output
Your Output
Comments

Abhishek357

Input
Expected Output
Your Output
Comments

Mysticode

Input
Expected Output
Your Output
Comments

_s_h_n_

Input
Expected Output
Your Output
Comments

AnestheticCoder

Input
Expected Output
Your Output
Comments

Blinding_Lights

Participant-Jury Interaction
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot for providing that testcase. I was trying for hours. Thank you! :)

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

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

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

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]

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    if q is not 1,2,3,4... initially and it is P then the same idea seems to work

»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the editorial mate :)

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.