codeforces-scrape

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

1155A.md (2102B)


      1 Source: https://codeforces.com/problemset/problem/1155/A
      2 
      3 A. Reverse a Substring
      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 a string $s$ consisting of $n$ lowercase Latin letters.
     22 
     23 Let's define a substring as a contiguous subsegment of a string. For example, "acab" is a substring of "abacaba" (it starts in position $3$ and ends in position $6$), but "aa" or "d" aren't substrings of this string. So the substring of the string $s$ from position $l$ to position $r$ is $s[l; r] = s_l s_{l + 1} \dots s_r$.
     24 
     25 You have to choose exactly one of the substrings of the given string and reverse it (i. e. make $s[l; r] = s_r s_{r - 1} \dots s_l$) to obtain a string that is less lexicographically. Note that it is not necessary to obtain the minimum possible string.
     26 
     27 If it is impossible to reverse some substring of the given string to obtain a string that is less, print "NO". Otherwise print "YES" and any suitable substring.
     28 
     29 String $x$ is lexicographically less than string $y$, if either $x$ is a prefix of $y$ (and $x \ne y$), or there exists such $i$ ($1 \le i \le min(|x|, |y|)$), that $x_i \lt y_i$, and for any $j$ ($1 \le j \lt i$) $x_j = y_j$. Here $|a|$ denotes the length of the string $a$. The lexicographic comparison of strings is implemented by operator < in modern programming languages​​.
     30 
     31 Input
     32 
     33 The first line of the input contains one integer $n$ ($2 \le n \le 3 \cdot 10^5$) — the length of $s$.
     34 
     35 The second line of the input contains the string $s$ of length $n$ consisting only of lowercase Latin letters.
     36 
     37 Output
     38 
     39 If it is impossible to reverse some substring of the given string to obtain a string which is lexicographically less, print "NO". Otherwise print "YES" and two indices $l$ and $r$ ($1 \le l \lt r \le n$) denoting the substring you have to reverse. If there are multiple answers, you can print any.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 7
     47 abacaba
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 YES
     54 2 5
     55 ```
     56 
     57 Input
     58 
     59 ```
     60 6
     61 aabcfg
     62 ```
     63 
     64 Output
     65 
     66 ```
     67 NO
     68 ```
     69 
     70 Note
     71 
     72 In the first testcase the resulting string is "aacabba".