algorithms

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

problem.txt (2861B)


      1 C. Remove the Ends
      2 Finished
      3 Practice
      4 time limit per test: 3 seconds
      5 memory limit per test: 256 megabytes
      6 You have an array a of length n consisting of non-zero integers. Initially, you have 0 coins,
      7 and you will do the following until a is empty:
      8 • Let m be the current size of a. Select an integer i where 1 ≤ i ≤ m , gain |ai | ∗ coins,
      9 and then:
     10 ◦ if ai < 0, then replace a with [a1 , a2 , … , ai−1 ] (that is, delete the suffix beginning
     11 with ai );
     12 ◦ otherwise, replace a with [ai+1 , ai+2 , … , am ] (that is, delete the prefix ending with
     13 ai ).
     14 → Virtual participation
     15 Virtual contest is a way to take part in past contest,
     16 as close as possible to participation on time. It is
     17 supported only ICPC mode for virtual contests. If
     18 you've seen these problems, a virtual contest is not
     19 for you - solve these problems in the archive. If you
     20 just want to solve some problem from a contest, a
     21 virtual contest is not for you - solve this problem in
     22 the archive. Never use someone else's code, read
     23 the tutorials or communicate with other person
     24 during a virtual contest.
     25 Find the maximum number of coins you can have at the end of the process.
     26 ∗
     27     28 Start virtual contest
     29 Here |ai | represents the absolute value of ai : it equals ai when ai > 0 and −ai when ai < 0 .
     30 
     31 ---
     32 
     33 - array a of size n
     34 - all non-zeros
     35 - start with 0 coins
     36 - do while size != n:
     37     - select an element of a and add |a_i| coins
     38         - one indexed, from 1 -> m (where m is remaining coins)
     39     - if a_i < 0 then delete the suffix beginning with a_i
     40     - else delete the prefix beginning with a_i
     41 - compute max coins possible
     42 ---
     43 
     44 thoughts:
     45 
     46 we see that state at a given point in time is a triple:
     47     - (left, right, coins)
     48     - where left is the leftmost element that hasn't been dropped
     49     - where right is the rightmost element that hasn't been dropped
     50     - we can do this because the left and right are removed in order
     51 
     52 seems easily dp, but could also be a simple greedy approach that might be cheaper
     53 
     54 ---
     55 
     56 while the leftmost element is >= 0, we should always take it
     57 while the rightmost element is < 0, we should always take it
     58 
     59 
     60 ---
     61 
     62 6
     63 3 1 4 -1 -5 -9
     64 
     65 take 3,1, and 4
     66 
     67 -1 -5 -9
     68 
     69 take -9,-5,-1
     70 
     71 we get 8 + 15 = 23
     72 
     73 ---
     74 
     75 6
     76 -10 -3 -17 1 19 20
     77 
     78 
     79 in the bad cases, we are most interested in the righmost negative, and the leftmost positive.
     80 
     81 we could do either: 1, 19, 20
     82 or: -17,-3,-10
     83 
     84 vs 30
     85 vs 40
     86 
     87 so we take the 40
     88 
     89 ---
     90 
     91 1
     92 1
     93 
     94 ---
     95 
     96 these examples are kinda trash because they don't have complex combinations, or is this just a general problem?
     97 
     98 like we first check leftmost, rightmost, then left run, right run?
     99 
    100 what about inner options
    101 
    102 ---
    103 
    104 maybe we just do a naive dp approach because it seems in any case we'll have to do some amount of backtracking. 
    105 
    106 this approach is as follows:
    107 
    108 - compute best from given state where:
    109     - state := (left,right)