At first I thought that changing the conditions would make it harder to realize why we do not run out of prefixes during the substituion step. But after rewriting that part I think it did end up being easier to understand so... thanks for the suggestion!

Yeah, you’re right. There is no substitution that we can make without decreasing the size of the LIS.

But I have revised my submission and the solution in the editorial and the LIS has to be strictly increasing (which I didn’t remember last night when I wrote the previous answer) so we shouldn’t run into this problem.

Sure, but if they are equal you can simply replace $$$a_1$$$ and all of its prefixes with $$$a_2$$$ and all its prefixes since they will all be equal. I was probably thinking of a strictly increasing LIS when I wrote the proof

Yup, that was wrong. Hopefully, I got it right this time.

Regarding your questions:

1. The fact that $$$|s1| \lt |s2|$$$ should be enough because $$$r1-l1+1=|p|+|s1|$$$ and $$$r2-l2+1 =|p|+|s2|$$$ (just because of how $$$a_1$$$ and $$$a_2$$$ were split into the common prefix and "something else"). Now I want to replace all the prefixes of the suffix $$$[l_1,n]$$$ with prefixes of $$$[l_2,n]$$$ that are smaller than $$$[l_2,r_2]$$$. I can pick as many as I need from $$$[l_2,l_2], [l_2,l_2+1], \dots [l_2,r_2-1]$$$. All of those are valid since they will be greater than or equal to the corresponding ones from $$$[l_1,r_1]$$$ and are smaller than $$$[l_2,r_2]$$$. I should have enough because there are at most $$$r_1-l_1+1$$$ prefixes of $$$[l_1,n]$$$ in the LIS, this list has $$$r_2-l_2$$$ elements and $$$r_1-l_1+1 \lt r_2-l_2+1 \implies r_1-l_1+1 \le r_2-l_2$$$.
2. They might be in conflict. If they happen to be I can repeat the process and delete the ones that I added (along with some more). Each time I delete and add elements I will get rid of a position in which there are two adjacent elements in the LIS with a different beginning such that the first one does not reach to the end of the string (does not end at $$$n$$$). Therefore we can just keep repeating the process until there are no such positions and then the LIS will adhere to the claim.

I'm not sure if I understand your doubt correctly but I think there are some things that I could clarify.

What we actually want to prove is that there is a LIS of maximum length in which the "initial claim" holds. To do so I can assume that the LIS of maximum length does not fulfil this claim. In that case, I can take that LIS and modify it so that it fulfils the claim. Therefore I have reached a contradiction and there is a LIS of maximum length that fulfils the claim.

Keep in mind that there might be other LIS of maximum length that do not follow that structure at all. All we need to know is that there is one that does.

In problem E, I didn't quite understand the reasoning behind the fact that if the string $$$[l,r]$$$ is present in the LIS, the following ones ($$$[l,r+1],\, \dots,\, [l,n]$$$) must be present too so I want to share the proof that I came up with.

Firstly, we can observe that if $$$[l,r]$$$ and $$$[l,r+k]$$$ are present, all $$$[l,r+i],\ i \lt k$$$ must be present too. This is trivial since $$$[l,r+1]\ge [l,r]$$$. Furthermore, all these elements must be next to each other since that is the order that they follow in the sequence.

Now, we can prove the initial claim:

Let us assume that we have a LIS in which this is not true. Then there must be two adjacent elements in the LIS $$$a_1=[l_1,r_1],\ a_2=[l_2,r_2]$$$ such that $$$l_1 \lt l_2$$$ and $$$r_1 \lt n$$$.

• If $$$a_1$$$ and $$$a_2$$$ have a common prefix, we can denote its longest common prefix as $$$p$$$. Then, we know that $$$a_1 = p+s_1$$$ and $$$a_2 = p +s_2$$$ where the $$$+$$$ represents concatenation and $$$s_1,s_2$$$ are some strings.
  • If $$$|s_1| \gt 0 $$$, since we know that $$$s_1 \lt s_2$$$ (because $$$a_1 \lt a_2$$$) and $$$s_1$$$ and $$$s_2$$$ do not share any common prefix (otherwise $$$p$$$ would not be the longest), the first character of $$$s_1$$$ must be smaller than the first character of $$$s_2$$$. In this case, we can add all the rest of the prefixes of the suffix $$$[l_1,n]$$$ since all of them will be smaller than $$$a_2$$$
  • If $$$|s_1|=0$$$, we know that $$$|s_2|$$$ cannot be we 0 (otherwise $$$a_1=a_2$$$). Therefore $$$|a_1| \lt |a_2|$$$ and we can delete all the prefixes of the suffix $$$[l_1,n]$$$ replacing them by the corresponding prefixes of the suffix $$$[l_2,n]$$$. A more detailed proof of why we will have enough prefixes to do this replacing operation is provided in the replies to this comment.
• If they do not have a common prefix, $$$a_1[0] \lt a_2[0]$$$ and we can include all the remaining prefixes of $$$[l_1,n]$$$ in the LIS as they will all be smaller than $$$a_2$$$

By performing these changes a finite number of times we get a LIS that does not have less elements and fulfils the initial claim.

Edit: Changed the conditions in the proof following maomao90's suggestion to clarify the proof

Thanks!!

I was trying to argue back but thinking of it as adding zeroes made me understand why it works.Just in case anybody has the same doubt I'll elaborate on why I got confused with this:

5 2 10
11 11 8 8 8

For this testcase, the best I had been able to find was 11 8 8 8 11. But it turns out 8 8 8 11 11 is better.

However if you don't add the zeroes you won't find the second one since the code (at least mine) expects two days of being muzzled after each big number but that is not always the case.

I have a question about Div. 1-A.

Does anybody know why in the tutorial they are filling the array of the smaller elements with the last value as if there were more small elements?

I have made two submissions 89774711 and 89774745. The only difference between them is that in the second one I have commented out line 96 which is equivalent to the fill call in the tutorial. And the way I see it by adding those values to the end of the prefix sum we would be considering cases that are not valid because they have too many small elements.

Can anybody please explain this to me?