Please subscribe to the official Codeforces channel in Telegram via the link: ×

yuftftft's blog

By yuftftft, history, 10 months 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  

10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by yuftftft (previous revision, new revision, compare).

10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Dear yuftftft,

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.


Hope that this helps.

Best wishes