codeforces-scrape

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

2155C.md (2927B)


      1 Source: https://codeforces.com/problemset/problem/2155/C
      2 
      3 C. The Ancient Wizards' Capes
      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 There are $n$ wizards in a row numbered $1$ to $n$ from left to right. Each wizard has an invisibility cape which can be worn either on his left side or on his right side. Harry walks from the position of wizard $1$ until the position of wizard $n$ ($1 \le n \le 10^5$), and registers how many wizards he sees from each wizard's position. A wizard in position $j$ is visible from position $i$ if:
     22 
     23 * Wizard $j$ wears his cape on his left side and $i \ge j$.
     24 * Wizard $j$ wears his cape on his right side and $i \le j$.
     25 
     26 In particular, note that wizard $i$ is visible from position $i$.
     27 
     28 Harry's list is very old but, after much work, you managed to decipher it. The list is an array $a$ of $n$ elements, where the $i$-th element $a_i$ ($1 \le a_i \le n$) is the number of wizards that Harry saw from the position of wizard $i$.
     29 
     30 Your task is to determine how many of all the possible cape arrangements that Harry could have seen are consistent with the data recorded by the list, modulo $676\,767\,677$.
     31 
     32 Input
     33 
     34 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.
     35 
     36 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the length of $a$.
     37 
     38 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the elements of $a$.
     39 
     40 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     41 
     42 Output
     43 
     44 For each test case, print one integer — the number of arrangements for the wizards' capes that satisfy the condition, modulo $676\,767\,677$.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 7
     52 
     53 1
     54 
     55 1
     56 
     57 4
     58 
     59 4 4 3 2
     60 
     61 3
     62 
     63 1 3 2
     64 
     65 2
     66 
     67 2 1
     68 
     69 3
     70 
     71 2 2 2
     72 
     73 3
     74 
     75 3 2 3
     76 
     77 3
     78 
     79 3 2 2
     80 ```
     81 
     82 Output
     83 
     84 ```
     85 2
     86 
     87 1
     88 
     89 0
     90 
     91 1
     92 
     93 2
     94 
     95 0
     96 
     97 0
     98 ```
     99 
    100 Note
    101 
    102 The image below shows an arrangement of capes that matches Harry's list in the second test case.
    103 
    104  ![](https://espresso.codeforces.com/0680da940a0d05d53a0361d89529a6fb2b48278a.png) 
    105 
    106 Wizard 1 has the invisibility cape on his left side, while wizards $2$, $3$, and $4$ wear it on their right side.
    107 
    108 * From position $1$, we can see wizards $1$, $2$, $3$, and $4$.
    109 * From position $2$, we can see wizards $1$, $2$, $3$, and $4$.
    110 * From position $3$, we can see wizards $1$, $3$, and $4$.
    111 * From position $4$, we can see wizards $1$ and $4$.
    112 
    113 Thus, Harry's list ends up being $[4, 4, 3, 2]$. It can be proved that this is the only possible arrangement.
    114 
    115 In the third test case, it can be proved that Harry could not have obtained his list from any cape arrangement.
    116 
    117 In the fifth case, note that there are two possible cape arrangements from which Harry could have gotten his list:
    118 
    119 * $1 \mid \quad \mid 2 \quad 3 \, \mid$
    120 * $\mid \, 1 \quad 2 \mid \quad \mid 3$