codeforces-scrape

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

451B.md (2037B)


      1 Source: https://codeforces.com/problemset/problem/451/B
      2 
      3 B. Sort the Array
      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 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Being a programmer, you like arrays a lot. For your birthday, your friends have given you an array *a* consisting of *n* distinct integers.
     22 
     23 Unfortunately, the size of *a* is too small. You want a bigger array! Your friends agree to give you a bigger array, but only if you are able to answer the following question correctly: is it possible to sort the array *a* (in increasing order) by reversing exactly one segment of *a*? See definitions of segment and reversing in the notes.
     24 
     25 Input
     26 
     27 The first line of the input contains an integer *n* (1 ≤ *n* ≤ 105) — the size of array *a*.
     28 
     29 The second line contains *n* distinct space-separated integers: *a*[1], *a*[2], ..., *a*[*n*] (1 ≤ *a*[*i*] ≤ 109).
     30 
     31 Output
     32 
     33 Print "yes" or "no" (without quotes), depending on the answer.
     34 
     35 If your answer is "yes", then also print two space-separated integers denoting start and end (start must not be greater than end) indices of the segment to be reversed. If there are multiple ways of selecting these indices, print any of them.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 3  
     43 3 2 1
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 yes  
     50 1 3
     51 ```
     52 
     53 Input
     54 
     55 ```
     56 4  
     57 2 1 3 4
     58 ```
     59 
     60 Output
     61 
     62 ```
     63 yes  
     64 1 2
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 4  
     71 3 1 2 4
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 no
     78 ```
     79 
     80 Input
     81 
     82 ```
     83 2  
     84 1 2
     85 ```
     86 
     87 Output
     88 
     89 ```
     90 yes  
     91 1 1
     92 ```
     93 
     94 Note
     95 
     96 Sample 1. You can reverse the entire array to get [1, 2, 3], which is sorted.
     97 
     98 Sample 3. No segment can be reversed such that the array will be sorted.
     99 
    100 Definitions
    101 
    102 A segment [*l*, *r*] of array *a* is the sequence *a*[*l*], *a*[*l* + 1], ..., *a*[*r*].
    103 
    104 If you have an array *a* of size *n* and you reverse its segment [*l*, *r*], the array will become:
    105 
    106 *a*[1], *a*[2], ..., *a*[*l* - 2], *a*[*l* - 1], *a*[*r*], *a*[*r* - 1], ..., *a*[*l* + 1], *a*[*l*], *a*[*r* + 1], *a*[*r* + 2], ..., *a*[*n* - 1], *a*[*n*].