dev manus ( "GOD" for those who don't know Hindi ).

Thanks stefdasca

Please Keep Making Videos of Div2 Problems as well. They are very helpful. Thank you so much.

The video was quite nice. It is great to see that you made the videos while the contest was going on. lol :-)

for E, I was getting TLE for the same solution. UPDATE Ok i got it, my outer loop was running n times instead of k.

For E I implemented the same solution in Python. I get TLE on test 4. Are the problems not meant to be solved in python? Should I learn C++ instead?

Edit: Including submission link https://mirror.codeforces.com/contest/1353/submission/80416176

Thanks!!

F video editorial: Link

E video editorial: Link

D video editorial: Link

first index 0, second index the big number, and the rest is 0. u can't get any better than this (if u split it up, then ur basically splitting up the sum into two, but making the sums twice as plenty). so for all cases n>=3, u do 0, m, 00000000....

look for custom comparators c++ , useful stuff.

The final formula comes out to be n*(n-1)*(n+1)/3!!

Made a DP Solution for problem C .

Explanation , Code

I'm curious about that too.

This with counting sort instead:

https://mirror.codeforces.com/contest/1353/submission/80116286

It's possible but not neccessary

what he's trying to do is make a set with compare function, you can make a priority queue too.

COMPARE FUNCTION (class) EXPLAINED: It takes a pair as input(l,r) l = left index and r = right index . Then it sorts the pair in decreasing order of length( which signifies the length of zero sub array).

This helps us to always get the longest zero sub-array with ease, hence, we can solve the problem.

when it comes to why he used a struct for compare function, go through the link below.

https://stackoverflow.com/questions/16111337/declaring-a-priority-queue-in-c-with-a-custom-comparator

Consider the array [1,n] with initially all elements as zero let the interval [L,R] be defined as a part of array such that such all its elements are zero.Initially this part will be [1,n].Take std::set or std::map to store this interval. But the next interval which we will take should have maximum length and least 'L'; To do that we have to change the default sorting of set using comparator function. Then everytime we take the first interval from the set calculate the middle element and insert two new intervals in set [L,middle-1] and [middle+1,R] only if left<=right for this interval.If our set becomes empty at any instant then stop. Hope it helps

A little while after the hacking phase (12 hours) ends

It will change after 12 hours (after passing on whole test-sets and after hacking phase will end)

We decided to allow $$$O(n^3)$$$ solutions because we thought that this greedy observation can be not so obvious for Div.3 participant and implementation part can be difficult, but... We were so wrong :)

i used this

pi = pair<int,int>
struct cmp { 
    bool operator()(pi const& p1,pi const& p2) { 
        int f = p1.second- p1.first ,s = p2.second - p2.first;  
        if(f == s){
          return p1.first > p2.first;
        }
        return f < s;
    } 
};
priority_queue<pi,vector<pi >, cmp > pq;

Refer to my editorial for D: https://sahilbansal17.github.io/Competitive_Coding/2020/05/14/cf-642.html

change the positive to negative for reverse priority queue

Approach to solve problem D with priority queue : [ With C++ pseudocode ]

1. Create a structure for segment :

struct segment 
{
int start;
int end;
};

``

1. Create a comparator function by overloading the () operator in a struct such that the top of the priority queue contains the segment which has a greater length and in case of equal lengths, the element with smaller start position (left segment) is at the top.
   

struct comp{
	bool operator () (segment l1, segment l2) 
	{
		int len1=l1.end-l1.start+1;
		int len2=l2.end-l2.start+1;
		return (len1<len2)||((len1==len2)&&(l2.start<l1.start));
	}
};

Declare a priority queue in main() :

priority_queue<seg,vector<seg>,comp> pq;

If you don't understand this syntax, go through this article :
Priority queue for a struct in C++

1. As initially , the array contains all zeros. So, insert {0, n-1} to the priority queue initially.

2. Iterate for all numbers 1 to n and pop the top segment, in the priority queue. Place the number at appropriate position as indicated in the question. Suppose the number is placed at an index ind
   Now, there are 2 new segments, which needs to pushed into priority queue:
   I. { start,ind-1}
   II. { ind+1,end }
   (Check for the corner case, when start > ind-1 or ind+1>end)

This is the minimum subarray sum problem.

You can store all pairs using recursion. Actually that's what I did during testing. The implementation is the same as the mergeSort function (without merging arrays function).

yes, I did it.

Submit: https://mirror.codeforces.com/contest/1353/submission/80136775

I'm not sure, but maybe something's wrong with PriorityQueue. I replaced it with heapq in your solution and it got AC 80179294.

Isn't that obvious? If you consider each unit independently, then it's obvious that you cannot obtain the answer more than two using one unit (because this is $$$1$$$-dimensional array). Thus if the number of units is $$$m$$$ then the maximum possible answer is $$$2m$$$.

Let n be odd and suppose you divided m into (n/2) numbers such that one number is (m/(n/2) + m%(n/2)) and other (n/2) — 1 segments of (m/(n/2)). So the optimal answer, in this case, is to place these numbers on even positions i.e. 2, 4. In this case, you can observe the maximum you can get is 2*m. However, if n is even, you will get less 2*m sometimes. So, in general, the optimal way is to place m to one position such that it's not ending position of the array. But for n==2 there is not such positon.

The segment should be sorted by size (biggest first), then by index (smallest first). One can write an comparator to do this comparation. Or one can put the values into a pair, change the signs of the size of the index field (the second) and use the default comparator of the prioriy_queue.

