thecortex's blog

By thecortex, history, 8 years ago, In English

What is the Pseudo Code for the solution to this problem 720A - Closing ceremony ?

I'm n't sure if this guess is correct;

1 — make two priority queues / heaps 2 — fill the heaps with the distances from point(0,0) and point(0,m+1) in quadratic time O(2*n*m) 3 — sort queues of audience k, l=n*m-k in ascending order 4 — for each attendee of the audience from both queues (pick the one with smaller stamina) in time of O(2*n*m) 5 ----- pop the minimum / top of the heap corresponding to the entry point either (0,0) or (0,m+1) 6 ----- if point was taken before, then get pop next min 7 ----- if point's distance from entry > stamina of attendee, then return false and terminate 8 ----- mark the point as taken, so that the other heap doesn't pick it

Any better approaches?

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