One should note shashank21j is the organizer of this event, not the person you linked to.

Please note, that person is not related to hackerrank. If there are issues reply on this blog so I can track it.

I hope you understand.

Try now, is it ok?

I will enable that after contest ends and will take them down by surprise.

"solved 100%" on a day when you submit a solution don't actually mean full solution. Your solution is tested only on pretests when you submit it; at the end of the day it is tested on full dataset, and you know your actual score. If you open detailed results of judge, you'll see that some testcases are marked as "additional". Maybe your solution failed some of these "additional" cases for last problem, and this is the reason why your score decreased.

If things are still as they used to be, your problems go through a final test every day with additional test cases. So when you submit a problem and get 100% on the available instant test cases, this doesn`t mean your program will get 100% on the daily recorrection. You should probably check the problem you submitted yesterday to see if this happened.

So... the last submit counts, not the best one?

I sense a disturbance in the Force contest rules...

Bug? Will fix it. Also I'm thinking i will reveal time. It'll be exciting for last challenge.

Я писал два декартовых дерева — для чётных и нечётных индексов. Своп меняет местами середину одного дерева с серединой другого, сумма ищет сумму, что очевидно. А как решать декомпозицией?

Задача Swaps and Sum решалась двумя декартовыми деревьями — для четных и для нечетных индексов массива соответственно. Код: link

А вообще это дикий баян, интересно как он попал на раунд: такая же задача Код задачи на informatics.mccme.ru даже менять не нужно, чтобы он прошел (если не считать то, что нужно убрать мультитесты).

This problem is solvable using dynamic programming.

Let dp[i][j] be the number of good arrays, built from the first i elements with last element equal to j.We can easily calculate our dp in O(N^3) time:

From this formula we can get another one:

dp[i][j] = dp[i][j - 1] - dp[i - 1][j - 2]

This formula is almost good, but we don't know, how to calculate the base of our recurrent formula (case with j==2 or j==1). We can generate this values by hand and just google them :) It turns out, that answers for j==1 and j==2 (they are equal in the most of cases) can be expressed as the members of the Catalan's triangle, and there is a formula for calculating them. Specifically, this values depend from the value of the last fixed number in the array and from it's position.

Using this observations, we can solve our problem in O(n * maxA) time

Code

The first thing to do is to determine what a valid height sequence looks like. Let us think about it in terms of the dfs. Lets say at the current point in the dfs, we are at height h. The next entry in the array is either h + 1 (which corresponds to us moving to a child), or some value x, 0 < x ≤ h which corresponds to going back up the dfs callstack. Hence, a valid sequence will be composed of a series arithmetic progressions (of difference 1), where each arithmetic progression starts at a value less than or equal to the previous term. In other words, it will look like 0, 1, ... , e₁, b₂, b₂ + 1, ... , e₂ - 1, e₂, b₃, ... , e₃, b₄, ... where 0 < b_i ≤ e_i and b_i + 1 ≤ e_i.

Now the problem boils down to counting these sequences with some values already set. In order to do this, notice that the set numbers create a series of ranges which we can evaluate independently. A range is simply [i, j] where A[i] ≠ ? and A[j] ≠ ? and . To count the number valid sequences range, we convert it to a question on the cartesian plane. We are essentially counting the number of grid paths from (0, 0) to (A[j] - A[i] + j - i, j - i - 1) that do not go past the line y = x - A[i]. To see why this is true, think of each upwards step as moving down in the dfs tree, and each rightwards step as moving back up the callstack in the dfs. To solve this problem, we can use a trick called Andre's Reflection Method, which states than the number of paths from (0, 0) to (a, b) not going beyond y = x - k to be . The Wikipedia explanation of the method gives you a sense of how it works. Basically, it relies on the fact that the number of paths that are invalid is , because there is bijection between each invalid path from (0, 0) to (a, b) and every path from (0, 0) to (b + k + 1, a - k - 1), the later point being (a, b) reflected over y = x - k - 1.

You can do an sqrt-decomposition.

Split the array into blocks of even size, approximately . Each block can be viewed as 2 arrays, formed by even and odd elements respectively. If you apply a swap operation to a whole block, we can view it as moving these 2 arrays, one to the right and the other to the left (that can mean that an element has to be erased from one end and an element added to the other end); if we only apply it to a part of the block, we can process that block (depending on how it's been moving so far — essentially transform a deque into an array) and bruteforce the swaps made on it.

There are at most blocks to process in each query, at most 2 blocks to bruteforce (in time), so the time complexity is .

It sounds simple in theory, but (at least to me) it was long hours of debugging an ugly long code.