Well, I can explain it rough. The thing is that there are $$$O(n)$$$ (actually at most $$$2n$$$) endpoints of these segments (the second case) and $$$O(n)$$$ (at most $$$n$$$) sums of kind $$$a_i + a_{n-i+1}$$$ (the first case). And the idea is that you are only interested in these $$$3n$$$ points (maybe with some adjacent points also). This is because in other points values of $$$pref$$$ and $$$cnt$$$ don't change at all. So you can compress coordinates and then just consider all segments as events going from left to right and changing the value of $$$pref$$$ correspondingly and store $$$cnt$$$ in some logarithmic data structure like map in C++.

video editorial of D. Click here

Because I think compared to the tutorials solution it is much simpler code here a link to a submission 77584565

Why? I'm precalculate three (actually two) parts on $$$O(n+k)$$$ time and then iterate over all possible sums in $$$O(k)$$$ with getting precalculated values in $$$O(1)$$$ time.

We first precompute the needed pref[] and cnt[] in O(n+k) so when we repeat the procedure for each possible x we can use the precomputed elements in O(1) making overrall complexity O(n+k)

UPD: Just noticed the question has been answered by vovuh

your code will WA answer for the test case 1 5 5 3 1 5 10 5 6 100 80 3 2 1 2 1 4 5 4 5 3 answer is 32 your code is giving 101 means that here you will go from a to b then from b to c via a that will give minimum answer

Here a test case that resembles the graph of 2nd example in the problem.

1 7 9 1 5 7 3 3 5 10000 10000 10000 10000 10000 10000 1 2 1 3 1 4 3 2 3 5 4 2 5 6 1 7 6 7

The optimal output should be 1->7->6->*5*->6->7 then you assign these prices 5,3,3 to get the answer as 5 + 2*(6) = 17.

You cannot do the question on basis of only considering shortest from A to B and then shortest from B to C separately. Consider smallest path from A to B(length s)and there is another path from A to B(length s+1)which has only one more edge then the smallest one.Suppose that path contains C, so that is more advantageous and we need only smallest s+1 prices while with the shortest path we will need then s+k prices (k distance of B from C).

Thank you everyone for helping me figure out my mistake. I really Appreciate it

I guess,it is because of the data type the value overflows so try using long long.

keep it up bro

same here bud, keep going

Since the segments have endpoints at $$$2$$$, $$$3$$$, ..., $$$n$$$, at each iterative step you are actually picking the segment that is with endpoint $$$1$$$ greater than the segment you previously picked. There is exactly $$$1$$$ valid segment in each step, which means the reconstruction is unique if an valid permutation exists for you fix of first element.

Finally, someone's asking the real questions :P

here we follow the path: a->x->b->x->c

for every vertex x <= n, find the shortest distances from a to x, b to x, and c to x

since b->x is common, we should distribute minimum weights along this path. Let prefix(i) be sum of i smallest weights.

So the answer will simply be prefix(distance(a to x) + distance(b to x) + distance(c to x)) + prefix(distance(b to x))

don't go for F now just focus on A,B,C of div2 and A,B,C,D of div3... i am saying this because of my experience in compi beleive me or not i am saying this for your good... keep it up mate....

See for any particular sum(say x), prefix[x] is having number of pairs that need at most 1 element to be changed. Since for any pair we can make any sum(ofc less than 2k) by changing both the elements so if we have n/2 pairs in total and prefix[x] is number of pair that need at most 1 change so n/2 — prefix[x] is number of pairs which needs both the elements to be changed.

That's because the ones we calculated prefix for are the ones who can reach that x by replacing one element. Thus by subtracting prefix(x) from n/2 and multiplying it by 2 gives us those pairs where we have to change both elements.

Have a look at my submission. I have added comments.

https://mirror.codeforces.com/contest/1343/submission/77603570

Part 3 includes those pairs in which we have to change both values to get the desired sum. Since prefix(x) contains the count of pairs in which we have to change one or none value, hence (n/2)-prefix(x) gives the third part.

I did the same mistake and got the same WA on the same test case :D. The problem is that you are assuming that the shortest path from a->b->c will comprise of shortest path a->b and shortest path b->c, which is not true..

Since each element of the array lies between 1 and k, the range of values [min(a[i],a[n-i+1])+1,max(a[i],a[n-i+1])+k] will include the pairs for which the sum equals x as well. Hence pref(x) represents the pairs for which AT MOST 1 needs to be changed. n/2 is the total. Subtract pref(x) from it, we will get the ones which require both elements to be changed. Final equation we need number of changes = (at most 1 change required — no changes required) + 2*(number of pairs which require both elements to be changed)

