codeforces-scrape

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

1316B.md (2779B)


      1 Source: https://codeforces.com/problemset/problem/1316/B
      2 
      3 B. String Modification
      4 
      5 time limit per test
      6 
      7 1 second
      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 Vasya has a string $s$ of length $n$. He decides to make the following modification to the string:
     22 
     23 1. Pick an integer $k$, ($1 \leq k \leq n$).
     24 2. For $i$ from $1$ to $n-k+1$, reverse the substring $s[i:i+k-1]$ of $s$. For example, if string $s$ is qwer and $k = 2$, below is the series of transformations the string goes through:
     25    * qwer (original string)
     26    * wqer (after reversing the first substring of length $2$)
     27    * weqr (after reversing the second substring of length $2$)
     28    * werq (after reversing the last substring of length $2$)Hence, the resulting string after modifying $s$ with $k = 2$ is werq.
     29 
     30 Vasya wants to choose a $k$ such that the string obtained after the above-mentioned modification is lexicographically smallest possible among all choices of $k$. Among all such $k$, he wants to choose the smallest one. Since he is busy attending Felicity 2020, he asks for your help.
     31 
     32 A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds:
     33 
     34 * $a$ is a prefix of $b$, but $a \ne b$;
     35 * in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.
     36 
     37 Input
     38 
     39 Each test contains multiple test cases.
     40 
     41 The first line contains the number of test cases $t$ ($1 \le t \le 5000$). The description of the test cases follows.
     42 
     43 The first line of each test case contains a single integer $n$ ($1 \le n \le 5000$) — the length of the string $s$.
     44 
     45 The second line of each test case contains the string $s$ of $n$ lowercase latin letters.
     46 
     47 It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.
     48 
     49 Output
     50 
     51 For each testcase output two lines:
     52 
     53 In the first line output the lexicographically smallest string $s'$ achievable after the above-mentioned modification.
     54 
     55 In the second line output the appropriate value of $k$ ($1 \leq k \leq n$) that you chose for performing the modification. If there are multiple values of $k$ that give the lexicographically smallest string, output the smallest value of $k$ among them.
     56 
     57 Example
     58 
     59 Input
     60 
     61 ```
     62 6
     63 4
     64 abab
     65 6
     66 qwerty
     67 5
     68 aaaaa
     69 6
     70 alaska
     71 9
     72 lfpbavjsm
     73 1
     74 p
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 abab
     81 1
     82 ertyqw
     83 3
     84 aaaaa
     85 1
     86 aksala
     87 6
     88 avjsmbpfl
     89 5
     90 p
     91 1
     92 ```
     93 
     94 Note
     95 
     96 In the first testcase of the first sample, the string modification results for the sample abab are as follows :
     97 
     98 * for $k = 1$ : abab
     99 * for $k = 2$ : baba
    100 * for $k = 3$ : abab
    101 * for $k = 4$ : baba
    102 
    103   The lexicographically smallest string achievable through modification is abab for $k = 1$ and $3$. Smallest value of $k$ needed to achieve is hence $1$.