### KAN's blog

By KAN, history, 4 years ago, translation,  Tutorial of Technocup 2017 - Elimination Round 2   Tutorial of Practice_Round_1 Tutorial of Training_2 Tutorial of W8 main contest Comments (13)
 » "Will be translated soon": Waiting for translation...
 » should be inside the maximum function. Similarly, for zhenya.
•  » » Sure, fixed. Thanks!
 » 4 years ago, # | ← Rev. 2 →   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.
•  » » Have you tried fast I/O?
•  » » » yup, that's indeed the problem. Keep forgetting about that :( Thanks )
 » Can someone please suggest some reading materials for learning graph matching? =)
 » Can someone give a good explanation for the problem Div2 D?
 » 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?
•  » » 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).
 » For problem E, why is 3 the answer for the following test case:9 1 0 1 1 1 1 1 6 7 8Clearly, workers at index 2 to 5 are wrong because they should have 2,3,4 and 5 superiors respectively. I must be misunderstanding something. Could anyone please help to clarify?
 » 4 years ago, # | ← Rev. 4 →   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.
 » In Financiers Game, shouldn't the "difference between the sum" mean the absolute value of the differences?