Russian Code Cup 2016 — Finals :: Problem A — Closing ceremony

Revision en1, by thecortex, 2016-09-19 23:36:50

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?

Tags priority queue, grid, sorting

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English thecortex 2016-09-19 23:36:50 864 Initial revision (published)