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²).
Auto comment: topic has been updated by nader (previous revision, new revision, compare).
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$$$ ninjas 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^2)$$$.
it's better to write a blog with Latex.