Things_I_Do_For_WA's blog

By Things_I_Do_For_WA, history, 2 years ago, In English,

I believe I have a correct solution for the problem. Of course I know that division 1 red coders tried it for quite sometime and did not manage to come up with a proved solution so I won't dare give 100 percent guarantee. But anyway I am writing my approach and my proof here. If anyone finds a counter example or mistake in my proof, please tell me so. I am also writing because it could help someone to find a new approach and get a full proved solution. I also know that LLI_E_P_JI_O_K explained his approach in the comments of the announcement post and his solution is looking correct. However, if I had understood correctly, he seemed to have attacked the problem case by case and there may be a little chance that he missed some case. Instead, I used a kind of complete search to solve it.

So, we already know if the segment length is greater than 2*(a+b) then the answer will be a+1 ( if b>=a ) or 2*a-b (else). Now, if the segment length is smaller than that, first we will find how many 2*(a+b) segment has appeared before l-th index. Let there be n such segments. It can be easily shown that Mr B always has a strategy such that he can play through this 2*n*(a+b) long string such that from the next index the computer will produce the first a alphabets (which was done initially at the game). So we assume that the game is played by that strategy until the string has 2*n*(a+b) length. After that, we have to generate a string that gives minimum number of distinct character for [l,r] range.

The string we generate will have 4*(a+b) length. This will handle all the possible l and r when the segment length is smaller than 2*(a+b) So, the computer will have 4 moves and Mr B has 4 moves within this string. Now, the computers move is always dependent on the previous suffix and Mr B has options in his choice of character. So different string can only be generated by varying Mr B's choice. Now, here comes a slight potential drawback in my approach. I believe, its always optimal for Mr B to choose one single character in each of his move. He may select different characters in different moves but when he chooses one character in one of his move he will stick with that character throughout the move to get the best result. (I can't prove this belief. Its just a very strong intuition. Someone is welcome to give a formal proof or give a counter example to this assumption.)

Hence, in each of his 4 moves, Mr B has to choose 4 characters. So in total there can be 26^4 options for him and therefore we will have at most 26^4 different strings. (This can be further optimized by limiting total characters from 26 to max(a+1,2*a-b) which can be the maximum answer. However, using 26 also runs within the time limit, I tested it.)

So, here's how the solution goes: If segment length is greater than 2*(a+b) the ans is a+1 or 2*a-b depending on the value of a and b. Otherwise, the initial string will be the first a characters. So there will be 4 Mr B's moves and 3 computer moves left. So we keep a vector of length 4 which will store Mr B's choices of characters for each of his moves, generate the string by appending Mr B's characters and also computing the computer's move by passing current string to its algorithm. By varying the vector, we will have a total of around 26^4 strings max. And for each of this string we can count how many distinct characters are there in the range [l:r] and we take the minimum of it.

Here is my AC code: 28108706

Anyone is welcome to share his/her opinion.

Read more »

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