Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

KAN's blog

Technocup 2017 — Elimination Round 2 (and Codeforces Round 380) Editorial
By KAN, history, 10 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?
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

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

should be inside the maximum function.

Similarly, for zhenya.

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

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

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

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

→ Reply
»
10 years ago, hide # |
 
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
  • »
    »
    10 years ago, hide # ^ |
     
    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
»
10 years ago, hide # |
← 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
»
10 years ago, hide # |
 
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