PHIL_STONE - Editorial

editorial
1

PROBLEM LINK:

Practice
Coding Retreat

Author: darknight_1729
Tester: darknight_1729
Editorialist: darknight_1729

DIFFICULTY:

EASY

PROBLEM:

There are total N (odd) shards. There are 2 types of shards A and B. Three consecutive shards can be fused into one iff only 2 shards are of same type. You have to tell whether this process if produced repeatedly will result in only a single shard at the end.

QUICK EXPLANATION:

Let F_A and F_B be the number of A (auburn) shards and the number of B (black) shards, respectively.
You need to check whether or not | F_A ​ - F_B | = 1 . If it is then it should print "Y" else print "N".

EXPLANATION:

Let F_A and F_B be the number of A (auburn) shards and the number of B (black) shards, respectively.

We can observe that every time shards are fused F_A and F_B each decrease by 1 . One implication of this is that total number of shards F_A + F_B ​ decreases by 2 each time. Since N is initially a positive odd integer, this means that the sequence of shards will always be reduced to a single shard after enough fusing operations, as long as they can all be performed safely. A more interesting implication is that | F_A ​ - F_B | remains constant between operations. Since | F_A ​ - F_B | ​ must be equal to either 1 or −1 when there’s one shard remaining, we must also have | F_A ​ - F_B | =1 in the initial sequence in order for that final state to be achievable.

So far, we’ve shown that the answer must be "N" if | F_A ​ - F_B | \neq 1 . The remaining question is whether the answer is always "Y" if | F_A ​ - F_B | = 1 . The only way it could be "N" is if it were impossible to perform a fusing operation at any point while there are three or more shards. This is only impossible if all shards are the same colour (as there must otherwise be at least one consecutive triple of shards not all sharing the same colour), which cannot ever be the case if N \geq 3 and | F_A ​ - F_B | = 1 (as we must have F_A \geq 1 and F_B \geq 1 ).

Therefore, we have only to loop over the shards in O(N) time to compute F_A and F_B , and then check whether or not | F_A ​ - F_B | = 1 .

SOLUTIONS:

Editorialist's Solution 
#Python Solution 
test=int(input()) #For taking test cases as input

while test:
    #For each test case
    test=test-1
    n = int(input()) # Number of shards
    
    s=input() #String containing A,B (Type of shard)
    
    freq={"A":0,"B":0} #Dictionary containing frequency of shards
    for i in s:
        freq[i]=freq[i]+1
    ans="N"
    if abs(freq["A"]-freq["B"])==1: #Checking absolute difference
        ans="Y"
    print(ans)