The New Year's Bell
InterviewTime limit1sMemory limit512 MB
Given an N by M grid of who heard each bell ring, decide whether some distance thresholds R can produce exactly this pattern.
- Level
Medium4 of 10
- Topics
- Sorting, Greedy, Implementation, Array
- Solved
- No attempts yet
Problem
Ringing the New Year's bell marks the end of one year and the start of the next. At this event, the bell at Bosingak is rung several times.
The sound of the New Year's bell has the property that everyone within a certain distance R of the bell can hear it, and everyone farther than R cannot. Because celebrities such as politicians and entertainers take turns ringing the bell, the value of R changes with each ring.
Suppose there are N people, and the bell was rung M times in total at the New Year's bell ringing held on the night of December 31, 2019. While the M rings are taking place, the people do not move, because they are concentrating on the bell.
Given, for each of the N people, whether they heard each of the M rings, determine whether the situation is actually possible.
Input
The first line gives N (1 ≤ N ≤ 1,000) and M (1 ≤ M ≤ 100).
The i+1-th line (1 ≤ i ≤ N) gives M integers a**i,1, a**i,2, ..., a**i,M. If a**i,j is 1, person i heard the j-th ring; if it is 0, they did not hear it.
Output
Print YES if the situation is actually possible, and NO otherwise.