codeforces-scrape

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

1102B.md (1904B)


      1 Source: https://codeforces.com/problemset/problem/1102/B
      2 
      3 B. Array K-Coloring
      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 You are given an array $a$ consisting of $n$ integer numbers.
     22 
     23 You have to color this array in $k$ colors in such a way that:
     24 
     25 * Each element of the array should be colored in some color;
     26 * For each $i$ from $1$ to $k$ there should be at least one element colored in the $i$-th color in the array;
     27 * For each $i$ from $1$ to $k$ all elements colored in the $i$-th color should be distinct.
     28 
     29 Obviously, such coloring might be impossible. In this case, print "NO". Otherwise print "YES" and any coloring (i.e. numbers $c_1, c_2, \dots c_n$, where $1 \le c_i \le k$ and $c_i$ is the color of the $i$-th element of the given array) satisfying the conditions above. If there are multiple answers, you can print any.
     30 
     31 Input
     32 
     33 The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 5000$) — the length of the array $a$ and the number of colors, respectively.
     34 
     35 The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 5000$) — elements of the array $a$.
     36 
     37 Output
     38 
     39 If there is no answer, print "NO". Otherwise print "YES" and any coloring (i.e. numbers $c_1, c_2, \dots c_n$, where $1 \le c_i \le k$ and $c_i$ is the color of the $i$-th element of the given array) satisfying the conditions described in the problem statement. If there are multiple answers, you can print any.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 4 2
     47 1 2 2 3
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 YES
     54 1 1 2 2
     55 ```
     56 
     57 Input
     58 
     59 ```
     60 5 2
     61 3 2 1 2 3
     62 ```
     63 
     64 Output
     65 
     66 ```
     67 YES
     68 2 1 1 2 1
     69 ```
     70 
     71 Input
     72 
     73 ```
     74 5 2
     75 2 1 1 2 1
     76 ```
     77 
     78 Output
     79 
     80 ```
     81 NO
     82 ```
     83 
     84 Note
     85 
     86 In the first example the answer $2~ 1~ 2~ 1$ is also acceptable.
     87 
     88 In the second example the answer $1~ 1~ 1~ 2~ 2$ is also acceptable.
     89 
     90 There exist other acceptable answers for both examples.