problem : https://atcoder.jp/contests/abc173/tasks/abc173_d

IMHO the proof in editorial is insufficient.

"IF the k+1-st person does not cut in to next to k-th person, then whether or not swapping them is none of their business." but it can have influence on people arrived after them.

Here is my proof not depends on people arrived in the decreasing order. Consider all the n-1 comfort we can get. I will prove: If there are k numbers >= x, others < x, then among all comfort we can get, there are at most 2*k-1 comfort >= x.

We note these k person as nice person, and the position between 2 nice person as nice position. also we note comfort >= x as nice comfort. 1. There are at most k-1 nice comfort these k nice person can get(first nice person can not get nice comfort). 2. when a nice person arrive, nice position will increase at most one, when a not so nice person get a nice comfort, he must decrease a nice position. so not so nice persons can get k nice comfort at most.

so we can get at most 1 comfort >= a[0], 3 comfort >= a[1], and so on...

Problem: https://mirror.codeforces.com/contest/1373/problem/F

We will prove it is not possible if

1. total capacities of the designed stations is smaller than total households of all cities. or
2. for some continuous k stations, their total capacity is smaller than total households of (k-1) cities between them.

otherwise, it is always possible.

It is obvious that if condition 1 or 2 is met, it not possible. Now we prove it is the only senario that it is not possible.

Let us consider a circle segmented to n arcs with n nodes N1, N2, ... Nn. the length between Ni ans Ni+1 is ai(the number of households in the i-th city.) and there is a small ring in arc_i, note as Ci. the rings constrained by its node boundaries. For example ring C1 cannot move outside the bounds of N1 and N2. there is a rope with origin length bi between Ci and Ci+1. the rope can be stretched if necessary.

Now if we can arrange all the rings so that no rope need to be stretched, there is a solution.

We just let all rings move freely. if no rope are stretched, it is ok. If some ropes are streched. there are 2 conditions:

a. all ropes are streched, it is condition 1; b. some continuous ropes are streched, while the rope before and after them are not. In this case, the start and end ring of these ropes must be at the node. so it is condition 2.

end of proof. Sorry for my poor English.

When solving AtCoder Grand Contest 044 Problem B, I wrote some O(n^3) code with n<=500 like:

typedef vector<int> vi;
vector<vi> dirs({{0,1}, {0,-1}, {-1,0}, {1,0}});
...
for (auto dir : dirs){ // run O(n^3) times
...
}

and get TLE. On my pc it runs within 4900ms. During the contest I have no idea why.(dumb me) After the contest I looked at other people's solution and finally get accepted solution, just add an '&' after 'auto':

for (auto& dir : dirs){ // run O(n^3) times
...
}

480 ms on my pc! 10 times faster!

I did more tests:

for (int dd = 0; dd<4; ++dd){ // run O(n^3) times
    vi dir = dirs[dd];

4900 ms

for (int dd = 0; dd<4; ++dd){ // run O(n^3) times
    vi& dir = dirs[dd];

480 ms

vi dir;
for (int dd = 0; dd<4; ++dd){ // run O(n^3) times
    dir = dirs[dd];

1800 ms

Maybe vector is too big, I tried pair:

vector<pair<int, int>> dirs({{0,1}, {0,-1}, {-1,0}, {1,0}});
for (auto dir : dirs){ // run O(n^3) times

370 ms, no difference if I add ‘&’， maybe because pair of int is the same size as 64 bit pointers.

Final conclusion: Seems like

for (auto dir : dirs)

is equivalent to

for (int dd = 0; dd<4; ++dd){ // run O(n^3) times
    vi dir = dirs[dd];

that will construct a vector and assignment another vector to it every iteration. which cost much more time than simple data structures or reference.