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|)
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*log(N+M))
Space Complexity : O(1)
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)
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)
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)
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)
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)
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.
Time Complexity : O(|s| + |t|)
Space Complexity : O(|s| + |t|)
For further contest updates you can follow our facebook page here.
