aditraj2004's blog

By aditraj2004, history, 4 months ago, In English

Question Id :- 1714D - Color with Occurrences

Wrong Submission Link :- 242502092

In Problem D ,why does the algorithm in which selecting the word from which maximum red letters occurs in string s in a given step doesn't work.. According to my understanding .. If we don't pickup the substring of s in which maximum occurence of red happens in a step , then we can always pick it up later if the substrings of current picking doesn't intersect with the substring in which the maximum red occurence happens in a particular step. And if the substring intersect , then still we can swap the positions of picking of a substring in which maximum red characters appear in a step , the number of reds will decrease by the same. But , if one string is a substring in the strings in which we have to make it red. then picking the string with maximum red happens in a step is still optimal ..

So , Why at each step just applying the operation with the string k[i] (1 <= i <= k) , in which the maximum new red characters which happen in a operation in string s is wrong.

Implementation of the Algorithm :- In the submission Link.

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by aditraj2004 (previous revision, new revision, compare).

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Maybe this testcase will help:

1
abaaba
2
baab
aba
2
2 1
2 4
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I ran your code and got incorrect answer in this testcase.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Okay , Thanks for the help..

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot , bro understood what was wrong with my proof . By the way , how did you generate the test cases and found the wrong testcase. Is there some website that generate the test cases ?