algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

problem.txt (2073B)


      1 C. Zero-Sum Prefixes
      2 time limit per test
      3 1 second
      4 memory limit per test
      5 256 megabytes
      6 
      7 The score of an array v1,v2,…,vn is defined as the number of indices i (1≤i≤n) such that v1+v2+…+vi=0.
      8 
      9 You are given an array a1,a2,…,an of length n. You can perform the following operation multiple times:
     10 
     11     select an index i (1≤i≤n) such that ai=0;
     12     then replace ai by an arbitrary integer. 
     13 
     14 What is the maximum possible score of a that can be obtained by performing a sequence of such operations?
     15 Input
     16 
     17 Each test contains multiple test cases. The first line contains a single integer t (1≤t≤104) — the number of test cases.
     18 
     19 The first line of each test case contains one integer n (1≤n≤2⋅105) — the length of the array a.
     20 
     21 The second line of each test case contains n integers a1,a2,…,an (−109≤ai≤109) — array a.
     22 
     23 It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
     24 Output
     25 
     26 For each test case, print the maximum possible score of the array a after performing a sequence of operations.
     27 
     28 ---
     29 
     30 problem:
     31 
     32 - sum := number of indices where all prior values + current == 0
     33 - operation
     34     - select an index s.t. a[i] == 0 and replace it with any number
     35     - we can do this as many times as we want
     36         - don't have to though
     37 - return max score where we can perform the ops
     38 
     39 ---
     40 
     41 ex1: 
     42 
     43 2 0 1 -1 0
     44 
     45 2 2 3 2 2
     46 
     47 2 -2 1 -1 0
     48 
     49 2 0 1 0 0
     50 
     51 heuristic here was to compute the prefix sums, check sums to the right and 
     52 if number of zeroes < most popular other number, substitute the zero with the 
     53 inversion of the most popular number.
     54 
     55 ex2:
     56 
     57 1000000000 1000000000 0
     58 
     59 1000000000 2000000000 2000000000 
     60 
     61 1000000000 1000000000 -2000000000 
     62 
     63 1000000000 2000000000 0
     64 
     65 The heuristic should be inclusive of the a_i index
     66 
     67 ex3:
     68 
     69 0 0 0 0
     70 
     71 0 0 0 0
     72 
     73 4
     74 
     75 ex4:
     76 
     77 3 0 2 -10 10 -30 30 0
     78 
     79 3 3 5  -5  5 -25  5 5
     80 
     81 3 -5 2 -10 10 -30 30 0
     82 
     83 3 -2 0 -10 0 -30 0 0
     84 
     85 We only care about the sums between zeroes
     86 
     87 ex5:
     88 
     89 1 0 0 1 -1 0 1 0 -1
     90 
     91 1 1 1 2  1 1 2 2  1
     92 
     93 1 -1 0 1 -1 0 1 0 -1
     94 
     95 1 0  0 1  0 0 1 1 0
     96 
     97 1 -1 0 1 -1 -1 1 0 -1
     98 
     99 1 0  0 1 0  -1 0 0 -1