KAN's blog

Technocup 2017 — Elimination Round 2 (and Codeforces Round 380) Editorial
By KAN, history, 7 years ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +77
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"Will be translated soon": Waiting for translation...

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

should be inside the maximum function.

Similarly, for zhenya.

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

Any idea why my submission for 729C http://codeforces.com/contest/737/submission/22410492 is exceeding time limit (on test #9). Please help to check.

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

Can someone please suggest some reading materials for learning graph matching? =)

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

For problem C, I do not understand the following statement:

if x ≤ f, then it is possible to ride in the fast mode min(x, f - x) kilometers.

How did you obtain the expression min(x,f-x) kilometers?

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

    Let the number of km in fast mode be k. Then the number of km in slow mode in x — k. So, we have the equation: Fuel used = 2*k + (x — k) <= f -> k + x <= f. Therefore, k <= f — x. Also, k <= x because we stop when we reach the next station. Therefore, k = min(x, f-x).

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

I had some trouble understanding Div2 D solution, so I'll explain it in more details.

The solution is actually an application of the pigeonhole principle.

Let s be the maximum number of positions where you can place a ship (of course, already considering those k misses of the input). The trick: reduce the problem to its complement! In other words: what is the maximum number of misses we can still make? The answer: m = s - a. If we shoot m ship slots once, an additional shot will hit some slot a second time (by the pigeonhole principle), or will hit a ship. So if we choose m + 1 distinct ship slots to be shot once, at least one of the shots will hit a ship.

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

In Financiers Game, shouldn't the "difference between the sum" mean the absolute value of the differences?

→ Reply