codeforces-scrape

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

1983C.md (3891B)


      1 Source: https://codeforces.com/problemset/problem/1983/C
      2 
      3 C. Have Your Cake and Eat It Too
      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 Alice, Bob and Charlie want to share a rectangular cake cut into $n$ pieces. Each person considers every piece to be worth a different value. The $i$-th piece is considered to be of value $a_i$ by Alice, $b_i$ by Bob and $c_i$ by Charlie.
     22 
     23 The sum over all $a_i$, all $b_i$ and all $c_i$ individually is the same, equal to $tot$.
     24 
     25 Given the values of each piece of the cake for each person, you need to give each person a contiguous slice of cake. In other words, the indices at the left and right ends of these subarrays (the slices given to each person) can be represented as $(l_a, r_a)$, $(l_b, r_b)$ and $(l_c, r_c)$ respectively for Alice, Bob and Charlie. The division needs to satisfy the following constraints:
     26 
     27 * No piece is assigned to more than one person, i.e., no two subarrays among $[l_a,\ldots,r_a]$, $[l_b, \ldots, r_b]$ and $[l_c, \ldots, r_c]$ intersect.
     28 * $ \sum_{i = l_a}^{r_a} a_i, \sum_{i = l_b}^{r_b} b_i, \sum_{i = l_c}^{r_c} c_i \geq \lceil \frac{tot}{3} \rceil$.
     29 
     30 Here, the notation $\lceil \frac{a}{b} \rceil$ represents ceiling division. It is defined as the smallest integer greater than or equal to the exact division of $a$ by $b$. In other words, it rounds up the division result to the nearest integer. For instance $\lceil \frac{10}{3} \rceil = 4$ and $\lceil \frac{15}{3} \rceil = 5$.
     31 
     32 Input
     33 
     34 The first line contains an integer $t$, the number of testcases, ($1 \le t \le 10^4$)
     35 
     36 For each testcase:
     37 
     38 The first line contains the integer $n$ ($3 \le n \le 2 \cdot 10^5$).
     39 
     40 The following three lines contain $n$ integers each:
     41 
     42 One line with $n$ integers $a_1, a_2, \ldots, a_n$ represents the values for Alice ($1 \le a_i \le 10^6$).
     43 
     44 The next line with $n$ integers $b_1, b_2, \ldots, b_n$ represents the values for Bob ($1 \le b_i \le 10^6$).
     45 
     46 The next line with $n$ integers $c_1, c_2, \ldots, c_n$ represents the values for Charlie ($1 \le c_i \le 10^6$).
     47 
     48 It is guaranteed that $ \sum_{i = 1}^{n} a_i = \sum_{i = 1}^{n} b_i = \sum_{i = 1}^{n} c_i$.
     49 
     50 The sum of $n$ over all testcases does not exceed $2 \cdot 10^5$.
     51 
     52 Output
     53 
     54 For each testcase, output $-1$ if the required condition is impossible.
     55 
     56 Otherwise, output six numbers – $l_a, r_a, l_b, r_b, l_c, r_c$, the respective starting and ending indices ($1$-indexed) of the subarrays for Alice, Bob and Charlie, respectively.
     57 
     58 Example
     59 
     60 Input
     61 
     62 ```
     63 10
     64 
     65 5
     66 
     67 5 1 1 1 1
     68 
     69 1 1 5 1 1
     70 
     71 1 1 1 1 5
     72 
     73 6
     74 
     75 1 2 3 4 5 6
     76 
     77 5 6 1 2 3 4
     78 
     79 3 4 5 6 1 2
     80 
     81 4
     82 
     83 4 4 4 4
     84 
     85 4 4 4 4
     86 
     87 4 4 4 4
     88 
     89 5
     90 
     91 5 10 5 2 10
     92 
     93 9 6 9 7 1
     94 
     95 10 7 10 2 3
     96 
     97 3
     98 
     99 4 5 2
    100 
    101 6 1 4
    102 
    103 1 8 2
    104 
    105 3
    106 
    107 10 4 10
    108 
    109 8 7 9
    110 
    111 10 4 10
    112 
    113 7
    114 
    115 57113 65383 19795 53580 74452 3879 23255
    116 
    117 12917 16782 89147 93107 27365 15044 43095
    118 
    119 33518 63581 33565 34112 46774 44151 41756
    120 
    121 6
    122 
    123 6 3 1 8 7 1
    124 
    125 10 2 6 2 2 4
    126 
    127 10 9 2 1 2 2
    128 
    129 5
    130 
    131 5 5 4 5 5
    132 
    133 1 6 3 8 6
    134 
    135 2 4 1 9 8
    136 
    137 10
    138 
    139 1 1 1 1 1001 1 1 1001 1 1
    140 
    141 1 1 1 1 1 1 2001 1 1 1
    142 
    143 1 1 1 1 1 1001 1 1 1 1001
    144 ```
    145 
    146 Output
    147 
    148 ```
    149 1 1 2 3 4 5 
    150 5 6 1 2 3 4 
    151 -1
    152 -1
    153 1 1 3 3 2 2 
    154 -1
    155 1 2 3 4 5 7 
    156 3 6 1 1 2 2 
    157 1 2 3 4 5 5 
    158 1 5 6 7 8 10
    159 ```
    160 
    161 Note
    162 
    163 In the first testcase, the sum of either of the three arrays is $9$. Each person needs a cake slice corresponding to a subarray with a total value of at least $\lceil \frac{9}{3} \rceil = 3$.
    164 
    165 If we assign the subarray ($1$,$1$) to Alice, its total value to her is $5$, which is $\ge 3$; the subarray ($2$,$3$) to Bob, its total value to him is $1 + 5 = 6$, which is $\ge 3$; and the subarray ($4$,$5$) to Charlie, its total value to him $1 + 5 = 6$, which is also $\ge 3$. Each person gets their own separate pieces of the cake, and no piece is common to two or more people.
    166 
    167 It can be shown that for the third test case, it is not possible to give slices of the cake in a way that satisfies the given constraints.