aloopuri's blog

Doubt in round 203 Division 2 A problem name TL
By aloopuri, history, 6 years ago, In English

i was not able to initially figure out the method on this problem,But then i was able to understand that,only the correct n solution should have the minimum time limit,but if any wrong m solution has a time limit which is lesser than the highest time limit of the correct n solution,a TL cannot be set for that problem,For which "-1" has to be printed,but when i look at the code why should max(2*v,p)<s is taken?Where v is the min of a[i] and p is the max of a[i] and s is the min of b[i],instead of which p<s can be directly taken ?Is it wrong to just consider p<s ? For this problem

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

Comments Comments (3)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Dear aloopuri,

Satisfying the condition a_max < b_min only does not consider the third condition about the "extra" time, which implies that 2 * a_min < b_min must be also satisfied. Both conditions can merged into a single expression V = { v | v_min <= v <= v_max }, where v_min = max( 2 * a_min, a_max ) and v_max = b_min — 1. If v_min > v_max, then V is an empty set, and the answer is -1. Otherwise, the answer is v_min.

The following is a GNU C++17 implementation of this solution.

35541338

Hope that this helps.

Best wishes

→ Reply