codeforces-scrape

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

2049B.md (2585B)


      1 Source: https://codeforces.com/problemset/problem/2049/B
      2 
      3 B. pspspsps
      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 Cats are attracted to pspspsps, but Evirir, being a dignified dragon, is only attracted to pspspsps with oddly specific requirements...
     22 
     23 Given a string $s = s_1s_2\ldots s_n$ of length $n$ consisting of characters p, s, and . (dot), determine whether a permutation$^{\text{∗}}$ $p$ of length $n$ exists, such that for all integers $i$ ($1 \le i \le n$):
     24 
     25 * If $s_i$ is p, then $[p_1, p_2, \ldots, p_i]$ forms a permutation (of length $i$);
     26 * If $s_i$ is s, then $[p_i, p_{i+1}, \ldots, p_{n}]$ forms a permutation (of length $n-i+1$);
     27 * If $s_i$ is ., then there is no additional restriction.
     28 
     29 $^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
     30 
     31 Input
     32 
     33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     34 
     35 The first line of each test case contains a single integer $n$ ($1 \le n \le 500$), the length of $s$.
     36 
     37 The second line of each test case contains a string $s$ of length $n$ that consists of the characters p, s, and ..
     38 
     39 It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.
     40 
     41 Output
     42 
     43 For each test case, output YES or NO on a line. Output YES if there is such a permutation and NO otherwise.
     44 
     45 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 9
     53 
     54 4
     55 
     56 s.sp
     57 
     58 6
     59 
     60 pss..s
     61 
     62 5
     63 
     64 ppppp
     65 
     66 2
     67 
     68 sp
     69 
     70 4
     71 
     72 .sp.
     73 
     74 8
     75 
     76 psss....
     77 
     78 1
     79 
     80 .
     81 
     82 8
     83 
     84 pspspsps
     85 
     86 20
     87 
     88 ....................
     89 ```
     90 
     91 Output
     92 
     93 ```
     94 YES
     95 NO
     96 YES
     97 YES
     98 NO
     99 NO
    100 YES
    101 NO
    102 YES
    103 ```
    104 
    105 Note
    106 
    107 For the first test case, one permutation that works is $p = [3, 4, 1, 2]$. The restrictions are as follows:
    108 
    109 * $s_1 =$ s: $[p_1, p_2, p_3, p_4] = [3, 4, 1, 2]$ forms a permutation.
    110 * $s_2 =$ .: No additional restriction.
    111 * $s_3 =$ s: $[p_3, p_4] = [1, 2]$ forms a permutation.
    112 * $s_4 =$ p: $[p_1, p_2, p_3, p_4] = [3, 4, 1, 2]$ forms a permutation.
    113 
    114 For the second test case, it can be proven that there is no permutation that satisfies all restrictions.
    115 
    116 For the third test case, one permutation that satisfies the constraints is $p = [1, 2, 3, 4, 5]$.