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

zarkdavor's blog

AtCoder ABC 223 Doukasen
By zarkdavor, history, 5 years ago, In English

Does anyone has a proof of the formula for problem C, the time T that the two flames meet is expressed as follows:

$$$ T = \frac{1}{2} \sum_{i=1}^{N} \frac{A_i}{B_i} $$$

Thanks

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
5 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Assume that left and right flame meet at point x , and the time in which left flame reaches the point x is the same time right flame takes . T[l] = T[r] = t , and total time it will take to burn complete system is T* which is summation of A[i] / B[i] , and now 2*t = T = > t = T/2

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

The main idea is that we can change the burning speed of all the fuses equal to 1. By doing this the new length of any ith fuse becomes (Ai/Bi) that is its length/speed.

suppose we call new length as upgraded length.

Now the problem reduces to a simpler problem that all the fuses has burning speed 1 and length equal to (Ai/Bi). Due to equal burning speed the two flames will meet at half of the total upgraded distance.

Hence , the given equation is proved.

I have tried my best to explain it :)

If u want u can cheak my submission too https://atcoder.jp/contests/abc223/submissions/26645120

→ Reply