codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

868C.md (1606B)


      1 Source: https://codeforces.com/problemset/problem/868/C
      2 
      3 C. Qualification Rounds
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Snark and Philip are preparing the problemset for the upcoming pre-qualification round for semi-quarter-finals. They have a bank of *n* problems, and they want to select any non-empty subset of it as a problemset.
     22 
     23 *k* experienced teams are participating in the contest. Some of these teams already know some of the problems. To make the contest interesting for them, each of the teams should know at most half of the selected problems.
     24 
     25 Determine if Snark and Philip can make an interesting problemset!
     26 
     27 Input
     28 
     29 The first line contains two integers *n*, *k* (1 ≤ *n* ≤ 105, 1 ≤ *k* ≤ 4) — the number of problems and the number of experienced teams.
     30 
     31 Each of the next *n* lines contains *k* integers, each equal to 0 or 1. The *j*-th number in the *i*-th line is 1 if *j*-th team knows *i*-th problem and 0 otherwise.
     32 
     33 Output
     34 
     35 Print "YES" (quotes for clarity), if it is possible to make an interesting problemset, and "NO" otherwise.
     36 
     37 You can print each character either upper- or lowercase ("YeS" and "yes" are valid when the answer is "YES").
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 5 3  
     45 1 0 1  
     46 1 1 0  
     47 1 0 0  
     48 1 0 0  
     49 1 0 0
     50 ```
     51 
     52 Output
     53 
     54 ```
     55 NO
     56 ```
     57 
     58 Input
     59 
     60 ```
     61 3 2  
     62 1 0  
     63 1 1  
     64 0 1
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 YES
     71 ```
     72 
     73 Note
     74 
     75 In the first example you can't make any interesting problemset, because the first team knows all problems.
     76 
     77 In the second example you can choose the first and the third problems.