nader's blog

By nader, history, 6 years ago, In English

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²).

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by nader (previous revision, new revision, compare).