KAN's blog

By KAN, history, 4 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...
Tutorial of Practice_Round_1
Tutorial of Training_2
Tutorial of W8 main contest
 
 
 
 
  • Vote: I like it
  • +77
  • Vote: I do not like it

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

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

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

should be inside the maximum function.

Similarly, for zhenya.

»
4 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.

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

    Have you tried fast I/O?

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

      yup, that's indeed the problem. Keep forgetting about that :( Thanks )

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

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

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

Can someone give a good explanation for the problem Div2 D?

»
4 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?

  • »
    »
    4 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).

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

For problem E, why is 3 the answer for the following test case:

9 1 0 1 1 1 1 1 6 7 8

Clearly, 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   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.

»
4 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?