Berezin's blog

Codeforces Round #214 (Div. 2) — Tutorial
By Berezin, 11 years ago, translation, In English

366A — Dima and Guards

The solution doesn't exist only if the mimimal way to bribe is grater than n. Otherwise we can increase the gift price to make price1 + price2 = n.

Let's find the miminal way to bribe. We should buy that gift for old lady which costs less. It means, if we have 2 guards with params a b c d, then minimum bribe price will be min(a, b) + min(c, d). Let's choose the guard with the minimal bribe price. If the minimal bribe price is greater than n, answer -1. Otherwise, the possible answer is, for example: Guard number, min(a, b), n–min(a, b).

366B — Dima and To-do List

Dima can make k–1 tasks, so Inna always tells him off for each k-th taks, beginning from the chosen place. So for the numbers with same modulo by k the answer will be the same. We should find the answer with minimal first task number so it is eniugh to calculate the sums of “tellings of” for tasks 0, 1... k–1. We can do it in such way: Determine the array int sum[k]. And put the number into appropriate bucket while reading:

sum[I mod k] +  = a[i]. Now we should simply find first i with minimal sum[i].

Complexity: O(N).

366C — Dima and Salad

Let's calculate dinamic: d[num][balance] where num – last looked fruit, balance — difference between sum of colories and sum of tastes. Let's multiply each b by k. The answer will be d[n][0].

d[num][balance] = maximal possible sum of tastes under conditions.

Step: from d[num][balance] we can relax answers:

d[num + 1][balance] = max(d[num + 1][balance], d[num][balance]) – if we don't choose a fruit

d[num + 1][balance + a[i] - b[i]·k] = max(d[num + 1][balance + a[i] - b[i]·k], d[num][balance] + a[i]) – if we choose a fruit.

Balance can be negative, so in programming languages which don't support negative indexation, indexes should be shifted by the biggest negative number for balance. If we determine the balance as sum(b·k) - sum(a) it will be the sum of all tastes.

366D — Dima and Trap Graph

The answer for some path is a range under which we can go all the way, and this range is the intersection of all the ranges on the path. We can conclude it because the number is valid for path if it is valid for all ranges in the path. We will iterate all ribs. Let the left board of range on a rib is the left board of our intersection. It means we can't use ribs whith left board greater than ours. Lets iterate all right boards, determining the answer as the range from fixed left board to the chosen right. This answer exists if we have any path from the first node to the last. Let's check if the graph is connected if we leave only ribs with left board not greater than our and right board not less than our. If the graph is connected — let's update the answer. Right board can be found by binary search so the complexity is O(M2·logM).

366E — Dima and Magic Guitar

There are many solutions for this task. I will describe my, you can deal with other by looking participants code. To find the answer we should calculate maxDis[k][k], where maxDis[i][j] – maximal complexity from note i to note j.

Now we should only iterate the song updating answer for each pair of adjacent notes. Let's think how we can calculate the matrix.

For each place (x1, y1) on the guitar let's iterate pairs (x2, y2) with y2 ≤ y1.

If (x2 ≤ x1) distance will be x1–x2 + y1–y2. So we should find minimal x2 + y2 in submatrix from (0, 0) to (x, y).

If (x2 ≥ x1) distance will be x2–x1 + y1–y2. So we should find maximal x2–y2 in submatrix from (n–1, 0) до (x, y).

We will calculate this values for each note. We need too much memory so we should memorize only one previous row for each note. For each place we will update dinamics for both variants according to already calculated and for our own note (which is in this cell) we will also compare (i + j) or (i–j) with current value in the cell.

Complexity O(N·M·K)

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

Comments Comments (22)
| Write comment?
»
11 years ago, # |
← Rev. 3   Vote: I like it +24 Vote: I do not like it

I (but not just me, as I noticed from looking at others' codes) have a cool solution of E:

Imagine that we want to calculate the max. distance of 2 tones a, b. Take tone a at (x1, y1) and b at (x2, y2); notice that |x1 - x2| + |y1 - y2| is the maximum of  ± (x1 - x2) ± (y1 - y2) for all signs, which leads to 4 possible expressions:

x1 + y1 - x2 - y2
x1 - y1 - x2 + y2
 - x1 + y1 + x2 - y2
 - x1 - y1 + x2 + y2

Instead of limiting ourselves to the correct expression, we can evaluate the maxima of all pairs of points with all 4 expressions, and the answer will still be the maximum of them all. Notice that all 4 are linear, so we just need to calculate the maximum and minimum of $x_1+y_1$ and x1 - y1 for all points of one tone; the result for 2 tones can be found by trying the maxima of all 4 expressions, which are (in that order)

Complexity: O(NM) :D

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

    Please elaborate the part Notice that all 4 are linear, so we just need to calculate the maximum and minimum of x1 + y1 and x1 - y1 for all points of one tone;

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

      We compute the numbers and and take their difference. Similarly for the other 3 expressions, and for any pair of tones (denoted here as "1" and "2").

      For any linear function f (UTFG if you don't know about these) we have

      → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

Actually there is a simple soluton for problem D with complexity O(M ^ 2).

Tip: Two pointers instead of binary search.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can u double-check the expressions in solution for task C?

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone please explain the solution to C? I did not understand the use of balance. I just thought of doing the following: For a pair (a,b), if a/b = k, it can be.included in our solution. For all pairs for which a/b!=k, check if adding the pair to the solution satisfies given conditions. If yes, include it in solution. We can choose nC2 pairs and do the above operations in O(n^2).

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

    I still don't understand how to handle negative indices. Btw, it's Dynamic Programming.

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

      Yes, I got that it is dp.

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      the second index (balance) always lies between -100,000 and +10,000. therefore, we can access the ith element of an array by shifting indices like a[i+100000] (here it's dp[i][balance+100000]), or by using other data structures like map.

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

      One way is to use a third state variable which denotes the sign of the difference i.e, whether the difference is +ve or -ve. Here: 45877072

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In D, what do you mean by ribs and boards?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    i'm not sure, but i think rib means edge, and board means bound (i.e. left board = lower bound, right board = upper bound)

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can somebody explain problem D solution

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

I don't like how A is worded,

"If a chocolate bar for some guard costs less than the minimum chocolate bar price for this guard is, or if a box of juice for some guard costs less than the minimum box of juice price for this guard is, then the guard doesn't accept such a gift."

By using "this guard" and "some guard", it can be read that out of all the guards, this guard's minimum chocolate price must be the minimum out of every guard.

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you are absolutely correct there is a problem in this statement my solution is not working just because of this condition

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

I must say problem C is amazing, never seen any problem quite like it.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
C can be solved with use of dp with bitmasks 
dp state: dp[i][summation of tastes][summation of calories] 
and if we want add new taste it will be

dp[i+1][summation + a[i]]<<=b[i];

we will shift every summation of calories by b[i];

ACCEPTED

→ Reply
  • »
    »
    14 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Is it doable in a recursive way? Using Bitsit.

    → Reply