I am happy to present you author's ideas of solutions. Editorial of the first five problem is authored by — HolkinPV and gridnevvvit, editorial for the last two problems is written by me.

### 479A - Expression

In this task you have to consider several cases and choose the best one:

```
int ans = a + b + c;
ans = max(ans, (a + b) * c);
ans = max(ans, a * (b + c));
ans = max(ans, a * b * c);
cout << ans << endl;
```

### 479B - Towers

The task is solved greedily. In each iteration, move the cube from the tallest tower to the shortest one. To do this, each time find the position of minimum and maximum in the array of heights (in linear time).

### 479C - Exams, 480A - Exams

The solution is again greedy. Sort the exams by increasing *a*_{i}, breaking ties by increasing *b*_{i}. Let’s consider exams in this order and try to take the exams as early as possible. Take the first exams in this order on the early day (*b*_{1}). Move to the second exam. If we can take it on the day *b*_{2} (i.e. *b*_{1} ≤ *b*_{2}), do it. Otherwise, take the second exam on the day *a*_{2}. Continue the process, keeping the day of the latest exam.

```
std::sort(a, a + n); // а is the array of pairs, where first element is the date in schedule, and second is the early date of passing
int best = -1;
for(int i = 0; i < n; i++) {
if (best <= a[i].second) {
best = a[i].second;
} else {
best = a[i].first;
}
}
```

### 479D - Long Jumps, 480B - Long Jumps

It is easy to see that the answer is always 0, 1 or 2. If we can already measure both *x* and *y*, output 0. Then try to measure both *x* and *y* by adding one more mark. If it was not successful, print two marks: one at *x*, other at *y*.

So, how to check if the answer is 1? Consider all existing marks. Let some mark be at *r*. Try to add the new mark in each of the following positions: *r* - *x*, *r* + *x*, *r* - *y*, *r* + *y*. If it become possible to measure both *x* and *y*, you have found the answer. It is easy to check this: if, for example, we are trying to add the mark at *r* + *x*, we just check if there is a mark at *r* + *x* + *y* or *r* + *x* - *y* (by a binary search, since the marks are sorted). Make sure that the adde marks are in [0, *L*].

### 479E - Riding in a Lift, 480C - Riding in a Lift

The task is solved by a dynamic programming. State is a pair (*i*, *j*), where *i* is the number of trips made, and *j* is the current floor. Initial state is (0, *a*), final states are (*k*, *v*), where *v* is any floor (except *b*).

It is easy to see the transitions: to calculate *dp*(*i*, *j*), let’s see what can be the previous floor. It turns out that all possible previous floors form a contiguous segment (with a hole at position *j*, because we can’t visit the same floor twice in a row). So, *dp*(*i*, *j*) is almost equal to the sum of values *dp*(*i* - 1, *t*), where *t* belongs to some segment [*l*, *r*] (the values of *l* and *r* can be easily derived from the conditions from the problem statement). Using pretty standard technique called “partial sums” we can compute *dp*(*i*, *j*) in *O*(1), so overall complexity is *O*(*NK*).

Jury solution: 8322623

### 480D - Parcels

Let’s make two observations.

First, consider the parcels as time segments [*in*_{i}, *out*_{i}]. It is true that if at some moment of time both parcel *i* and parcel *j* are on the platform, and *i* is higher than *j*, then .

Second, let’s imagine that there are some parcels on the platform. It turns out that it is enough to know just a single number to be able to decide whether we can put another parcel on top of them. Let’s denote this value as “residual strength”. For a parcel (or a platform itself) the residual strength is it’s strength minus the total weight of parcels on top of it. For a set of parcels, the residual strength is the minimum of individual residual strengths. So, we can put another parcel on top if it’s weight does not exceed the residual strength.

These observations lead us to a dynamic programming solution. Let the top parcel at the given moment has number *i*, and the residual strength is *rs*. Make this pair (*i*, *rs*) the state of DP, because it is exactly the original problem, where the platform strength is *rs* and there are only parcels *j* with . In *d*(*i*, *rs*) we will store the answer to this instance of the original problem.

Which transitions are there? We can choose a set of parcels *i*(1), *i*(2), ... *i*(*k*) such that

*out*_{i(j)}≤*in*_{i(j + 1)}, i.e. segments do not intersect (but can touch) and are sorted;- the weight of each of these parcels does not exceed
*rs*.

This choice corresponds to the following sequence of actions: first put parcel *i*(1) on the top of *i*. This gets us to the state *i*(1), *min*(*rs* - *w*_{i(1)}, *s*_{i(1)}), so we add up the answer for this state and the cost of *i*(1). Then we take away all parcels, including *i*(1), and put the parcel *i*(2) on top of *i*, and so on.

As the number of states in DP is *O*(*NS*), all transitions should take linear time. It can be achieved by making an inner helper DP. This give a solution in *O*(*N*^{2}*S*). Note that for simplicity the platform can be considered as a parcel too.

