The Contest link is : here

EDITORIAL :

Simple Game:

Intuition : For this problem , it can be proved that for any number not having length 2 , you can make any digit to remain last digit. So the minimum digit of the number is the answer if the number is more than 9 and less than 100, the last digit will be the answer as alice has only one possible move.

For more than two digit, keep the minimum digit in the second position, and do operation on other positions. When the minimum digit comes at the end then swap it with the first number. In this way Alice can make the minimum digit as answer.

Time Complexity : O(T log N)

Space Complexity : O(1)

Code : here

Two Jar:

Intuition : The jar who contains maximum kg of food is the answer.

Time Complexity : O(1)

Space Complexity : O(1)

Code : here

Make more Profit:

Intuition : Suppose you are selling the book on i-th day (1 <= i <= n) , then you should buy the book the minimum costs of x-th day (1 <= x <= i) . Then you get maximum profit for selling i-th day. The profit will be A[i]-A[x]. SO, for every i (1 <= i <= n) we have to find this profit and the maximum profit among them is the answer. So we go through i from 1 to n and update a minimum value and calculate the profit.

Time Complexity : O(n)

Space Complexity : O(n)

Code : here

A pond of Lotus:

Intuition : We saw that the lotus becomes double for every night. So, from one lotus, we found X amount of lotus where X is a power of two. Now we have to find minimum k where N = X1 + X2 + X3 + …… + Xk. In bit manipulation we know that the number who is power of two has exactly one set bit. So, if N has M set bit then this M will be the minimum possible k that earlier I mentioned. So count of set bit of N is the minimum number of Lotus you have to buy. Then k * P will be the minimum taka you need.

Time Complexity : O(T log N)

Space Complexity : O(1)

Code : here

Mex of subarray:

Intuition : You have to use contribution technique for this problem. Firstly keep track of the posititons of all the elements. Them go through value 1 to n , calculate their contribution on the answer. Let’s calculate contribution for x (1 <= x < n) . Let’s say The number of subarray that’s MEX is x is equal to C. Then x contributes C times x to our answer. Let’s see how we can calculate. We kept all the position of value 0 to x — 1 in a set. Now, find a segment [L, R] with minimum distance or R-L such a way that all positions of value 0 to x-1 remains >= L and <= R. The L is actually minimum value of the set and R is the maximum value of the set. We can get this with logarithmic complexity from set.begin and –set.end . To make x as a mex for any subarray starting form l and ending at r, we need to cover the segment [L, R] by [l, r] as the values 0 to x-1 remains in segment [L, R]. So, we can say that l <= L and r >= R. If the position of x is greater than L and smaller than R , we can not get any subarray that makes mex = x. So , we can skip there, but if x is smaller L or x greater than R then we should calculate C . C is number of subarray [l, r] that covers [L, R] but not covering position of x, as we want x as mex.

If position of x < L then possible l are L-pos[x] and possible r are N-R+1.

If position of x > R then possible l are L, and possible r are pos[x]-R. 

Then the C = possible l times possible r. And contribution of x = x times C. After calculating for the x, update the position of x to your set.

Time Complexity : O(N log N)

Space Complexity : O(N)

Code : here

We are open , We are looking for Problems:

Intuition : This is very basic dp problem . If you calculate the beautiful names of type — Z or Type — A then it’s enough. Because Type — A and Type — Z has equal number of beautiful names. But there are 26 common names which is also type A and Z. those are n equal character x, a <= x <= z. So, calculating only Type — Z is enough.

To calculate the Type — Z, use dp of n times 26 states. For every position, keep track what was the character of the following previous position. If the previous state was character x (a <= x <= z) then try to keep the character y ( x <= y <= z) in the current position and move forward and calculate. Make sure you calculate for all possible length before test case to cover in time limit.

Time Complexity : O(26 * N)

Space Complexity : O(26 * N)

Code : here

Thanks for your participation of the SPC Round 65. Hope you enjoyed this round.

You can follow us on facebook for next contest update here.