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.
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.
Diagonals on a board :
Tutorial : In the sample testcase description you will find that 2*n-1 diagonals are available for n*n board.
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.
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.
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.
