Hello everyone!

Recently I was talking with my friends about task E. Editorial and solution of this problem involve two greedy observations. First of all it's kinda intuitive that we can omit such indexes, that both strings have equal letter on them. However, I didn't see any proof of this in editorial and actually I couldn't prove it myself too. So here comes my first request. Could anyone show formal proof of this observation?

Suppose we have this proven now.

It turns out that we can achieve minimum number of operations using greedy algorithm (just picking alternating (0 and 1) or (1 and 0) whenever we can from left to right). Editorial mentions that the number of required operations is equal to the "maximum absolute value of the sum of any subarray in A", where A is an array which meets the conditions :

if si==ti, Ai = 0
else if si==1, Ai = 1
else Ai = −1

(sorry for shitty formatting)

However I believe that the proof of this part is trashy as well. Suppose that maximum sum of subarray in A is M. If I'm not mistaken editorial doesn't deal with the case when we could potentially inscrease by 1 sum of subarray which had sum M-1, thus preserving the maximum subarray sum between operations.

I would also love to see proof of this part. I suppose that proof of the second part is easier than the proof of first part.

There is also a possibility that I'm just stupid and it's all trivial, however I think that not proving things in editorial of greedy problem is not commendable. I have also seen some people asking about the first part and no one responded them. I believe that at least 90% of people who got this problem accepted is unable to proof its correctness. I would love to see some feedback — proofs of both parts mentioned above and your thoughts on putting greedy problems, which can't be proven easily in problemset.

Have a nice day!