Last stone weight II - Oct. 7, 2019, 10:00 PM mock interview

LastStoneWeightII.py

'''
We have a collection of rocks, each rock has a positive integer weight.

Each turn, we choose any two rocks and smash them together.  Suppose the stones have weights x and y with x <= y.  The result of this smash is:

If x == y, both stones are totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.
At the end, there is at most 1 stone left.  Return the smallest possible weight of this stone (the weight is 0 if there are no stones left.)

 

Example 1:

Input: [2,7,4,1,8,1]
Output: 1
Explanation: 
We can combine 2 and 4 to get 2 so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1 so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0 so the array converts to [1] then that's the optimal value.
 

Note:

1 <= stones.length <= 30
1 <= stones[i] <= 100
# 
# Enjoy your interview!

'''

## 
## [2,7,4,1,8,1]
##  |   |
## [  7,2,1,8,1]
##    |     |
## [    2,1,1,1]
##      | |
## [    1,  1,1]
## [    1      ]


## [2, 7, 4]
## [2, 7] = 5  ..4  -> 1
## [7, 4] = 3  ..2 -> 1

## [1...n]
## f[0,n]: from 0 to n elements, smallest value can get
## f[0, n] = abs(f[0, i] - f[i+1, n]): minimal value for all possible i
# [2,7,4,1,8,1]
## [2, 7, 4] # smash 0, 2, and then 1
# f[0,3]: f[0,1] 2 ; f[1,2], 0; 

# [1, 8, 3]
# [1, 3, 8] sort

# f[0, 2] min val we can get

#                    [1,3]   [8]  |  [1]    [3,8]
# f[0,2] = min( abs f[0,1]-f[2,2], f[0,0]-f[1,2]  )
#        = min(      abs(2 - 8) =6,  1-abs(3-8) = 4             )
#        = min (6, 4) = 4

# Time: start, end, middle
# Time O(N*N*N)   n<=30  900*30=27000

a, b, c 
Math.Abs(Math.Abs(a-b) - c)
3 * 2 * 1 = 6 -> a, b, c
two sets -> a - b (a > b) -c 
a - (b + c)
sum of two sets 
diff of sum1 - sum2 
sum of the arry = Sum 
two sets, sum1, sum2
min(sum1 - sum2) , sum1 > sum2, 

f: sum
# sum[i]： sum from 0..i
# result = min (sum[n] - 2 *sum[j])
# O(N)
s1 + s2 = s
s1 - s2 = diff <- minimum

try to figure out s2 
line 89 - line 90
s2 * 2 = s - diff
diff = s - s2 * 2  <- like to find s2, make sure that diff is minimum 
diff >=0
s2 * 2 < s
s2 <= s/2  - another constraint 

kansacks DP - dynamic programming - 
#     [1, 1, 2, 4, 7,   8]  (1, 4, 7) (1, 2, 8)
# sum [1, 2, 4, 6, 13, 21]
# min( sum[n] - 2*sum[i])
#  21 - 2*13 | 2*6 | 2*4    # s2 <= 10, you have 13 sum is 10 from ( 1, 2, 7), 13 from set 2 (4, 8, 1)
#  21 - 2*13 = 5
# 

# first get the total sum
# find a subsum exsit so that sum-2*subSum gives the min diff

## how to get the all possible subsum?
# f[i, k] :  subsum i is possible with 0..k rocks
# f[i, k] = f[i-w[k], k-1] or f[i, k]

# 1 <= w <= 100
# maxSum = 30*100 = 3000

# time: O(3000*30=90000)
# space: O(3000*30=90000)
# f[i, n]: use 0..n rocks, can we have subsum of i?

# loop through all possible subsum:
# and record the global minval of abs(sum-2*subSum) 

    
    
# [2,7,4,1,8,1]
# [1, 1, 2, 4, 7, 8]
# [1, 1, 2] [4, 7, 8]
# [0]       [3]
# [1, 1, 2, 4] [7, 8]
# [0]          [1]
# [1]

# [1, 1, 1,30,31, 100, 100]  sorted first 
## f[0,n]: from 0 to n elements, smallest value can get
# f[0,3]
# f[start, end] = INF
# for i in range(n):
#    f[start, end] = min(f[start, end], abs(f[0,i]- f[i+1, n])) # what is definition f
# what is minV? 
# f[start, end] ? 

# f[0,n] = f[0, i] f[i+1, n]

# [1] [1, 1,30,31, 100, 100]  divide two groups, [1]
# [1, 1] [1,30,31, 100, 100]

# [1, ,1, 1] [30,31, 100, 100]
#...
##[[1, 1] [1,30,31, 100] [100]


# [1, 1, 1, 30, 31] [100, 100]
# [1, 1, 1] [30, 31] [0]
# [1] [1] [0]
# [0]

## f[0, n] = for i from 0 to n:  abs(f[0, i] - f[i+1, n]): minimal value for all possible i
## f[k,k] = w[k]