willtryagain's blog

C. Good String
By willtryagain, history, 4 years ago, In English

In the problem good string([https://codeforces.net/problemset/problem/1389/C]) I made two observations- 1. When n is odd then all characters are equal ~~~~~ 2. Else

s1 = s3 = ... = sn ~~~~~

s2 = s4 = ... = sn-1 ~~~~~

It means the string is fixed by the first two starting characters. I iterated from 0 to 9 for the first two characters and found the count of positions-

- if i is odd and si != s1 or
  • i is even and si != s2 ~~~~~

My answer is off by one in some test cases. I want to a small test string where I could find the reason.

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

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

If you are taking an alternating sequence then the length of the sequence must be even.

Eg: 59595

Here the alternating sequence is of length 5 but we need an even length if we are alternating so ans will be 4. But if you are taking all same chars then it can odd or even, no matter.

if(len%2!=0 && i!=j) len--; //if length of sequence is odd and it is alternating(i!=j), take len--

This may be the reason your answers are off by only 1.

My submission : Good String

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

I am pretty sure that if all the numbers are the same (i.e. aaaaa...), then it can have any length, odd or even. If the numbers are in alternating order (i.e. ababab...), then it HAS to be even.

This is my submission -> https://codeforces.net/contest/1389/submission/88384839

If you want it. Test this string out:

1233330985

The optimal answer is to remove everything except for the EVEN amount of 3's

→ Reply