Last term multiplied by 2 because 2 elements are changed.

It is on of the popular techniques, it can update in O(1) time and changes are accumulated at the end by calculating the prefix sum.

The range is updated using the index bounds. Consider you want to update the range [l,r] then that can be done adding the +1 to the left bound and -1 at the right corner. So whenever you would be calculating the final results, the following thing happens -:

1. The +1 is propagated in the range [l, r] since you are adding the previous element to the present element.

2. The -1 handles the stopping case at r + 1 and now the +1 is neutralized by -1.

Once this array pref is generated, you are now with sum values which would require just a single modification to reach sum.

Since the answer for this overall problem will be :

1. The number of pairs in which both elements need to be changed.
2. The number of pairs in which a single element need to be changed.

For the 2nd one, cnt[i] (already having the sum of i beforehand) — pref[i] (which need one element modificationto reach sum i)

For 1st one, the remaining pairs will be the one with 2 modifications, (n / 2) (Total pairs) — pref[i] (sum with one modification to reach i).

Multiplying it by 2 since two modifications are required.

Now try to calculate minimum by iterating over all the possible values of sum [2, 2k].

Sorry for the bad representation. I hope it helps.

for any pair a[i] and a[n-i-1] we can make it equal to some sum x by changing at most one element a[i] or a[n-i-1] if sum x is in range min(l1,l2) to max(r1,r2). but as sum goes to max(r1,r2)+1 we need to change two elements

we are calculating prefix sum because above argument follows for all sum values that are in range min(l1,l2) to max(r1,r2)

i got the idea of d and u i.e ranges starting and ending before and after x but can u please explain how did u conclude get =min(d,u)

You can ignore overestimates, because it can be shown that vertices that cause overestimates are never the optimal choice for intersection.

A very rough "proof": if the editorial's algorithm assigns more than one cost to a set of edges and thus overestimates the cost, it means that at least two paths among $$$x \rightarrow a, x \rightarrow b,$$$ and $$$x \rightarrow c$$$ overlap. The overlapped edges would form a path from $$$x$$$ to some other vertex $$$y$$$. In this case, $$$y$$$ is always a better choice of intersection.

It is in queue, wait for the system testing to get over.

I built a vector that holds the minimum value every pair can take with one change, and a vector that holds the maximum value every pair can take with one change. Fix a target 1 <= x <= 2k that you want every pair to equal after your changes. The number of pairs whose min is > x will require 2 changes, as will the number of pairs whose max is < x. You can binary search for the number of pairs that fulfill these conditions, using something like lower_bound(mins.begin(), mins.end(), x). You'll can also see that a pair cannot fulfill both of these conditions simultaneously, so we don't double count.

It's in queue. Wait for a while

Because currently the system test are running, just wait some half an hour.

we have our prefix sum array of size M it is practically impossible to have more than M distinct edges weights so This condition is applied to control indexing error If You don't apply it will give you an out of index error for some cases :)

You can check this soln by Ashishgup https://mirror.codeforces.com/contest/1343/submission/77496545

The given array will consist of some positive and some negative elements. An alternating subsequence will consist of alternating elements (pos,neg,pos,neg... or neg,pos,neg,pos.... and so on). you need to take the max length of alternating sebsequence and find its sum. Remember there could be multiple such subsequence of max size but you need to print the max sum among all.

In the example {6 1 1 7 6 3 4 6}, K = 7. the sum values are 12, 5, 4, and 13. But you get minimum when u make x as 7 or 8 or 9 or 10. So the logic of only checking for sum fails.

do you like want downvotes or something? Please format your code

During the contest, not all test cases are run. You would have got the correct answer for the tests that were run during the contest. After the contest was over, when all test cases are run, there must be some test cases in which your code didn't run in time. Changing long long to int would have solved the problem because computation on integers takes about half as much time as computation on long long integers. This is because in some machines, the size of the CPU register is 32 bits and long long takes 64 bits. I think it is also dependent on the compiler but not sure.

It can be solved even in $$$O(n^2)$$$ https://mirror.codeforces.com/blog/entry/76306?#comment-608280

vovuh Maybe you want to mention that there is a $$$O(n^2)$$$ solution

plz organizers revert to this vovuh[user:vovuh]

This algorythm simply does not give the optimal assignment.

