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]$.