Problem - A

Problem Link

Simply check if S[0]==S[1]==S[2]

Problem - B

Problem Link

Simply keep calculating alcohol volume in your body and see when does it becomes strickly greater than x.

To avoid precision error use

X > (Y/100)  <==> X*100 > Y

code

Atcoder solution Link

Problem - C

Problem Link

In every subsegment it’s optimal to choose maximum value of x as x has to be less than equal to every value in segment. Hence maximum value of x in a particular segment in the minimum value in that segment.

Now, we can simply fix L and keep increasing R and update minimum on the go.

code1

Atcoder solution Link

We can also use sparse table and solve this problem in n*log(n)

code2

Atcoder solution Link

We can also use O(n) stack method by visualizing this problem as finding the maximum area in a histogram.

Link

Problem - D

Problem Link

It’s a simple dp

dp[i][0] = be the number of ways to get false after ith steps

dp[i][1] = be the number of ways to get false after ith steps

code

Atcoder solution Link

We can also do

if current operation is AND then to get true here we need to have true before, ans[i] = ans[i-1]

current operation is OR then if we put 1 here than we can have anything before and if we put 0 here then we need to have 1 before, ans[i] = ans[i] + 2^n

Problem - E

Problem Link

The way I did it that I created kind of linear equation:-

$ X_t^k $ be value of x-coordinate of kth point after t operations

$ X_t^k = Mx_t * x^k + Ax_t $

and similar for y coordinate.

$ Y_t^k = My_t * y^k + Ay_t $

Now, we could find Mx_t, Ax_t , etc after each operation then we are done.

We also need to maintain a variable S for each time stamp that tells do we need to swap x and y coordinates.

for Operation of type 1 :- (Mx * x + Ax,My * y + Ay) —> (My * y + Ay,-Mx * x - Ax)

        we need to swap (x,y)
        Mx[i] = My[i-1];
        Ax[i] = Ay[i-1];

        My[i] = -1*Mx[i-1];
        Ay[i] = -1*Ax[i-1];

we can form similar transition for all 4 operations.

code

Atcoder solution Link

A better solution is to use transformation matrix.

For rotation:

[X'] = [0 1 0 ] [X]
[Y'] = [-1 0 1 ] [Y]
[1] = [0 0 1 ] [1]

we can form transformation matrix for other opeartions too and then simply multipy these matrix.

Problem - F

Problem Link

Let’s first see if are in state s and future expectation number of moves are independent of how we got here.

So it’s better to process in backward order

dp[i] = Expected number of moves require to reach n.

dp[n] = 0

dp[0] = ans

Now, Lets first solve a easier verison where m = 0 or there are not any special cells.

dp[i] = 1 + (dp[i+1] + dp[i+2] + … + dp[i+m])/m

Now, in orginal problem all special cell leads us to first cell.

means dp[A] = dp[0] where A is any special cell.

so dp[i] = 1 + (sum of dp values of normal cell + number of special cells * X)/m

where X = dp[0]

at last we can solve linear equation

dp[0] = X = 1 + (sum of dp values of normal cell + number of special cells * X)/m

code

Atcoder solution Link