You would not have to find the shortest route from b to c, but instead the shortest path from any vertex in path from a to b, to c. But considering that the part from that vertex to b counts twice. So you end up with the turorials solution.

in this prblm if we print n itself then it should be correct na ??? because for k = 1 --> x == n always satisfy the solution .

theres nowhere written that x can't be n .

use this test case draw on paper and think why it failed. I was facing exactly the same issue.

1
6 6 1 5 6
1 2 3 4 10000 20000
1 2
2 3
3 4 
4 5
2 5
2 6

I got it. sorry i bothered you

let {a[i],a[n-i+1]} be the pair of elements, then whats the minimum sum of this pair possible by replacing at most 1 of the two elements so the operation cost is 1, so we will take the minimum of the two pair unchanged and will change the maximum of the pair to 1 as the minimum number we can replace to is 1. So it becomes min(a[i], a[n-i+1])+1. Hope it helps.

Can you please help me what is wrong in my solution for D (Brute Force), I'd be grateful:

#include<bits/stdc++.h>
using namespace std;

int numberOfChanges(vector<pair<int, int>> v, int k){
    int sum= 0;
    for(int i=0; i<v.size(); i++){
        if((v[i].first+ v[i].second)==k) sum+=0;
        else if(v[i].first >=k && v[i].second >=k) sum+=2;
        else sum+=1;
    }
    return sum;
}

int main(){
    int t;
    cin>>t;
    while(t--){
        int n, k;
        cin>>n>>k;
        int A[n];
        for(int i=0; i<n; i++){
            cin>>A[i];
        }
        vector<pair<int, int>> v;
        for(int i=0; i<n/2; i++){
            v.push_back(make_pair(A[i], A[n-i-1]));
        }
        int count, min_count=INT_MAX;
        for(int i=2; i<=2*k; i++){
            count= numberOfChanges(v, i);
            if(count<min_count) min_count= count; 
        }
        cout<<min_count<<"\n";
    }
    return 0;
}

Let the paths $$$a = v_1 ... v_n = b$$$, $$$b = v'_1 ... v'_m = c$$$ be optimal. Choose minimal $$$i$$$ such that $$$v_i \in {v'_1 ... v'_m}$$$, say $$$v_i = v'_j$$$. $$$i <= n$$$ since $$$v_n \in {v'_1 ... v'_m}$$$. Let $$$P_1 = (v_i, ... ,v_n), P_2 = (v'_1 ... v'_j)$$$. Let $$$rev(P)$$$ for path $$$P$$$ be the reverse of that path.

There are cases:

$$$P_1 \not = rev(P_2)$$$. WLOG say the length of $$$P_1 \geq $$$ length of $$$P_2$$$. Then we can replace the $$$ab$$$ path with $$$v_1, v_2 ... v_{i - 1}, rev(P_2)$$$. This new $$$ab$$$ path is not longer then the old $$$ab$$$ path so we can do this.

$$$P_1 = rev(P_2)$$$. Then take $$$x = v_i$$$ and we have paths $$$a \rightarrow x$$$ is $$$v_1 ... v_i$$$, $$$x \rightarrow b$$$ is $$$v_i ... v_n$$$, $$$b \rightarrow x$$$ is $$$v'_1 ... v'_j$$$ and $$$x \rightarrow c$$$ is $$$v'_j ... v'_m$$$.

I post a reply to someone below. Hope you work out the problem after seeing my post. Thanks very much.

Because the length of p is m, so the length of the array containing prefix sum of p is m. You may get runtime error if dist(a,x)+dist(b,x)+dist(c,x) is greater than m

x->c can have edges which are common with x->a or x->b . If it's x->a, then we have 2 cases: 1) x->c has all edges from x->a (path is x->a->c and common edges are the edges from x->a) or 2) there is some point y in between 'a' and 'x' such that the edges from x->y is common (i.e x->y->c, a->y->x and common edges are the edges from y->x). In the first case, if 'x' is not 'a', then having x=a will always give better answer as x->a +x->b + x->c will be smaller and you have a longer prefix x->b. In second case, you can have x=y which will give a smaller answer because of the same reason mentioned above. Similarly, you can work out for edges which are common to x->b. The point is that the algorithm will find surely find the optimal answer (x=a or x=y in above case) if there exists one.

This is the function that returns the "sign" of an integer. +1 for positive X, -1 for negative. You can google it: https://stackoverflow.com/questions/7951377/what-is-the-type-of-lambda-when-deduced-with-auto-in-c11