A. You should iterate over all dices from up to down and restore answer. You can easily find number of the bottom side of the 1st dice. Using known sides of the 2nd dice you can find pair of numbets on top and bottom side of the 2nd dice. If one of them equal to number on bottom of the 1st dice, you can restore all numbers on the 2n dice. Then using this idea you can try restore numbers on the 3rd dice and so on. If you restored all numbers, you should write YES. If for some dice you cannot uniquely determine order of numbers on the top and botton sides, there will be at least 2 placing of numbers. In this case you shoyld write NO.

Author is Ripatti .

B. Firstly you should generate all k-bonacci numbers less than n. For k ≤ 32 you can do it straightforward, for bigger k you can see that all k-bonacci numbers less 10⁹ are powers of two only (and 0). So you will have no more then 100 numbers.

Then you should use greedy algo. You should substract from n maximal possible k-bonacci numbers. You should repeat this operation while n is not decomposed. And in the end you will have answer.

Why all numbers will be different? One of possible proves:

F(k, n) = F(k, n - 1) + F(k, n - 2) + ... + F(k, n - k)

F(k, n - 1) = F(k, n - 2) + F(k, n - 3) + ... + F(k, n - k - 1)

You can substract the 2nd equation from the 1st one and you will recieve F(k, n) + F(k, n - k - 1) = 2F(k, n - 1), that equal to 2F(k, n - 1) ≥ F(k, n). This unequation also holds for n ≤ k.

Suppose than greedy also constricted 2 equal numbers F(k, x) in decomposition. But then in virtue of unequation we should take number F(k, x + 1) insead these 2 numbers. Сontradiction.

But you didn't need prove than greedy algo works, you might believe that it works:)

Authors are Gerald , Ripatti .

C. Firstly you should calculate number of white and black pixels in every column. After that you should calculate number of white and black pixels for every prefix in sequence of columns. Now you can calculate number of black or white pixels in every vertical line of any width in O(1).

Now you should use dynamic programming. Let's dp[i][j] will store numbers of repainted pixels in prefix from the 1st column to the j-th and color of the last column will be white for i = 0 and black for i = 1.

Than you can recalculate dp using forlulas: dp[0][0] = dp[1][0] = 0

Answer will be min(dp[0][m], dp[1][m]).

This solution works in O(nm + m * (y - x)).

Author is Ripatti .

D. There is just BFS. State is head place and mask that store place of tail: using 2 bits you can code position of every segment in relation to previous segment. Mask will contain no more than 16 bits, and number of all states will be no more than 4⁸ × 15 × 15 (also you can try understand that number of states no more than 3⁸ × 15 × 15).

Then you should just carefully implement it.

Author is Ripatti .

E. You have z = [x / 2] + y + xy. That is equivalent to

z = [2k / 2] + y + 2ky, where x = 2k, k > 0
or
z = [(2k + 1) / 2] + y + (2k + 1)y, where x = 2k + 1, k ≥ 0.

z = k + y + 2ky, k > 0
or
z = k + y + (2k + 1)y, k ≥ 0.

Still more steps:

2z + 1 = 2k + 2y + 4ky + 1, k > 0
or
z + 1 = k + 2y + 2ky + 1, k ≥ 0.

2z + 1 = (2k + 1)(2y + 1), k > 0
or
z + 1 = (2y + 1)(k + 1), k ≥ 0.

From the 2nd equation you can see than z should be 2^t - 1 because otherwise z + 1 will have odd divisor and we can build solution. From the 1st equation you can see that 2^t + 1 - 1 should be prime, otherwise we also can build solution. If z = 2^t - 1 and 2^t + 1 - 1 is prime, obliviously there are no solutions.

Prime numbers like 2^a - 1 are Mersenne primes. Only about 46 such numbers are found now. Powers of 2 for the firts 40 numbers you can find for example here.

Author is Ripatti .