Solutions

Problem - Self-Destructing Strings

Problem Link

As every deletion operation, deletes EXACTLY 2 character means parity of length of string does not change. Our objective is to make reduce string to empty string means to string of length of 0 which is even hence length of original string must also be even

Also, After going through few examples we can see, we need abs(cnt[0]-cnt[1])/2 operations.

But, There is one edge case :- when string contain only all same character then it is impossible to reduce it to empty string

Whenever something releated to afternative 01 or 10 is given, Keep this edge (when every thing is equal) in mind.

Code

CodeChef Solution Link

Problem - Circle of Chaos

Problem Link

Let’s see when will be not able to delete any of the sorcerer?

When N is such that, all the M spells are multiples of N.

As in this case

$$ M[i] \bmod N = 0 $$

=> Every spell will kill yourself.

Let g = GCD(All M spells)

so, When N is any divisor of g we wouldn’t be able to kill any sorcerer. So, We just need to find the greatest divisor of N which is not greater that N.

Code

CodeChef Solution Link

Problem - Sed Passwords

Problem Link

Its a simply bitmasking problem, Where first 26(0-25) bits will represent parity of frequency of current character. And we can use 26th bit can represent parity of frequency of ‘?’.

Let B[i] be current mask for string S[0]....S[i]
Let T be final mask of original string
we want

$$ B[i] \oplus B[j] = T $$

and

for K in [0-25]:

$$ B[i] \oplus B[j] \oplus (1 « k) \oplus ( 1 « 26) = T $$

For empty string, mask is 0

So remember to intialize cnt[0] = 1

Code

CodeChef Solution Link

Problem - Carry All Fruits

Problem Link

This is a contruction problem.

My idea is basically on each day I will put fruits in only two plates.

WLOG, Lets say we are on day i which is a perfect power of 2

and

we have a plate with capacity 2*i full of (i-1) fruits corresponding to previous i-1 days. 

Let it be P1. 

And we also have a empty plate P2 of 4*i capacity.

Now for each day, j , from day [ i - 2*i ),

- we will put 1 fruit of type 'j' in P1

- we will put 3 fruit, one of each type, which are not already present in P2.

- we will present P1 on each day

As we will have i days in between 2i and i and each day we have capacity to put 3 fruits in P2, So for sure, by the end of 2i th day, we would have added all 2*i fruits in P2.

Now For iteration from 2i to 4i,

P2 <--- P1 
we will have new empty plate with capacity 8*i as P2

Looks at implementation for better understanding.

Code

CodeChef Solution Link