Here was my thought process:

Started with a naive solution (recursion): At each step, we can do one of three things: - Accept the current sum and stop the process - Reverse the array - Replace the array with its diff (as explained in the problem statement).

This worked, but is super slow, so let's see how we can optimise it.

First observation, since the length of the input array is 50, we can replace the array with its diff at most 49 times (specifically, at most n-1 times), after that, we can no longer make any move.

Second observation, reversing the array twice consecutively is worthless, as it will have no effect on the result.

From these observation we conclude that we are looking for a sequence of operations such that there is never 2 consecutive reversing, and no more than n-1 diff operations. So it should look something like this: [R,D,D,D,R,D,...] (R for reverse, D for diff).

Notice that an R must be followed by a D.

Now notice the following: Say we have an array [a1, a2, a3, a4], if we do diff directly, we get [a2-a1, a3-a2, a4-a3], if we do reverse followed by diff, we get [a3-a4,a2-a3,a1-a2].

What do you notice? We got the same elements, but multiplied by -1.

It means that if doing diff eventually gives us a solution X, then doing reverse then diff should give us a solution -X.

So now we can reduce the recursion complexity a lot, because we only need to discover one of the two branches, the opposite branch is just -1 * the first one.

Thus, we can simply do the following: At each step, check the current sum, then compute the diff and do recursion to get a return R. Finally, return max(sum, abs(R)).

thanks..

I already found this amazing post and was reading it and it seems to work.

Does it mean that we should always use map in cpp in competition?

While using unordered_map with custom hash worked for problem B, it doesn't seem to be faster than the map implementation in any sense

Why using unordered_map in problem B gave TLE on testcase 14!!!!

Replacing it with map worked...

my solution passed prestests, but failed in system testing.. this is awful

https://codeforces.me/blog/entry/137621?#comment-1233115

First, the optimal strategy is to always re-arrange b so that the relative sort order is identical to that of a.

In other words, the maximum item of b should be at the same position as the maximum item in a.

This will guarantee the defined product P to be maximised.

