Nerevar's blog

By Nerevar, 9 years ago, translation, In English

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 ai, breaking ties by increasing bi. 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 (b1). Move to the second exam. If we can take it on the day b2 (i.e. b1 ≤ b2), do it. Otherwise, take the second exam on the day a2. 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 [ini, outi]. 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

  • outi(j) ≤ ini(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 - wi(1), si(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(N2S). 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 r1, r2, c1, c2 (r1 ≤ r2, c1 ≤ c2), 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 c2 - c1 ≤ r2 - r1 (the opposite case is symmetric). Take the middle row r = (r1 + r2) / 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 c1 ≤ c ≤ c2; the second is an array of values down(r, c), where c1 ≤ c ≤ c2. 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).

  • Vote: I like it
  • +65
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

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:

while (there_is_square(side: biggest_square_side + 1, containing_point: P))
    biggest_square_side++;

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:

for (P in reverse(points))
    for (size_to_try = biggest_square_side + 1 ; ; size_to_try++)
        if (there_is_square(side: biggest_square_side + 1, containing_point: P))
        // there_is_square takes O(N log N) in my code
            biggest_square_side = size_to_try + 1
        else 
            break;

This looks like two loops with O(NlogN) inside the innermost loop, but since in total we won't increment biggest_square_side more than N times it should give only O(N2logN) 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: 8315473

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I had similar solution but working in O(NK).

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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?

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 . ?

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for quick editorial!

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Div2A: Those are not all the possible solutions (there are ab + c and a + bc), but the good thing is that you can prove that these two cases don't happen.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E,DIV 2,is it necessary that after transporting each time,we have to be on a new floor ?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ?

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        As in the problem statement, we can only go from floor x to floor y iff |x  -  y|  <  |x  -  b|. Say that a = 1 and b = 6, then we can't do (1, 3, 5, 1), but if b is large enough, let's say b = 10, we can achieve it (since |5 - 1| < |5 - 10|).

»
9 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 some k we know that the algorithm in the editorial is optimal (it's not difficult to prove for example for k = 1). Now we should prove it for k + 1. Let res be the answer for k + 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 than res. It can be done by induction hypothesis and some accurate analysis of the cases.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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:=)

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    If you add 60 as a new mark, is there any number x such that x - 60 = 117 or x - 60 = 148?. As far as I can see there is no such X.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But you can obtain this numbers with addition 57+60=117 and 48+60+20. = 148

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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)"

»
8 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a different solution in the exercise A my algorithm has a higher result in the test cases where a = 6, b = 7, c = 1; the answer is 48 but my algorithm gets 49; (6 + 1) * 7;

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem A if you really make all the possible combinations it will be a wrong answer !!

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi, in problem C, on my submission using dfs and dp, I am getting Runtime error (Exit code : -1073741819) on test 26 with n=5000 but the code works fine with n = 4949. I tried finding the error in the indexing but couldn't get any at all. Please help.

I understand that a better greedy solution exists but still for learning purpose, I can't get why this code gets this strange error.

Here is my submission link : Code