gautam94's blog

Problem 386B two pointers method
By gautam94, 11 years ago, In English

386B - Fly, freebies, fly! Please help me understand this solution. 5711342 Is this the two pointers method. Why is the final answer ans = max(ans,j-i) ?

  • Vote: I like it
  • +5
  • Vote: I do not like it

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

Here ans will contain the maximum of previous result and new result. j-i is the new result freebie can visit in T seconds starting from ith second.

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

This solution is similar to be brute force. So the main idea of problem is to find maximum in sorted timings of j-i, where a[i] + t <= a[j] (i <= j).

for example, first lucky student was i-th. it means that some next students whose time is not greater than a[i] + t are lucky too. We can find this maximum by brute force in submission 5711342 and by two pointers method. e.g. 5705879. Difference is that we don't change j, because if we know that a[i] + t <= a[j], this means that a[i + 1] + t <= a[j] too.

→ Reply