APIO 2012 problem

Правка en1, от nader, 2018-07-28 15:28:35

Can anyone give me the main idea to solve APIO 2012 Problem 2 Guard?

It is clear that when a guard reported 1 in a range A, then some guards reported 0 in every position in range A except position I. we are certain that there is a ninja at position I. After calculating all positions that way(let's say we have found IS such positions), we still have K-IS ningas and that information can help us be certain about other positions, but I didn't know how to solve this problem in less than O(n²).

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский nader 2018-07-28 15:28:59 0 (published)
en1 Английский nader 2018-07-28 15:28:35 580 Initial revision (saved to drafts)