Hello, CODEFORCES!

In this blog, I would discuss the intuition behind a problem which I felt was pretty interesting. So in case you wanna read the problem statement or try it out yourself, I'll leave a link to the problem down below. Happy reading! :))

Problem link: https://www.codechef.com/problems/STRINGXOR?tab=statement

1. The first thing that you wanna note down is: If both the strings are already equal then you don't really need to do any operations, and the answer will definitely be a "YES".

2. Now, let's first take a simple case where N=2, i.e. the size of the string A is 2. In this case, the only possibilities are 00, 01, 10, and 11. Let's find what happens if we xor them up : 0^0 =0 , 1^0 =1 So, we get 00, 11, 11, 00. Now, one thing to note here is that if there is an array having only zeros, you can't really transform it into a string B (where B is not equal to A).

3. A key observation that follows is: If at least one '1' is present in string A, you can actually convert it into any other string B (with a few exceptions which I'll be discussing later). This is because say you have a string of the form: 1000. So, you can xor up the first two characters, and you have: 1100. If you proceed in a similar manner, you can have 1110 and 1111. Moreover, you can even delete "1's" in pairs. Like 1100 can be converted to 0000 by applying a xor operation on the first 2 characters. Similarly, 1110 can be converted to 0010 or 1000, and then you can shift the ones by similarly xor-ing up the characters and then deleting the characters. (I hope you get the idea!)

4. If you are still a bit confused take a paper and pen and write down '111' and try converting it into the other possible 3-letter binary strings(000,001,010,011,100,101,110) by performing xor and delete operations. (By delete, I do not mean the removal of any character. All I mean is: after xor of 11 we get 00 so that operation.)

5. By doing the above exercise, one thing you'll notice is: that you can't really convert it into 101 and 010. Boom! now you're almost there... try to find the similarity between the exceptions and try to reason why it is happening. Even if we go back to the earlier case (N=2), we find that we can't actually convert 11 to 10 or 01. Do you find a similarity between these exceptions? .. well yes, you are correct: if we have alternating ones and zeros in string B, we can't really do any operation to a string A to convert it into B)

Well, that's it!! Now you can go on and implement the solution for yourself. But before that, I'd like to pass on a few remarks. In problems of this type, the difficulty that most of us face is basically not being able to explore all the possible exceptions, or not being able to find a trend that the problem wants us to find. So, I recommend the following approach :

1. First break down the problem into smaller problems..(by this I mean try to take N=2, N=3,.. and understand what actually is happening in the problem. In most cases, after some workings and a bit of patience, you'll be able to find trends in the problem, and it would start to look less open-ended.

2. Once you get a good understanding of the trend, it's now time to look for the possible exceptions. They must be following a particular mathematical/logical trend. Just break through that, and you'll be good to go!!

In case you still are stuck somewhere, am attaching my code down below for your reference. Feel free to comment down below in case you still have doubts :)

MY CODE : /predownloaded/5e/9b/5e9baf59ef1f10c099953f67b95e57abf4ca160a.png

Hello coders! I am sure all of you would have faced a "Wrong answer on pretest 2" at some point of time during your codeforces journey. It is a pretty frustrating feeling when you see your ranks (or ratings) dropping by a significant amount only due to some edge cases which you could not figure out during the contest time.. But the question that then comes to one's mind is : "Am I that dumb to not have figured it out then?.. and is there a way to make sure it doesn't happen a second time?" Well the answer is both a yes and no. So if you're someone struggling in the range between 1000-1400 (or even lower) then you might find this blog helpful!

Actually, for the past few weeks this has been a major concern for me because either during contests or even while practicing I used to get a lot of "Wrong answer on test 2" and when I used to check for the case where I went wrong.. Most of the times it used to return something like "786th token doesn't match". Now how on Earth am I to figure out where my code is going wrong because the 786th input is not visible to me.. Right?! What you actually can do is the following:

1. First thing, don't get demotivated by it because even the top coders aren't completely immune to it.. But one can definitely reduce it's frequency or reduce the time of getting their solution "accepted" after a "wrong ans on pretest 2" by immense practice.

2. Talking about problems A and B (#div.2) — the problems aren't complicated.. so the reason of getting a wrong ans mostly is because sometimes our approach to a question may be correct but the way we implement our solution may involve unnecessary complications (in terms of usage of multiple and unnecessary data structures or variables)..

So one can try to think of a particular problem in the simplest way possible (both in terms of approach and implementation). And I would recommend not to check what went wrong in your submission immediately after the verdict (while practicing). Instead try to first exploit all the possible edge cases that might have occurred or maybe try to reduce the unnecessary complications that ur solution might be having. And after making the necessary changes in ur soln, try resubmitting. In many of the cases you will get an "Accepted" verdict.

Suppose if you don't get it, then look at the test case which the system displays (where ur soln would have gone wrong) .. try correcting it! If it shows something like [786th tokens don't match].. then don't just get frustrated and leave the question then and there... if you are mentally too exhausted with that problem then bookmark it and move to the next problem but after say 3-5 hours (in your recess period) try to think what could have possibly gone wrong in your solution (even if you don't get an "Accepted" verdict, it still is a good exercise.

After all this, look at a friend's code who got an "Accepted" verdict or if you can make a difference between your way of implementation and the editorial, even that works fine!!

Now the reason why I want you to refrain from immediately checking the editorial or referring to a youtube tutorial on that question is because, this way you won't build your logic and implementation skills and the next time you sit for another contest a "wrong answer on pretest 2" is bound to happen again.

NOTE : This tip might not prove very effective for those high up in the ratings or maybe for those who don't have much time to devote to Competitive programming. But for beginners this will definitely boost up your ratings and improve your problem-solving approach!

Hope this helps!