Блог пользователя aloopuri

Doubt in round 203 Division 2 A problem name TL
Автор aloopuri, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить