Help in Codeforces problem (571-Div2)

1

Can any one suggest me an approach to solve this problem

Thanks in advance :slight_smile:

1 Like
2

Lets assume you have two strings having same length and you have to count the number of positions where the two strings are different and tell whether count is even or odd, so first take indices where both strings have common bit so if that same bit is in both string thus total sum of no. of 0 and 1 bit in both strings is even till now, now coming to the number of indices where they differ means in one string it will be 0 than in the other it will be 1 or vice versa so if the count to be even than the number of 1’s and number of 0’s will also be in total be even as number of 1’s=number of 0’s=number of positions where the two strings are different.
So, basically (number of 1’s or 0’s in string a+number of 1’s or 0’s in string b) should be even for the count to be even.

Now coming to the original problem we can take each subarray and calculate number of 1’s in it and if the (number of 1’s in subarray + number of 1’s in string b) is even than count+=1.

Complexity:O(len(string a))

1 Like
4

String a be 11100110100
String b be 11111001000

From index 0 to 2(inclusive) both strings are common so the total number of 1’s are 2*(3) (even).

From index 3(i) to 8(j), the strings have different bits at these positions but as each index between i and j it will differ so number of 1’s(a+b)=number of 0’s(a+b)=j-i+1;
So, for j-i+1 to be even, the number of 1’s will be also even and the number of 0’s will also be even.
And where they are the same the number of 1’s or 0’s will be even.

So, for the number of positions where the two strings are different to be even the total no. of 1’s or 0’s(1’s in a+1’s in b ) will also be even.

I hope this may turn to be useful.

1 Like
5

I too participated in this contest, just wanna know what was wrong in the question B, and did you try solving it?

6

Yeah, I attempted B and wasted a lot of time on it but I think this is not the platform to discuss such things, already there is much chaos on codeforces on this topic so you can refer to the comment section of the announcement of the round on codeforces for details.

7

Just ended up doing A,C,D in virtual contest, can you explain E? I tried to do it as a[i+1][j+1]=a[i+1][j] + a[i][j+1], but at the end on pen paper, I got like 4k or something on 8,8.
After that I wasn’t able to figure how to do it.

8

I don’t think, it’ll pass with an O(n^2) time complexity, you could do it with O(n). Simply take the minimum values and keep checking when sum reaches 0. If we take minimum values then, we would have either 0, or negative sum, then increase the elements one by one(Increase only if they don’t have ceil(val)==floor(val)), increase sum by 1, and check if it’s 0. go out of the loop.

here’s my code: Submission #56237952 - Codeforces

9

Here is the editorial of the question: Editorial of Codeforces Round #571 (Div. 2) - Codeforces

10

My bad Sorry, I was actually talking about problem E