Great editorial. This question took me longer than I’d like to admit.
To clarify on the Editorialist’s solution:
The variable fst stores the length of each successive gap encountered during the pass. The bool badstuffGot is used to ignore the identical characters in the prefix part (if present).
For eg. if strings are aaababa and aaaaaaa , then the initial aaa shouldn’t be considered.
Due to the nature of the pass, we push in fst into our vector only when we encounter unequal characters. Hence, identical characters in the suffix part of string s, will not be considered, which is correct.
Your code gives segmentation fault for the test case where both the strings are equal as vector ind will be empty and line 20 will make illegal reference and give sigsev
There are many cases which you can make if you understand the problem. To be very honest, you yourself can prove that your algorithm is wrong after some serious thinking. There are many areas in which a person can get a WA. Maybe if you will show me your code (if that is the reason why you are asking for test cases, i don’t know) I can help you.
Overall, this problem was a beauty. The setter @rumblefool nailed it, and editorialist @rajarshi_basu also nailed it in trying to explain the outline of this solution. Kudos to the tester @raja1999 for ensuring strong test cases.
First thing,Thanks thanks thanks a lot.
Second thing,how did you then figure out my solution if the link was wrong?
Third thing,this is my problem that even if I come up with algos,these mistakes just kill my hard work.How to improve in this matter?I had read the question 5 to 6 times,still made this mistake
If you have any suggestions ,kindly give me .because I also want to be a good coder.
For the second thing, there is something called Google / search engines.
For the third thing, This happens with me also. And in fast problem solving, you often forget or mess up the format of input. It happens with practice. Eg. With this happening, you will now never forget not to look at the Input section for the format.
ok @rajarshi_basu Sir, I want to discuss another approach.We sort the lengths of segments having similar character as the you have pointed out.Now what I try to do is that check whether these lengths when added whether decreases the the term KL or not.If not then we simply break out from the loop that iterates over this length.Otherwise the length is added to the value of total number of chars to be replaced and K decreased by 1.The condition to check for the inclusion is tested in the way that
whether current length of chars to be replaced>=length I want to add(K-1)?
Bcz when we add that length, K*L decreases by L and increases by (K-1)*no. of chars to be added to L.
If any length cannot be included,no length larger than this cannot also be included.
Is there anything wrong with the approach?
I am also attaching the link to solution. https://www.codechef.com/viewsolution/32167102
Anyone who could help in debugging my code will be awarded a princely state in the Ottoman Empire. Thank You in advance. MINOPS
PS: I’m facing wrong answer! @rajarshi_basu
.