SPOJ - RGBRED , Color Play

1

Any idea how to solve this problem : Color Play

2

@nichke @ssjgz @suman_18733097 @iceknight1093 @cherry0697 please help.

3

ans will always be length of string or 1 or 2
find the cases now

4

could you please share your approach, all I can think of is greedy solution that’s not working here.

5

Here is my solution & testcase where code fails.http://codeforces.com/blog/entry/94410

6

if the string is homogeneous(made of 1 character only) ans is length of string
if all counts of R,B,G have same parity(all odd or all even) ans is always 2
otherwise we can reduce it to 1 character

RGRRGRR
fix left R
GRRGRR can be converted to BRGRR->GGRR->GBR->GG
now RGG-> BG->R

honestly I just checked some random samples and the logic seemed to work, so I submitted it
I don’t have a proof of my solution, my apologies.

1 Like