A physical proof of Educational Codeforces Round 90 problem F.

Revision en7, by iynaur87, 2020-06-26 05:00:20

Problem: https://codeforces.com/contest/1373/problem/F

We will prove it is not possible if

  1. total capacities of the designed stations is smaller than total households of all cities. or
  2. for some continuous k stations, their total capacity is smaller than total households of (k-1) cities between them.

otherwise, it is always possible.

It is obvious that if condition 1 or 2 is met, it not possible. Now we prove it is the only senario that it is not possible.

Let us consider a circle segmented to n arcs with n nodes N1, N2, ... Nn. the length between Ni ans Ni+1 is ai(the number of households in the i-th city.) and there is a small ring in arc_i, note as Ci. the rings constrained by its node boundaries. For example ring C1 cannot move outside the bounds of N1 and N2. there is a rope with origin length bi between Ci and Ci+1. the rope can be stretched if necessary.

Now if we can arrange all the rings so that no rope need to be stretched, there is a solution.

We just let all rings move freely. if no rope are stretched, it is ok. If some ropes are streched. there are 2 conditions:

a. all ropes are streched, it is condition 1; b. some continuous ropes are streched, while the rope before and after them are not. In this case, the start and end ring of these ropes must be at the node. so it is condition 2.

end of proof. Sorry for my poor English.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English iynaur87 2020-06-26 05:00:20 3 Tiny change: 'or 2 is meeted, it not p' -> 'or 2 is met, it not p'
en6 English iynaur87 2020-06-26 04:47:51 2 Tiny change: 'hed if neccesary.\n\n!' -> 'hed if necessary.\n\n!'
en5 English iynaur87 2020-06-26 04:39:34 6
en4 English iynaur87 2020-06-26 03:24:12 111
en3 English iynaur87 2020-06-25 21:51:09 43
en2 English iynaur87 2020-06-25 21:49:45 71
en1 English iynaur87 2020-06-25 21:48:42 1329 Initial revision (published)