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.

We are going to arrange a programming contest. Hope you will find it Educational. This contest is suitable for below EXPERT on codeforces

SPC round 65

This Friday, 7 September at 9:00 pm (Bangladesh standard time).

Duration : 2 hour

Contest link : here

tourist became Tourist !!!

But once I caught anotherTourist !

The contest link is here.

EDITORIAL :

SONAMONIDERPROGRAMMINGADDA :

Tutorial : The greedy part of the problem is you can make string S any of it's permutation. So, You just sort the given string and "SONAMONIDERPROGRAMMINGADDA" string , after sorting if both of them are equal then it's yes possible otherwise not.

Time Complexity : O(|S| log |S|)

Space Complexity : O(|S|)

C++ Code

Alice wants to win :

Tutorial : Alice will win only if the number of moves becomes odd. Now imagine a number _n >= n and _n is multiple of m. Now , the game will progress like n → _n → 0. In this way if you get odd number of moves then it's yes Alice wins. Otherwise the moves is even. now, you can go one more multiple of m. In this way if you go n → _n + m → 0 then parity of move will only change if m is even. Because if m is odd then you move odd times forward and one time backward. ultimately the parity will not be changed. So, now just check if m is even then moves parity will change and you can say yes otherwise there's no way to make your moves count odd.

Time Complexity : O(T)

Space Complexity : O(1)

C++ Code

Diagonals on a board :

Tutorial : In the sample testcase description you will find that 2*n-1 diagonals are available for n*n board.

Time Complexity : O(T)

Space Complexity : O(1)

C++ Code

Free Diagonals on a board :

Tutorial : You can use binary search to find maximum free diagonals. Imagine a mid for the free diagonals , then calculate calculate minimum possible amount of cells holding these diagonals so that maximum buttons can be kept other cells . To calculate this you can choose a greedy part that the cells amount series looks like 1, 1, 2, 2, 3, 3, ...... n-1, n-1, n. From this series you should pick first mid elements sum. Then occupied cells will be C = n*n — sum of first mid elements. You can make equations for the sum of first mid elements. Now if C >= K , then mid diagonals are enough to keep their all cells empty. sol go for right segment for more free diagonals otherwise go left.

There's one corner case, The n can be equal to 0, in that case answer shouldn't be -1, answer will be 0. It's silly harassment though.

Time Complexity : O(T*log N)

Space Complexity : O(1)

C++ Code

Searching more AND :

Tutorial : For every bit 33 to 0 you just calculate AND of all elements in this way : if the bit is off for ith value upadate current AND by AND operation with (A[i] + k) otherwise just update current AND by A[i]. For all 34 different AND , the maximum AND is the final answer.

Time Complexity : O(N * 34)

Space Complexity : O(N)

C++ Code

360 Clock :

Tutorial : Maintain a set of elements that represents the all possible positions where you are just before the current move. As there are at most 360 positions , so the size of the set must not exceed 360. For every position , update all positions with +A[i], and -A[i]. If there were X positions just before this move, now 2*X positions will be after the current move. But as you maintaining a set of size 360. The set size will never get more than 360. Always do not forget to keep the positions inside [0, 360) by mod with 360.

After all N moves print the set size and all the positions.

Time Complexity : O(N * 360)

Space Complexity : O(N * 360)

C++ Code

Fever is called Jor not Xor :

Tutorial : This is very basic problem on Trie. You need to keep track on 33 bit to find the answer for the current position while going with pre Xor and update the bits for pre Xor on the Tree. For all maximum answer between 0 to i the maximum value is the answer for the ith index. You can maintain a dp array to keep track the maximum of the back. You can find a related helpful video here.

Time Complexity : O(N * 33)

Space Complexity : O(N * 33)

C++ Code

Substring of string

Tutorial : You can create a rolling hashing structure to get substring hash. and match any substring of S with t in o(1). Just go from 1 to |s|-|t| and check if the hash of substring [i, i + |t|-1] of s is equals to hash of string t then count one more. You can also solve this using KMP algorithm and Z-algorithm.

Time Complexity : O(|s| + |t|)

Space Complexity : O(|s| + |t|)

C++ Code

For further contest updates you can follow our facebook page here.

We are glad to share that we are going to arrange a programming contest. This contest is suitable for those who are below EXPERT on codeforces.

In this round , the problem setters are : piyash_basak , FahimR and mahfuzswe

I hope you guys take part in this contest and support us for our little efforts.

Contest Link : Click here

Contest Time : 23 August at 21:00 (Bangladesh Standard Time)

Duration : 2 hours 15 minutes

Hope you find all the problems interesting and difficulty will not be sorted. I apologize for any kind of mistakes if we do. Thank you.