Can you please send them another mail? I will ask them to check it up asap. These things shouldn't be happening at all!!

It's enough for segments of lengths 2 and 3 to be valid, longer segments can be split up to these ones. And now it's just dp[N][2][2] of position, sign of previous number and sign of the number before it with state being the smallest sum you can achieve.

Here's an alternate approach, using 1-D dp and segment trees, probably a bit too overcomplicated:

First observation: any element can only be multiplied by  - 1 is it is strictly smaller than both its neighbours (segments of length 2 must be valid, to quote the other answer). From now on, by 'valid position', I will mean a position which can be multiplied by  - 1.

Let suf[i] denote the suffix sums of the array. Then, the sum of some range [l, r] of the array can be calculated as suf[l] - suf[r + 1], and sum of the whole array is just suf[0].

Let dp[i] denote the best possible answer till position i, with the condition that position i is multiplied by -1, and nothing after i is (and of course, array is valid). dp[i] = suf[0] if i is not a valid position.

Second observation: When calculating the answer for a particular i, only the (valid) positions before it matter, since everything after it has a constant contribution to its answer being always positive.

This gives us a simple recurrence for dp: dp[i] = min(suf[0] - 2a[i], min(dp[j] - 2a[i])) = min(suf[0], min(dp[j])) - 2a[i] where 1 ≤ j ≤ i - 1 and the sum S =  - a[j] + a[j + 1] + ... + a[i - 1] - a[i] is positive. (do you see why we don't need to bother about any other segments?)

Third observation: S = S + suf[i] - suf[i] + a[j] - a[j] = (suf[j] - 2a[j]) - (suf[i] + a[i])

Notice now that we essentially want the following: minimize the value of dp[j] across all positions j such that suf[j] - 2a[j] > suf[i] + a[i]; where the right side is just a constant once i is fixed, and the left side depends purely on j. This can be done fairly simply using a segment tree, and at the end, we can just find the minimum value of dp[i] across all valid i, and this is our answer. Reconstruction of the answer is also simple by simply storing extra data at each node.

(If the segment tree part is not obvious, think about this problem: given N points (x_i, y_i) in the plane, and some number k, find the minimum value of y_i across all pairs (x_i, y_i) such that x_i > k.)

My implementation.

Problem Rubber requires to check whether a polygon in the plane minus some points (the nails) is homotopic to zero or not. An algorithm to do so can be found in Theorem 3.22

Rubber: The problem started to make sense after I saw this test case:

(The point is we can't look at just a single nail at a time to make conclusions. (Also 2 nails are not enough either if we extend this test case, we need many.). The solution is folding together 3 points into 2 points whenever doing that doesn't intersect with any nails. We also add extra points to avoid cases where it get's stuck, like this one.)

Sersum: No need for interpolation, but a lot of googling and FFT. (Too hard to explain in detail, just giving hints):

1. Use Faulhaber's formula

2. We can speed this up for multiple k, if we use FFT (B_k together with k! and x^(p-k+1) together with (p-k+1)!)

3. We can calculate the Bernoulli numbers in O(k^2) which takes about 1s out of given 6s.

4. If we have multiple x, we can just add them together in the Faulhaber's formula before FFT

(Now we need to solve a different problem: given an array, calculate the sum of k-th powers of it's elements for every k in [0,K])

1. Use Newton sums

2. If we construct polynomial (x-a_0)*(x-a_1)*...*(x-a_{n-1}), then it's roots are our array, so it fits nicely into Newton sums. (We can calculate the coefficients of this without interpolation, just divide and conquer multiplying left half and right half with FFT).

3. We can calculate Newton sums faster, if we do something like "sqrt"-decomposition with FFT. So calculate first 10000 S_i in the naive way, then FFT them together with the coefficients. Same with next 10000. That is all we need to fit into 6 seconds.

First, let assume a[i][j] = a[j][i] (if not, we will spend some cost to make those two equal).

For all graph, it is possible to build a tree such that the minimum cut between any two vertices in that tree is the same with the minimum cut between those vertices in the original graph (such tree is called Gomory-Hu tree). So, the task is reduced to: Build a tree such that sum of a[i][j] - minE(i, j) for all pair of (i, j) is minimum (minE(i, j) mean the minimum weight of the edges on the path from i to j).

This can be done greedily by iterating over all pair (i, j) in decreasing order of a[i][j] and add edge (i, j) into the tree if i and j are not connected yet (similar to Kruskal's algorithm).

My implementation

Okay, since nobody tells their solutions, I might share some ideas, at least. I solved only the easy subtask but still.

Firstly, the task asks you the following thing. You take an edge e₁ from the first tree, insert it into the second tree, take all the other edges on the cycle produced by adding e₁ and calculate the number of them which produce such a cycle in the first tree that e₁ lies on it. I won't mention cases with coinciding edges, they are trivial.

The latter check can be done in O(1). With either some cases with tins and touts or segments on eulerian traversal. Here is the approach in O(n²) using the second idea.

Now you should remember that you can choose some segment on eulerian traversal that it contains all the edges on the path between v and u odd number of times and other edges — even number of times (0 or 2, of course).

So if we learn to extract only the first ones then we can make queries on segments for the first cycle check. The first thing that came to my head was Mo's algorithm. It's easy to maintain the number of times edge appears on some segment. We just need such a structure that can count the number of segments (a, b) such that given some (x, y), exactly one of x or y appears in that segment. When we add or remove edge (move border) we make an update operation on 2D-BIT :D Okay, what does it store. It stores segments in form of points on a grid, get operation just calculates the number of points of some prefix-rectangle. That was the last solution I wrote. It is and TLs even the first subtask :D

I believe I have an idea how to get solution of it. Still, I don't really think I can implement it in such a way that it fits into TL.

Straight up implementation. And such an ad-hoc one.

You should probably notice that there is only one path binary search can take to reach some position. The rest is just greedy ideas compressed into a couple of ifs.

Define goal number as the number that you want to reach to. Start binary search in a normal fashion i.e from indexes 0 to n-1. Also keep 4 integers cl,cr,okl,okr.

Case 1:- The goal number is to the left of the current index. The number at the current index also leads to the left. Increment okl.

For eg:- The number at current index is 7 and goal number is 1 present to the left of 1. The number 7 will lead you to left and goal is also to the left.

Case 2:- The goal number is to the right of the current index. The number at the current index also leads to the right. Increment okr.

Case 3:- The goal number is to the left of the current index. The number at the current index leads to the right. Now we need to swap a number with this current index that will lead to the right. The nature of the number should be such that it is less than the goal number. Increment cl.

Case 4:- The goal number is to the right of the current index. The number at the current index leads to the left. Now we need to swap a number with this current index that will lead to the left. The nature of the number should be such that it is more than the goal number. Increment cr.

Now okl and okr are the numbers that are fixed and do the work for us. We don't need to swap them. However cl and cr are the smaller and greater numbers that we need. Try to see if we have enough of them (by excluding okl and okr from total_smaller_numbers and total_greater_numbers than goal number respectively). Also we can swap the numbers such that 1 cl and 1 cr number is adjusted in one swap only.

For implementation:- Code