### 480E - Parking Lot

Let’s denote the car arrivals as events.

Consider the following solution (it will help to understand the author’s idea): let’s consider all empty square in the table. There a too many of them, but imagine that we can afford to loop through all of them. If we fix a square, we can find out when it is no longer empty: find the first event that belongs to this square. Let this event has number *x*, and the size of the square is *k*. Now we can update the answers for all events with numbers less than *x* with a value of *k*.

The model solution use the idea of Divide and Conquer. Let’s make a recursive routine that takes a rectangular sub-table, bounded with *r*_{1}, *r*_{2}, *c*_{1}, *c*_{2} (*r*_{1} ≤ *r*_{2}, *c*_{1} ≤ *c*_{2}), and a list of events that happen inside this sub-table. The purpose of the routine is to consider how maximal empty squares in this sub-table change in time, and to update the answers for some of the events.

Let’s assume that *c*_{2} - *c*_{1} ≤ *r*_{2} - *r*_{1} (the opposite case is symmetric). Take the middle row *r* = (*r*_{1} + *r*_{2}) / 2. Virtually split all the squares inside the sub-table into those which lie above *r*, those which lie below *r*, and those which intersect *r*. For the first two parts, make two recursive calls, splitting the list of events as well. Now focus on the squares that intersect the row *r*.

Using initial table, for each cell (*r*, *c*) we can precompute the distance to the nearest taken cell in all four directions (or the distance to the border, if there is no such cell): *up*(*r*, *c*), *down*(*r*, *c*), *left*(*r*, *c*) и *right*(*r*, *c*). Using this values, build two histograms for the row *r*: the first is an array of values *up*(*r*, *c*), where *c*_{1} ≤ *c* ≤ *c*_{2}; the second is an array of values *down*(*r*, *c*), where *c*_{1} ≤ *c* ≤ *c*_{2}. I say histograms here, because these arrays actually can be viewed as heights of empty columns, pointing from the row *r* upwards and downwards. Lets call the first histogram “upper”, the second one — “lower”. Now consider all events inside the sub-table in the order they happen. Each event changes a single value in a histogram. If after some event *x* the maximum empty square found in the histograms has size *k*, and the next event has number *y*, we can update answers for all events with numbers *x*, *x* + 1, ..., *y* - 1 with the value of *k*.

It remains to learn to find a maximum square in two histograms. It can be done by a two-pointer approach. Set both pointers to the beginning. Move the second pointer until there is such square in histograms: there is a square with side length *k* if (minimum on the interval in the upper histogram) + (minimum on the interval in the upper histogram) — 1 >= k. When the second pointer can not be moved any more, update the answer and move the first pointer. To find the minimum in O(1), author’s solution creates a queue with minimum in O(1) support. That is, the maximum square can be found in linear time.

Let’s try to estimate the running time. Each call of the routine (omitting inner calls) costs *O*(*len*·*q*), where *len* is the shortest side of the sub-table, and *q* is the number of events in it. If we draw a recursion tree, we will see that each second call *len* decreases twice. The total cost of all operations in a single level of a recursion tree is *O*(*NK*), where *K* is the total number of events. As long as we have *O*(*logN*), overall complexity is *O*(*NKlogN*).

Solved E div. 1 a bit differently. I was iterating over events in the reversed order. So instead of adding cars I was removing them. With this approach max square size can only grow and obviously it grows only if new bigger square becomes available and it contains the point you have just cleared. Let's say that so far we have already found a square with the side

`biggest_square_side`

. Then to check if new square was cleared by removing car from point`P`

I simply had a loop like that:`there_is_square`

method was working similarly to yours histogram approach, but it was not looking for the biggest square, just checking if some specific square exists, so my two pointers were a bit simpler because the offset between them was fixed.Yet another round I have a solution based on amortized time complexity analysis :-) Basically my solution has three loops like that:

This looks like two loops with

O(NlogN) inside the innermost loop, but since in total we won't increment`biggest_square_side`

more thanNtimes it should give onlyO(N^{2}logN) if I didn't miss something. Anyway the solution was accepted, though the time is ~2 seconds, I think it's because of me using a lot of small`set<pair>`

objects. Submission: 8315473I had similar solution but working in

O(NK).Is it possible to find the largest rectangle between two histograms? Such that we just have to check the row and column of the removed car to find the new greatest rectangle?

problem "479B — Towers" what is the output for the input: 4 1 2 2 4 4

Input: 4 1 2 2 4 4 Output: 2 1 3 2

can it be : 2 1 3 1 ? beacause to convert 2 2 4 4 we can choose any 1 of two's and any 1 of four's . ?

Yes, any of the two answers would be accepted... ;-)

thank you micael . could u please see my new comment n hint me. newbie here :) thank you .

Thanks for quick editorial!

спасибо за разбор задач!

for problem B i am getting wrong answer on pretest 5 . any tricky case please ?