Rearranging b initially to fit into this condition can be done using sorting (sort both arrays while keeping track of each item's initial index).

After doing this, calculate the initial value of P.

After that, each time an operation happens, we need to rearrange b to fit the condition. The trick is that we don't need to do sorting again. It will be sufficient to swap at most 2 items to get the new optimal arrangement.

To make things easier, let's first sort both arrays, keep track of the initial index of each item in map (or array), call this index_mapper_a, and index_mapper_b respectively.

In other words index_mapper_a[i] = the index of the ith item of a in the sorted version of a (same for index_mapper_b).

To give a concrete example: suppose a = [1,5,3,2], then a_sorted=[1,2,3,5] and index_mapper_a = [0,3,2,1]

index_mapper_a[1] = 3 because a[1] is placed at index 3 in the sorted array.

Now if we receive a query to increment the ith item in a. We first need to retrieve the position of this item in the sorted array. We can do this using index_mapper_a. Let's denote x = index_mapper_a[i]. We need to increment a_sorted[x]. This might ruin the sort order. We need to fix the position of the incremented item in the sorted array.

If x == len(a)-1 or a_sorted[x] <= a_sorted[x+1], then a_sorted[x] is still in the right place (i.e. the sorting is preserved).

Else, we need to find the new position for it. We know that a_sorted[x+1:len(a)] is already sorted. So we can simply do binary search to find the new position of the incremented item. We should binary search for the first item Y in a_sorted[x+1:len(a)] such that Y >= a_sorted[x] (after incrementation for sure), we should then place a_sorted[x] just before that item. We can do this simply with a swap.

Example, if we had [1, 2, 2, 3, 3, 3, 5]. Let's say we had to increment the fourth item. We will get [1, 2, 2, 4, 3, 3, 5]. We binary search on [3, 3, 5] for the first Y such that Y>=4. We get 5. So 4 should we swapped with the item just before 5. So we get a sorted array again: [1, 2, 2, 3, 3, 4, 5].

When doing these operations, you should pay attention to update the index_mapper_a.

Finally, when we obtain all these information, we can update the value of P very simply:

We need to remove some factor from P and add some factor to it based on which item we swapped a_sorted[x] with.

Some final notes: - The case where no swap is needed should be handled so that we don't remove/add a factor that shouldn't have been added/removed. - Adding a factor is done by multiplying the new factor with P. - Removing a factor is done by dividing P by it. - As we need the answer modulo m, we need to also apply inverse modulo using fermat's theorem and modular exponentation.

Check my implementation for more details.

A naive approach would be to do simple recursion:

long long predictLuckVal(long long l, long long r, long long k) {
    if (r-l+1 < k) return 0;
    if (l == r) return l;
    long long m = (l+r)/2;
    if ((r-l+1)&1) return m+predictLuckVal(l, m-1, k) + predictLuckVal(m+1, r, k);
    return predictLuckVal(l, m, k) + predictLuckVal(m+1, r, k);
}

This gives the correct result but is very slow. We need to optimise it.

Notice that each time we split the current interval [l,r] in 2 intervals with equal lengths, the operations done on the 2 intervals will be exactly the same in terms of splitting. The only difference between the 2 intervals we are doing recursion on is the values that we are adding.

Let's say we are recursing on two intervals of equal length (after a split). Call them L and R respectively.

First observation: the number of stars that will count to our luck score from L should be exactly the same as that coming from R (why? because both intervals have same lengths).

Second observation: for each star that is counted in from L, there is a star counted from R such that m (or m+1/2) is their midpoint. Call the star that we collect from L m1, and the one collected from R m2, then (m1+m2)/2 = m. To be precise, if the split came from an interval with odd length, the relation would be (m1+m2)/2=m, else it will be (m1+m2+1)/2 = m.

So do we really care what the value of m1 and m2 are? No. Because at the end we collect both, so we should add m1+m2 to our luck score. This is as simple as 2m (or 2m-1).

The solution reduces to only knowing the number of stars that we should consider in only one of the intervals obtained after the split.

The solution will be as follows: If the current interval has odd length, the answer is m + 2mX. If the parent interval has even length, the answer is (2m-1)*X.

Where X is the number of stars that count into our luck in only the left interval obtained after the split.

This gives a complexity of O(logN)

You can check my code for the implementation.

I can give an extra hint to help with this:

Let's take an array containing only -1 and 1

1 -1 1 1 1 -1 -1 1

Let's pick an arbitrary subarray (for example):

1 1 1 [1 1 -1] -1 1

The current sum in this subarray is 1+1-1 = 1 Now what happens if we try to expand the subarray from the left?

1 1 [1 1 1 -1] -1 1 => adds 1 to the sum (sum becomes = 2)

1 [1 1 1 1 -1] -1 1 => adds 2 to the sum (sum becomes = 3)

[1 1 1 1 1 -1] -1 1 => adds 3 to the sum (sum becomes = 4)

What do you notice? If we can get the sum from 1 to 4, we necessarily have subarrays that give a sum of 2 and 3 (any integer between 1 and 4).

This is correct because as we expand the subarray from any side, we will either add 1 or subtract 1. Thus, if, starting from sum = x, we can achieve sum y by expanding the subarray from either sides, we will get all integers between x and y as sums along the way (here I am supposing y>x, but it also applies if y < x for sure).

So to sum up...

If we know that we can get a subarray with sum X, and a subarray with sum Y, then we are guaranteed to have subarrays with sum X, X+1, X+2, ..., Y

Thus... if the array is only composed of 1's and -1's, the different sums that we can get can be obtained by determining the smallest subarray sum, and the largest subarray sum. The result will be the set of every integer between the smallest subarray sum and the largest subarray sum (inclusively).

Finding the largest/smallest subarray sum is a classic dp problem that can be solved in O(N)

I don't think that it is not optimal to mix up 1 and -1

Consider this example:

1 1 1 -1 1 1 1 1 1 1

If you don't mix -1 and 1, the max sum you can get is 6. But this is not correct because we can get a sum of 8 by adding up all the items.

Hint 1: what would be the solution if abs(x)=1 for every x in the array?

Hint 2: now suppose that there is exactly one x in the array such that abs(x)!=1. X can split the array into 2 arrays (possibly one of them is empty). You can apply the solution found in Hint 1 to each array of them. This will include in the solution the sums of all subarrays not containing x.

Hint 3: Once you got the sums of all subarrays not containing x, you still need to get the sums of sub arrays containing x and add them to the solution.

Hint 4: Each subarray containing x is composed of a subarray starting from x, and a subarray ending at x. The sum of the subarray is the sum of the sums of both subarrays.

I hope these hints are useful. I tried not to be super clear to avoid giving you the solution directly. If you need more explanation let me know

Yes you are definitely right, thanks for correction. I missed this point. But the algorithm still applies however.

First notice that max(MEX) will never be less than 2, since no matter how we assign weights, there will always be some pair of nodes (u,v) such that the path from u to v has the edges bearing the weights 0 and 1. In short, max(MEX)>1 for any tree configuration or arrangement of edge weights.

Now that we know that max(MEX) is at least 2, we can simply find the edges having one of their extremities as a leaf, and assign to them the least unassigned weight starting from 0. That is, if we have k leaves, surely k<n, assign the value 0,1,2,3,4,...,k-1 to their corresponding edges.

Note that a node is a leaf if and only if its degree is 1 and thus we only have one edge issued to a leaf node.

This way of distribution of weights ensures that there will never be a path that contains the edges of weights 0,1 and 2 at the same time, since those 3 edges are all connected to leaves. Therefore we ensure that max(MEX)=2 , irrespective of the distribution of the weights left , that are: k,k+1,k+2,...,n

Not necessary, you can do it with simpler way.

First notice that max(MEX) will never be less than 2, since no matter how we assign weights, there will always be some pair of nodes (u,v) such that the path from u to v has the edges bearing the weights 0 and 1. In short, max(MEX)>1 for any tree configuration or arrangement of edge weights.

Now that we know that max(MEX) is at least 2, we can simply find the edges having one of their extremities as a leaf, and assign to them the least unassigned weight starting from 0. That is, if we have k leaves, surely k<n, assign the value 0,1,2,3,4,...,k-1 to their corresponding edges.

Note that a node is a leaf if and only if its degree is 1 and thus we only have one edge issued to a leaf node.

This way of distribution of weights ensures that there will never be a path that contains the edges of weights 0,1 and 2 at the same time, since those 3 edges are all connected to leaves. Therefore we ensure that max(MEX)=2 , irrespective of the distribution of the weights left , that are: k,k+1,k+2,...,n