sarthak_brahma's blog

Need help with Codeforces #715 (div 2) B
By sarthak_brahma, history, 4 years ago, In English

If the number of T is not double of M, then "NO". If the first or last character is M, then "NO".

I made two arrays that had the count of T's from the right and from the left. Then I traversed the string and for every M, I checked if the number of T's on left and right are positive or not. (To achieve this I had another variable which had the count of 'M' processed) `

vector<int> right(n), left(n);
    left[0] = 1;
    right[n &mdash; 1] = 1;
    for (int i = 1; i < n; i++)
    {
        if (s[i] == 'T')
            left[i] = left[i &mdash; 1] + 1;
        else
            left[i] = left[i &mdash; 1];
    }

    for (int i = n - 2; i >= 0; i--)
    {
        if (s[i] == 'T')
            right[i] = right[i + 1] + 1;
        else
            right[i] = right[i + 1];
    }

    int mp = 0;


    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'M')
        {
            int l = left[i] - mp;
            int r = right[i] - mp;

            if (l > 0 && r > 0)
            {
                mp++;
            }
            else
            {
                cout << "NO\n";
                f = true;
                break;
            }
        }
    }

`

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

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The two arrays to count from left and right are a good start!

"If the first or last character is M, then "NO"."

That is one special case. Take a look at "TMMTTT". This cannot work. Why? The first M is ok. we got 1 T on the left of it. The second M is not okay, since we only have one T two the left! You cannot provide for all M!

Can you generalize this?

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

    this is handled by the right and left array, when we will come to the second M, the left value will be 0, and "NO" will be printed

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

      I see, you are right! though, you are iterating from left to right but checking both directions. What does your Algorithm do with "TMTTMT"? It will fail at the second M, since there is only 1 T to the right and 2>1. But "TMTTMT" can be split into "TMT" and "TMT"!

      → Reply