and what should b output for 15 5 5 8 4 7 9 6 3 4 5 2 1 4 8 9 7

Output: 5 5 5 11 14 11 14 10 5 10 2 11

I don't think there is any tricky cases for this problem... If you get the right algorithm, it's pretty much straightforward.

When you submit your code, it is possible to check what is wrong by clicking on the submission ID, it will show you all the cases it passes and the case it fails.

ah ! that is valuable information i didn't know about. thank you :)

Div2A: Those are not all the possible solutions (there are

ab+canda+bc), but the good thing is that you can prove that these two cases don't happen.In problem E,DIV 2,is it necessary that after transporting each time,we have to be on a new floor ?

Yeah. It is given in the problem statement: Let us suppose that at the moment you are on the floor number x (initially, you were on floor a). For another trip between floors you choose some floor with number y

(y ≠ x)Suppose i start from floor number=1,and i go to floor 3.Than from 3 we go to 5 ,So from 5 can we go back to 1 or not ?

As in the problem statement, we can only go from floor

xto flooryiff |x-y| < |x-b|. Say thata= 1 andb= 6, then we can't do (1, 3, 5, 1), but ifbis large enough, let's sayb= 10, we can achieve it (since |5 - 1| < |5 - 10|).UPD: Never mind, I found my mistake. Stupid dp[blah][-1]. Thanks all :)

Can anyone help me with this solution of mine 8331072? Somehow it returns a very large number (maybe a result of a bad modulo) on Codeforces, but runs well on my machine.

usually long long everywhere helps in such problems...

Hi. Does anybody have proof that the greedy algorithm for div2B is correct?

It very easy. If difference between maximal element and minimal element less or equal to one, you can not improve unstability. In other cases, can only improve unstability by this move, and it can only decrease.

Sorry, but that doesn't sound convincing enough. Especially the other cases.

gridnevvvit, anyway thank you for the answer.

Actually, I suppose that more exact proof may be something like this, in my opinion.

We will use the induction by the maximal number of operations

k. Let's suppose that for somekwe know that the algorithm in the editorial is optimal (it's not difficult to prove for example fork= 1). Now we should prove it fork+ 1. Letresbe the answer fork+ 1 steps using the algorithm. We can show that any first switch which is different from switching between maximal and minimum will lead us to an answer more or equal thanres. It can be done by induction hypothesis and some accurate analysis of the cases.I would also like this. What is the optimal substructure of problem div2B, and what is the greedy property?

Time: 61 ms, memory: 20 KB Verdict: WRONG_ANSWER Input 19 180 117 148 0 1 19 20 21 28 57 65 68 70 78 88 100 116 154 157 173 179 180 Output 1 60 Answer 2 117 148 Checker comment wrong answer It's impossible to measure some value from wanted list

My solution failed on 12th test. but I think my answer is more correct. Isn't it? If you add 60 you can measure both 117 and 148. Your solution is not the best one. Please fix test, or explain me please the reason of failure:=)

If you add 60 as a new mark, is there any number

xsuch thatx- 60 = 117 orx- 60 = 148?. As far as I can see there is no such X.But you can obtain this numbers with addition 57+60=117 and 48+60+20. = 148

Probably you've missed an important part in the statement:

"Valery believes that with a ruler he can measure the distance of d centimeters, if there is a pair of integers i and j (1 ≤ i ≤ j ≤ n), such that the distance between the i-th and the j-th mark is exactly equal to d (in other words, aj - ai = d)"

Exactly, thanks:=)

Hi all, for the 479B Tower problem, I can run the source code in my computer but it raises an error "Run time error" for the test case 6 when I submit.

I test the test case 6 in my computer and it is ok.

Could you please help me?

http://codeforces.com/contest/479/submission/8367931

My solution failed on the 26th test, and I don't know why, can anyone help me? http://codeforces.com/contest/480/submission/8378930

thanks

For Div2C, my java(1), java(2) solutions both fail on test 18, while my cpp solution gets accepted. The only thing I can think of, is that I am screwing up the implementation of the comparison. Can anyone take a quick look and tell me what is wrong with my Java submissions?

Thank you!

what the hell is wrong with Cf now a days. my NKlogN solution == tLE for Div1 E . need to redude into NK.! solution link : http://codeforces.com/contest/480/submission/17254807. anyone why?

Edit : can be done in NK using max sliding window. got now.

This is my submission for problem C, http://codeforces.com/contest/479/submission/23508408, I verified my algorithm with the editorial,why am I getting WA for testcase 34? Thanks.

Can anyone explain me Div 2E . I am not able to understand it from the Editorial and comments as well

can anyone tell me my mistake on problem D? my submission

my idea is similar but i use set

`sx`

which contain mark to be inserted so that we can measure length x, and`sy`

which contain mark to be inserted so that we can measure length y. If some value in`sx`

also exist in`sy`

then its enough to insert 1 mark. Im getting WA 18 (minimum insert should be 1 but my program output 2)