jimmy51997's blog

Unable to understand the editorial for the problem — "The fair nut and strings" from cf round 526 .
By jimmy51997, history, 6 years ago, In English

Hello everyone,

Can anyone help me with this problem. I don't get the part from the second paragraph in the editorial. I have understanding of both trie as well as binary trees. Any help would be much appreciable.

Problem link — https://codeforces.me/contest/1084/problem/E

  • Vote: I like it
  • -20
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I also found editorial very difficult to understand. Then I tried implementing without any binary tree or trie. Luckily, I got AC.
Here is my solution
My idea is simple. I have done using map. You can do even using array. First I just calculated how many pts. will be there in both strings where by replacing that character with another I can form different strings. And then I stored them in map according to their length( length means how much length will be different from original string) And then added similar length of s and t once and different part individually.
Now just a for loop from i=1 to length of string. As whenever m[i] is non zero it means I can use it to form other strings and it will lead to two strings one by putting 'a' and other by putting 'b' and their length will be just one less than current length so, I will add those in map. One last part, I have stored Initial lengths what I got from s and t in map as well as in an array. Now, I have subtracted that array part from m[i+1]. Because these lengths will lead to only one string ( because other part will be either s or t acccordingly from whom it is taken and I have already considered lengths of s and t ). As I have taken these lengths also two times so, by subtracting arr[i] one part will get cancel off. And I will keep on subtracting k and whenever it becomes 0. I will break the loop. and print the answer.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

bittudalal Thanks for the help. I am able to understand how you are increasing m[] according to s[i] being 'a' or t[i] being 'b'. But, why are you incrementing m[i+1] and decreasing it by arr[i] is troubling me. Can you add something for this?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Because each time one string will decompose to two strings one by keeping 'a' at that position and other by 'b'. Now string length gets reduced by 1 because we have fixed this index. So, I can change only remaining indexes thats why I have added two times in m[i+1] and subtracted arr[i] because this arr[i] part will lead to only one kind pf string(othe kind will be s or t) but I have counted it two times. So, to make it only one time I have subtracted this from m[i+1].

    → Reply