broken-amit

It has been truly said that love is not meant for everyone.

Let me introduce you to a very sad story of my friend Broken Amit. Yes several times he has been left heartbroken. Looking at his poor condition even God is pity on him. God has given Amit a very nice opportunity to Kiss as many girls as he likes . 

There are N number of girls each having a "Love value" as well as a decrement value. 
So, Amit needs to kiss all the N girls exactly once in some order.
 In one step, he can kiss only a single girl and after every step girl's "Love value" decreases by an amount equal to her decrement value times her index (indexing starts from 0) .  But once a girl has been kissed her "Love value" won't decrease in further steps. 

"Love value" for Amit in a particular step is equal to the sum of "Love values" of all the n girls before the beginning of that step, whereas the "Gross Love Value" of Broken Amit is sum of  "Love Values" for Amit in each step. 

Now Amit not being a good analyzer wants your help to find the maximum "Gross Love Value" he can earn.
Input

First line contains an integer N - denoting the number of girls.

Second line contains N integers denoting the initial "Love value" of the girls (L[i]).

Third line contains N integers denoting the "decrement value of the girls (D[i]).
Output

Single integer denoting maximum "Gross Love Value", Broken Amit can earn.
Constraints

1 ≤ n ≤ 17

0 ≤ L[i] < 500000

0 ≤ D[i] < 500000

SAMPLE INPUT
2
2 4
1 2

SAMPLE OUTPUT
12

Explanation

If Amit kisses the first girl and then the 2nd one -
1st step - 2 + 4 = 6
2nd step - 2 + (4 - 12) = 4
Gross Love Value - 6+4 = 10
If Amit kisses the 2nd girl than the 1st one. 
1st step - 2 + 4 = 6
2nd step - (2 - 01) + 4 = 6
Gross Love Value = 12

Source: hackerearth | Difficulty: MEDIUM
Tags: Dynamic programming

Bit manipulation


Solutions:
def sumlval(lst,n):
	res=0
	for i in range(n):
		res+=lst[i][0]
	return res
	
def update(lst,k,n):
	for i in range(k,n):
		lst[i][0]-=(lst[i][1]*lst[i][2])
		
		
n = int(input())
lval = list(map(int,input().split()))
dval = list(map(int,input().split()))
lst=[]
for i in range(n):
	lst.append([lval[i],dval[i],i])
kfunc = lambda x: -(x[1]*x[2])
lst.sort(key=kfunc)
ans=0
for i in range(n):
	ans+=sumlval(lst,n)
	update(lst,i+1,n)
print(ans)


import itertools
import copy

def func(i):
	return i 

def doit(girls):
	i = sorted(list(girls.keys()), key = lambda x: x*girls[x][1], reverse = True)
	nogirls = len(list(girls.keys()))
	gross = 0
	for j in i:
		tot = sum([girls[k][0] for k in range(nogirls)])
		girls[j][1] = 0
		for k in range(nogirls):
			girls[k][0] -= k*girls[k][1]
		gross += tot
	return gross

girls = {}
nouse = eval(input())
lvalues = list(map(int, input().split()))
dvalues = list(map(int, input().split()))
for i in range(nouse):
	girls[i] = [lvalues[i], dvalues[i]]
print(doit(girls))


# coding=utf-8
"""
	@author: Hai
"""

import fileinput
import sys
n=0
L=[]
D=[]
def build(cache, step, mask):
	print('*'*20)
	print("mask =",  "{0:b}".format(mask), "step= ", step)
	#print bin(mask)
	if cache[mask] != 0:
		print('temp= ', cache[mask])
		return cache[mask]
		
	temp=-sys.maxsize - 1
	for i in range(0,n):
		print("i= ", i)
		if not mask & (1<<i):
			value= n * L[i] + i * D[i] * step * ( step + 1 ) / 2 - n * i * D[i] * step
			print('value= ', value)
			temp = max(temp, value + build(cache, step+1, mask | (1<<i)))
	cache[mask]=temp
	print('temp= ', temp)
	return temp


def solve(cache, mask, i):
	if i < 0:
		return 0
	if cache[mask] != -sys.maxsize - 1:
		#print "return from cache", bin(mask), i
		return cache[mask]
	temp=-sys.maxsize - 1
	for step in range(0, n):
		if not mask & (1<<step):  # chua xaistep
			value= n * L[i] + i * D[i] * step * ( step + 1 ) / 2 - n * i * D[i] * step
			'''
			if i==2:
				print "i= ", i, bin(mask), step, value
			if i==1:
				print "i= ", i, bin(mask), step, value
			if i==0:
				print "i= ", i, bin(mask), step, value  
			'''                                                                           
			temp = max(temp, value + solve(cache, mask | (1<<step),i-1))
			'''
			if i==2:
				print 'i= ',i , step, temp
			'''
	cache[mask]=temp
	return temp
			
	
def solve1(cache, mask, i): # mask of step
	if i == 0 :
		return n * L[i]
	for step in range(0,n):
		
		if not mask & (1<<step):
			pass

	 


if __name__=='__main__':
	# prepare data
	
	for index, line in enumerate(fileinput.input()):
		data=line.strip();
		if index==0:
			n= int(data)
		elif index==1:
			L= list(map(int,data.split(" ")))
		elif index==2:
			D= list(map(int,data.split(" ")))
	
	
	#n=4 #n=4 
	cache={}
	for i in range(0,2**n):
		cache[i]=-sys.maxsize - 1
		'''
		for j in range(0,n):
			cache[i][j]=0
		'''
			
	#L=[0,0,3,4] #[5,6,7]
	#D=[0,0,3,3] #[2,3,4]
	#L=[5,6,7]
	#D=[2,3,4]
	#print cache
	mask= 0
	print(solve(cache, mask, n-1))
	'''
	for key, value in cache.iteritems():
		print bin(key), ":",  value
	'''