There is a thumb rule stating that it takes roughly $$$1$$$ second for $$$10^8$$$ operations to get executed. Hence, $$$10^5$$$ operations are likely to take $$$5*10^5*10^{-8}$$$ second or $$$0.005$$$ seconds which is well within $$$1$$$ second.

Disclaimer: this is a rough estimation. Constants might affect this calculation to a great extent!

Iterator p becomes invalid after you erase the first element. Just move that line backwards a bit. 80179242

I have a simple solution for E 80161569

Well, they are not getting any kind of advantage by doing this. I don't get the reason why some users are doing this.

Yes

Suppose there is any optimal path. Now, look at array of heights in all steps $$$h_i$$$. You need somehow make them into array of consecutive numbers, for example: 3,4,5,6,7 or -3,-2,-1,0,1. First, understand that resulting array has values of form: $$$i+b$$$ where $$$i$$$ is index of value and $$$b$$$ some constant. We need to find value of $$$b$$$. You can't increase any of $$$h_i$$$ so you want such $$$b$$$ so $$$h_i$$$ >= $$$i+b$$$ for each $$$i$$$. In other words, it's condition to be able to make from original heights, heights of consecutive numbers. From the other hand, we need to have maximum $$$b$$$ among all possibilities to reduce heights as less as possible. Now two points of view:

• let say you set $$$b$$$ to some very big value like 1e18. then for each $$$i$$$ you'll have $$$h_i$$$ < $$$i+b$$$. Lets call those indexes like "bad" indexes. Now, decrease one by one $$$b$$$. At some point number of "bad" indexes will decrease. Then, it'll decrease again. Until their number hit zero. Zero number of "bad" indexes means that it's maximum $$$b$$$ that we need. Also, it's time when last $$$h_i$$$ become equal to $$$i+b$$$. As you can see, this index $$$i$$$ is our non-changing height.

• Other view is: rearrange $$$h_i - i >= b$$$, now we can make new array $$$z_i = h_i - i$$$ and find minimum here. Index of minimum is index of height that won't change.

Imagine that you have a path, on which every cell has been decreased at least once. You can increase each value by 1, which still produces valid path, but gives us better result. Doing that multiple times leads to some cell being unchanged.

We are moving from the center of the square grid, to the outermost square. It is obvious, that on moving towards the bigger square we find that, number of cells for each square we reach is 4*(n-1) where n is an odd number dimension of grid. Now, as we know that how many cells are at a particular distance from center. We simply iterate all odd numbers from 0 to size of grid and multiply each with their distances.

for i in range(0,n+1): sum+=4*(i-1)*dist; dist+=1

Also, if you look closely you find that after doing a little rearrangement the number of moves, boils down to just finding the sum of squares upto floor(n/2) and multiply result by 8. 80118906

a[i][j] is initial height and b[i][j] is final height.

It is guaranteed that the sum of n over all test cases does not exceed 2e5. This means that say, u have n=n1 in 1st testcase, n=n2 in 2nd testcase and so on. Then (n1 + n2 + ...... n(t)) will not exceed 2*(10^5). In short you don't need to multiply t with n . You can calculate the complexity using n = 2*(10^5) only.

all element of array a will be considered

In problem B, it said

Your task is to find the maximum possible sum you can obtain in the array a if you can do no more than (i.e. at most) k such moves (swaps).

No more than k moves, so you can just do 2 moves in your example

You can generate some random input and compare result of your solution with of the editorial solution. I am sure you can find a bunch of short counter test cases.

I don't think the maximum value of a[0][0] for which we can reach a[n — 1][m — 1] is always the optimal value of a[0][0]. Consider this case:

3 3
5 5 6
9 9 7
9 9 9

The answer is 2, but if you use the maximum value of a[0][0], which is 5, you'll need more than 2 steps.

Here you go.

Now don't say you were using online compiler as it was the queue time of online compiler

You either define struct with implemented operator, or use hacks based on fact how pairs compared under hood (lexicographically), or you need to define class or struct implementing operator () like this:

struct cmp {
    bool operator() (pair<int,pi> a, pair<int,pi> b) {... comparator code ...}
};
// then your set will be:
set<pair<int,pi>, cmp> my_set;

oh, I didn't check what is in editorial. Here is what I thought is there, this is from my code:

struct seg {
	int l, r;
	seg (int l = 0, int r = 0) : l(l), r(r) {}
	bool operator < (const seg &s) const {
		int a = r - l;
		int b = s.r - s.l;
		if (a != b)
			return a > b;
		return l < s.l;
	}
};

set<seg> segs; // usage.

Just make the length negative, that's solved !!!!!. so initially make s.insert({-n,{1,n}}); Btw i also hate comparator function its a waste of time

Thanks!!!

You are asked to count the minimum steps to bring everything on one point. Initially every block on board has one element. Your task to arrive at solution was to bring everything at center.

Here is cleaned source. 80174342. In previous source dp was filled diagonally (I'm retarded). And, there was check for int64 overflow.

I have doubt, can you help? I tried an approach that is similar to yours, but in my case, the time complexity is O(N * N / K) which will give TLE. But you have done it in O(K * N / K) => O(N).

But, with what I am thinking, we need to consider each index as start and then take jumps of k. How does your code check other cases with considering only K indices as start?

My TLE approach: 80175775

Try this case — https://mirror.codeforces.com/blog/entry/77373?#comment-622460