codeforces-scrape

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

1624D.md (3832B)


      1 Source: https://codeforces.com/problemset/problem/1624/D
      2 
      3 D. Palindromes 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 have a string $s$ consisting of lowercase Latin alphabet letters.
     22 
     23 You can color some letters in colors from $1$ to $k$. It is not necessary to paint all the letters. But for each color, there must be a letter painted in that color.
     24 
     25 Then you can swap any two symbols painted in the same color as many times as you want.
     26 
     27 After that, $k$ strings will be created, $i$-th of them will contain all the characters colored in the color $i$, written in the order of their sequence in the string $s$.
     28 
     29 Your task is to color the characters of the string so that all the resulting $k$ strings are palindromes, and the length of the shortest of these $k$ strings is as large as possible.
     30 
     31 Read the note for the first test case of the example if you need a clarification.
     32 
     33 Recall that a string is a palindrome if it reads the same way both from left to right and from right to left. For example, the strings abacaba, cccc, z and dxd are palindromes, but the strings abab and aaabaa — are not.
     34 
     35 Input
     36 
     37 The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of input data sets in the test.
     38 
     39 The descriptions of the input data sets follow.
     40 
     41 The first line of the description of each input data set contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the length of the string and the number of colors in which its letters can be painted. The second line of the description of each input data set contains a string $s$ of length $n$ consisting of lowercase letters of the Latin alphabet.
     42 
     43 It is guaranteed that the sum of n over all test cases does not exceed $2 \cdot 10^5$.
     44 
     45 Output
     46 
     47 For each set of input data, output a single integer  — the maximum length of the shortest palindrome string that can be obtained.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 10
     55 
     56 8 2
     57 
     58 bxyaxzay
     59 
     60 6 3
     61 
     62 aaaaaa
     63 
     64 6 1
     65 
     66 abcdef
     67 
     68 6 6
     69 
     70 abcdef
     71 
     72 3 2
     73 
     74 dxd
     75 
     76 11 2
     77 
     78 abcabcabcac
     79 
     80 6 6
     81 
     82 sipkic
     83 
     84 7 2
     85 
     86 eatoohd
     87 
     88 3 1
     89 
     90 llw
     91 
     92 6 2
     93 
     94 bfvfbv
     95 ```
     96 
     97 Output
     98 
     99 ```
    100 3
    101 2
    102 1
    103 1
    104 1
    105 5
    106 1
    107 1
    108 3
    109 3
    110 ```
    111 
    112 Note
    113 
    114 * In the first test case, $s$="bxyaxzay", $k=2$. We use indices in the string from $1$ to $8$. The following coloring will work: $\mathtt{\mathbf{\color{red}{b}\color{blue}{xy}\color{red}{a}\color{blue}{x}z\color{red}{a}\color{blue}{y}}}$ (the letter z remained uncolored). After painting:
    115   + swap two red characters (with the indices $1$ and $4$), we get $\mathtt{\mathbf{\color{red}{a}\color{blue}{xy}\color{red}{b}\color{blue}{x}z\color{red}{a}\color{blue}{y}}}$;
    116   + swap two blue characters (with the indices $5$ and $8$), we get $\mathtt{\mathbf{\color{red}{a}\color{blue}{xy}\color{red}{b}\color{blue}{y}z\color{red}{a}\color{blue}{x}}}$.
    117 
    118   Now, for each of the two colors we write out the corresponding characters from left to right, we get two strings $\mathtt{\mathbf{\color{red}{aba}}}$ and $\mathtt{\mathbf{\color{blue}{xyyx}}}$. Both of them are palindromes, the length of the shortest is $3$. It can be shown that the greatest length of the shortest palindrome cannot be achieved.
    119 * In the second set of input data, the following coloring is suitable: $[1, 1, 2, 2, 3, 3]$. There is no need to swap characters. Both received strings are equal to aa, they are palindromes and their length is $2$.
    120 * In the third set of input data, you can color any character and take it into a string.
    121 * In the fourth set of input data, you can color the $i$th character in the color $i$.
    122 * In the fifth set of input data can be colored in each of the colors of one character.
    123 * In the sixth set of input data, the following coloring is suitable: $[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 0]$. Rearrange the characters so as to get the palindromes abcba and acbca.