codeforces-scrape

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

1980D.md (2469B)


      1 Source: https://codeforces.com/problemset/problem/1980/D
      2 
      3 D. GCD-sequence
      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 GCD (Greatest Common Divisor) of two integers $x$ and $y$ is the maximum integer $z$ by which both $x$ and $y$ are divisible. For example, $GCD(36, 48) = 12$, $GCD(5, 10) = 5$, and $GCD(7,11) = 1$.
     22 
     23 Kristina has an array $a$ consisting of exactly $n$ positive integers. She wants to count the GCD of each neighbouring pair of numbers to get a new array $b$, called GCD-sequence.
     24 
     25 So, the elements of the GCD-sequence $b$ will be calculated using the formula $b_i = GCD(a_i, a_{i + 1})$ for $1 \le i \le n - 1$.
     26 
     27 Determine whether it is possible to remove exactly one number from the array $a$ so that the GCD sequence $b$ is non-decreasing (i.e., $b_i \le b_{i+1}$ is always true).
     28 
     29 For example, let Khristina had an array $a$ = [$20, 6, 12, 3, 48, 36$]. If she removes $a_4 = 3$ from it and counts the GCD-sequence of $b$, she gets:
     30 
     31 * $b_1 = GCD(20, 6) = 2$
     32 * $b_2 = GCD(6, 12) = 6$
     33 * $b_3 = GCD(12, 48) = 12$
     34 * $b_4 = GCD(48, 36) = 12$
     35 
     36 The resulting GCD sequence $b$ = [$2,6,12,12$] is non-decreasing because $b_1 \le b_2 \le b_3 \le b_4$.
     37 
     38 Input
     39 
     40 The first line of input data contains a single number $t$ ($1 \le t \le 10^4$) — he number of test cases in the test.
     41 
     42 This is followed by the descriptions of the test cases.
     43 
     44 The first line of each test case contains a single integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of elements in the array $a$.
     45 
     46 The second line of each test case contains exactly $n$ integers $a_i$ ($1 \le a_i \le 10^9$) — the elements of array $a$.
     47 
     48 It is guaranteed that the sum of $n$ over all test case does not exceed $2 \cdot 10^5$.
     49 
     50 Output
     51 
     52 For each test case, output a single line:
     53 
     54 * "YES" if you can remove exactly one number from the array $a$ so that the GCD-sequence of $b$ is non-decreasing;
     55 * "NO" otherwise.
     56 
     57 You can output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will all be recognized as a positive answer).
     58 
     59 Example
     60 
     61 Input
     62 
     63 ```
     64 12
     65 
     66 6
     67 
     68 20 6 12 3 48 36
     69 
     70 4
     71 
     72 12 6 3 4
     73 
     74 3
     75 
     76 10 12 3
     77 
     78 5
     79 
     80 32 16 8 4 2
     81 
     82 5
     83 
     84 100 50 2 10 20
     85 
     86 4
     87 
     88 2 4 8 1
     89 
     90 10
     91 
     92 7 4 6 2 4 5 1 4 2 8
     93 
     94 7
     95 
     96 5 9 6 8 5 9 2
     97 
     98 6
     99 
    100 11 14 8 12 9 3
    101 
    102 9
    103 
    104 5 7 3 10 6 3 12 6 3
    105 
    106 3
    107 
    108 4 2 4
    109 
    110 8
    111 
    112 1 6 11 12 6 12 3 6
    113 ```
    114 
    115 Output
    116 
    117 ```
    118 YES
    119 NO
    120 YES
    121 NO
    122 YES
    123 YES
    124 NO
    125 YES
    126 YES
    127 YES
    128 YES
    129 YES
    130 ```
    131 
    132 Note
    133 
    134 The first test case is explained in the problem statement.