CCC 2015 S5 - Greedy for Pies

1# CCC 2015 Senior 5: Greedy for Pies2#3# by Daniel Whitney, Newmarket High School4#5# NOTE: This is in python 3, tho I believe it would take very little6#       to convert it to python 2 (switch range to xrange, print() to7#       print).8# NOTE: This is way over 5 seconds for the 5 M = 100 if the default9#       python interpreter (cPython) is used, but if the JIT python10#       interpreter (PyPy) is used, the longest problems finish in11#       under 3 seconds :), i don't know if that counts tho, but it12#       was legal to use PyPy in the competition this year.13#14# This problem is a dynamic programming problem, so to solve it one15# must identify a way to store the states of the problem (sub problems)16# and identify the formula to find the optimal solution to that problem.17#18# First we have to make a few observations:19#  1. There is no point in inserting two pies directly adjacent to one20#     another, as if you do you could move that set to the end of the21#     list and it would have the same effect on the total.  Give it a try22#     and you'll see it is true.23#  2. It does not matter the specific order of the inserted pies, only24#     if a pie is counted or not.  If pies are counted their order could25#     be changed with no adverse effects.  Thus if we sort the pies we26#     can insert, we can either take pies from the bottom (pies that wont27#     count) or the top (pies that will count) of the list.28#29# Now, first look at the simpler problem, finding the maximum sugar30# without inserting pies.  We could identify a state as including all the31# pies up to a point (for example the first 5 pies).  We define two32# functions, one function will include the last pie on the list, the other33# will not.  I'll call these function I and E (include and exclude).  We34# can deduce that the value of I for a number of pies n, will be the35# maximum of E of n-1 plus the value if the nth pie or I of n-1. The36# solution is thus the maximum of I of number of pies or E of number of37# pies.38#39# For this problem we have to expand the state to include the inserted40# pies, so we add three more varables to the state, m for number of pies41# taken from the bottom of the sorted list of pies to add (they wont add42# to the total), M for number of pies taken from the top of the sorted43# list of pies to add (they will add to the total), and l to indicate if44# the last pie added was from the original list, or the new list.  l = 045# indicates last item taken from original list, l = 1 indicates last item46# taken from the insertion list.  Therefore if the I function takes from47# the new list it must take from the top of the list as the item will be48# included,and vise versa for the E function.49#50# Also we must ignore any state with a negative n, m, or M as they don't51# exist.52#53# Also note the base states for this function are simple, the state of54# just one item taken from the original list, or just one item from the55# top or bottom of the list of pies to be inserted.56#57# The new formulas are as follows:58#   I of n, m, M, l = the maximum of59#       E of n, m-1, M, 1   if  l is = 0 because we cant have adjacent inserted pies60#       E of n-1, m, M, 0   if  m+M != n+1 because if we remove an item from the original list61#                                          the remainder would have two more inserted items than62#                                          original items which would indicate adjacent insertions.63#64#       also if the last item inserted is from the new list (l = 1) and the state has the maximum65#       number of pies from the inserted list, then this state cannot exist and is skipped.66#67#       finally you would add the value of the added pie as the I function includes the last pie68#69#   E of n, m, M, l = the maximum of70#       E of n, m-1, M, 1 or71#       I of n, m, M-1, 1   if  l is = 0 because we cant have adjacent inserted pies72#       I of n-1, m, M, 073#       E of n-1, m, M, 0   if  m+M != n+1 because if we remove an item from the original list74#                                          the remainder would have two more inserted items than75#                                          original items which would indicate adjacent insertions.76#77#       if the last item inserted is from the new list (l = 1) and the state has the maximum78#       number of pies from the inserted list, then this state cannot exist and is skipped.79#80#       the value of the last pie is not added as the E function excluded the last pie81#82# We can calculate the values of these states from the bottom up (or83# iteratively) as the value of one function only relies on the values84# of the functions below it (with numbers lass than or equal to it).85#86# There is one final messy step, we must iterate through every state that87# contains all of the original list, and append to the end the optimal88# ordering of the remaining pies we could add.  This is simple, for an E89# function we simply add the sum of the upper half of the list of remaining90# pies to the list, and include the center pie if there's is an odd number91# of pies, and exclude this center pie for the I functions.  We then return92# the maximum sums of all these lists.93 94 95file = open('s5.15.in')96N = int(file.readline())97L = [int(file.readline()) for n in range(N)] + [0]  # read the ordered list of pies into a list98P = int(file.readline())99A = [int(file.readline()) for m in range(P)]        # read the pies to be inserted into a list and sort it100A.sort()101 102# Because of the versatile but slow nature of python's lists, I condensed103# what was a 5D array (first index was 0 or 1 to indicate I or E,104# second was n, third was m, etc.) but it took longer to initialize the105# list than actually calculate the states.  Using one list and multiplying106# the indexes by fixed numbers to simulate a multidimensional array was107# more than 6x faster.108 109# these are the factors to multiply the indices by110s5 = 1111s4 = 2*s5112s3 = (P+1)*s4113s2 = (P+1)*s3114s1 = (N+1)*s2115 116# this will hold all of the states117s = [0]*(2*s1)118 119# these are the bases states120s[0] = L[0]121if P != 0:122    s[1] = A[-1]123 124# loop through every possible valid state, in the order were all of the prerequisite states are already calculated.125for n in range(N+1):126    for m in range(min(n+1, P)+1):127        for M in range(min(n+1, P)+1-m):128            # we calculate the value of I and E for a state at the same129            #  time, first when the last item is from the original list130            max_i = 0131            max_e = 0132            # include a case only if the case is valid133            # include states where the last pie is from the insertion list134            if m > 0:135                max_i = s[1*s1 + n*s2 + (m-1)*s3 + M*s4 + 1]136                max_e = s[1*s1 + n*s2 + (m-1)*s3 + M*s4 + 1]137            if M > 0:138                max_e = max(s[n*s2 + m*s3 + (M-1)*s4 + 1], max_e)139            # include states where the last pie is from the original list140            if M+m != n+1 and n > 0:141                max_i = max(s[1*s1 + (n-1)*s2 + m*s3 + M*s4], max_i)142                max_e = max(s[1*s1 + (n-1)*s2 + m*s3 + M*s4], s[(n-1)*s2 + m*s3 + M*s4], max_e)143            # calculate the value of the I function144            s[n*s2 + m*s3 + M*s4] = max_i + L[n]145            # calculate the value of the E function146            s[1*s1 + n*s2 + m*s3 + M*s4] = max_e147            # now calculate the value of the functions when the last item is from the insertion list148            if M+m != P and M+m != n+1 and n > 0:149                # if the last item inserted is from the new list (l = 1) and the state has the maximum150                # number of pies from the inserted list, then this state cannot exist and is skipped151                # or if the number of inserted pies equals the total number of inserted pies it is skipped152                # include the cases where the last pie is from the original case if the case is valid153                max_i = s[1*s1 + (n-1)*s2 + m*s3 + M*s4]154                max_e = max(s[1*s1 + (n-1)*s2 + m*s3 + M*s4], s[(n-1)*s2 + m*s3 + M*s4])155                s[n*s2 + m*s3 + M*s4 + 1] = max_i + A[-M-1]156                s[1*s1 + n*s2 + m*s3 + M*s4 + 1] = max_e157 158# finally add the sums of the leftover pies159final_max = 0160for m in range(min(N+1, P)+1):161    for M in range(min(N+1, P)+1-m):162        # rA is all the pies we didn't add to the list163        if M == 0:164            rA = A[m:]165        else:166            rA = A[m:-M]167        final_max = max(final_max,168                        s[1*s1+(N-1)*s2+m*s3+M*s4] + sum(rA[len(rA)//2:]),169                        s[(N-1)*s2+m*s3+M*s4] + sum(rA[-((-len(rA))//2):]))170                                    # this strange statement causes upward rounding as opposed to downwards171        if M+m != P or M+m != N+1:172            if M == 0:173                rA = A[m+1:]174            else:175                rA = A[m+1:-M]176            final_max = max(final_max, s[1*s1+n*s2+m*s3+M*s4+1] + sum(rA[len(rA)//2:]))177            rA = A[m:-M-1]178            final_max = max(final_max, s[n*s2+m*s3+M*s4+1] + sum(rA[-((-len(rA))//2):]))179 180print(final_max)181