Guck_Freedy's blog

By Guck_Freedy, history, 3 years ago, In English

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!

  • Vote: I like it
  • +51
  • Vote: I do not like it

| Write comment?
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Perhaps not completely formal, but I can prove it.

Let us take the cases where a solution exists. Lemma 1 : The number of places wring $$$1s$$$ is equal to the number of indices with wrong $$$0s$$$.

Lemma 2 : Let us notice that a move is equivalent to choosing an alternating sub-sequence of even length and then flipping them.

lemma 3 : Now notice that we must choose the indices that are different an odd number of times and those that are same an even number of times. Make sure to keep in mind using an index for a second time is using it as the opposite of what it was.

Lemma 4 : We can show that we will choose $$$1s$$$ and $$$0s$$$ an equal number of times by Lemma 1 and Lemma 3.

Let us assume we only use the values which are wrong and choose them once.

We can compute the best answer given that we have chosen these sub-sequences by remembering the number of sub-sequences chosen for the first $$$i$$$ elements of each parity and of each ending value

Let us show that the parity is irrelevant.

If we choose an odd sub-sequence 0101 ... 010 we must also have 1010 ... 101 by Lemma 4. We can show we can also merge them and form 2 even sub-sequences with some case work.

Now let us see what happens when we choose an element twice. One sub-sequence that ends with $$$1$$$ now ends with $$$0$$$ and one sub-sequence that ends with $$$0$$$ now ends with $$$1$$$.

This does not affect the answer at all even if we do multiple of these.

Therefore there exists an optimal solution that chooses only the ones that are wrong and only once.

  • »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you tell you proof greedy problem in contest ??

    • »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We need to follow some steps: 1. Make a greedy choice which you will be using to solve our problem 2.prove that it will never lead a worse answer that an optimal solution

      But in general in contests, no such formal proving is required and intuition plays a major role, unless you are not very confident of your stratergy or the problem needs it.