algorithms

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

problem.txt (2163B)


      1 C. Maximize the Score
      2 time limit per test2 seconds
      3 memory limit per test256 megabytes
      4 You are given an array a
      5  of length 2n
      6 . Each integer from 1
      7  to n
      8  occurs exactly twice in a
      9 .
     10 
     11 Initially, your score is 0
     12 .
     13 
     14 You can repeatedly perform the following operation while a
     15  is non-empty:
     16 
     17 Choose an integer x
     18  that is present in a
     19 .
     20 Let l
     21  and r
     22  be the indices of the leftmost and rightmost occurrences of x
     23  in the current array, respectively. If x
     24  occurs only once, then l=r
     25 .
     26 Add (r−l+1)2
     27  to your score.
     28 Delete the elements al,al+1,…,ar
     29  from a
     30 . The remaining elements are concatenated without changing their order and re-indexed starting from 1
     31 .
     32 Find the maximum possible score after making the array empty.
     33 
     34 Input
     35 Each test contains multiple test cases. The first line contains the number of test cases t
     36  (1≤t≤104
     37 ). The description of the test cases follows.
     38 
     39 The first line of each test case contains a single integer n
     40  (1≤n≤2⋅105
     41 ).
     42 
     43 The second line contains 2n
     44  integers a1,a2,…,a2n
     45  (1≤ai≤n
     46 ).
     47 
     48 It is guaranteed that each integer from 1
     49  to n
     50  occurs exactly twice in a
     51 .
     52 
     53 It is guaranteed that the sum of n
     54  over all test cases does not exceed 2⋅105
     55 .
     56 
     57 ---
     58 
     59 - array a, size 2n
     60     - include each number from 1->n twice
     61 - score := 0
     62 - while a isn't empty you can do these steps if you want:
     63     - choose an int x in a
     64     - l = leftmost index of int x, r = rightmost index of int x 
     65         - iff only one x then l == r
     66     - add (r - l + 1) ^ 2 to score
     67     - delete a_l, a_l+1, ... a_r from array
     68 
     69 ---
     70 
     71 examples:
     72 
     73 ---
     74 
     75 ex1
     76 
     77 1 1
     78 
     79 drop 1, (r - l+1) ^ 2 = 4
     80 score = 4
     81 
     82 ---
     83 
     84 ex2
     85 
     86 1 2 1 2
     87 
     88 3-1 + 1 = 3
     89 
     90 3**2 = 9
     91 
     92 (0 - 0+1) ** 2 = 1
     93 
     94 res=10
     95 
     96 this could also be considered the spread with the largest score.
     97 
     98 ---
     99 
    100 1 2 2 1
    101 
    102 (3 - 0 + 1) ^ 2 = 16
    103 
    104 differ from inner first:
    105 
    106 (2 - 1 + 1) ^ 2 = 4
    107 (1 - 0 + 1) ^ 2 = 4
    108 
    109 = 8
    110 
    111 ---
    112 
    113 1 1 2 3 3 2
    114 
    115 (5 - 2 + 1) ^ 2 = 16
    116 
    117 1 1
    118 
    119 (1 - 0 + 1) ^ 2 = 4
    120 
    121 = 20
    122 
    123 
    124 ---
    125 
    126 1 2 3 3 2 1
    127 
    128 (5 - 0 + 1) ^ 2 = 36
    129 
    130 
    131 ---
    132 
    133 1 2 3 4 1 2 3 4
    134 
    135 (4 - 0 + 1) ^ 2 = 25
    136 
    137 2 3 4
    138 
    139 (0 - 0 + 1) ^ 2 = 1
    140 (0 - 0 + 1) ^ 2 = 1
    141 (0 - 0 + 1) ^ 2 = 1
    142 
    143 25 + 3 = 28
    144 
    145 it'd be equivalent to remove in either order so just remove first I guess