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
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".
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).
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!)
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.)
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 :
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.
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
Comments (0)
