Problem #103 concerns sets of integers with ordered sums of all possible subsets. The question reads:
Project Euler Problem 103: Special subset sums: optimum Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true: S(B) ≠ S(C); that is, sums of subsets cannot be equal. If B contains more elements than C then S(B) > S(C). If S(A) is minimised for a given n, we shall call it an optimum special sum set. The first five optimum special sum sets are given below. n = 1: {1} n = 2: {1, 2} n = 3: {2, 3, 4} n = 4: {3, 5, 6, 7} n = 5: {6, 9, 11, 12, 13} It seems that for a given optimum set, A = {a1, a2, ... , an}, the next optimum set is of the form B = {b, a1+b, a2+b, ... ,an+b}, where b is the "middle" element on the previous row. By applying this "rule" we would expect the optimum set for n = 6 to be A = {11, 17, 20, 22, 23, 24}, with S(A) = 117. However, this is not the optimum set, as we have merely applied an algorithm to provide a near optimum set. The optimum set for n = 6 is A = {11, 18, 19, 20, 22, 25}, with S(A) = 115 and corresponding set string: 111819202225. Given that A is an optimum special sum set for n = 7, find its set string. NOTE: This problem is related to Problem 105 and Problem 106.
This is possibly the most troll question in all of Project Euler. My solution technically isn’t a complete solution, but luckily it doesn’t need to be. Here’s my solution:
Solution #1: Engineer’s Induction Approach
Contrary to the problem’s advice, we can apply the “rule” another time on the optimal set for n = 6 to get a potential set for n = 7 of {20,31,38,39,40,42,45}. From here, I checked all 7-tuples with each element within 2 of the element for this potential set to find other sets with lower sums. Because no new sums were found, I concluded that the algorithmic set was the correct optimal set. Here’s an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #103
'''
import time
def testOrder(a):
a = sorted(a)
first = []
total = 0
for x in a:
first.append(total)
total+=x
first.append(total)
back = []
total = 0
for x in a[::-1]:
back.append(total)
total+=x
back.append(total)
l = len(a)
for x in range(1,l):
if first[x+1]<back[x]:
return False
return True
def subset(myList,n):
if n==0:
return [[]]
l = len(myList)
if l<n:
return []
a = myList[0]
b = subset(myList[1:],n)
c = subset(myList[1:], n-1)
for x in c:
x.append(a)
b.append(sorted(x))
return b
def testNoneEqual(a):
l = len(a)
allSums = []
for x in range(1,l+1):
v = subset(a,x)
for y in v:
value = sum(y)
if value in allSums:
return False
allSums.append(value)
return True
def isSpecialSet(myList):
if testOrder(myList):
if testNoneEqual(myList):
return True
return False
def allPossible(myList,length):
if length==0:
return [[]]
v = allPossible(myList, length-1)
total = []
for a in myList:
for x in v:
t = x[:]
t.append(a)
total.append(t)
return total
def projectEulerProblemOneHundredThree():
bestKnown = [20,31,38,39,40,42,45]
l = len(bestKnown)
potential = True
possible = [-2,-1,0,1,2]
addition = allPossible(possible, l)
final = []
for a in addition:
if sum(a)<0:
final.append(a)
while(potential):
potential = False
for a in final:
t = bestKnown[:]
for x in range(l):
t[x]+=a[x]
if isSpecialSet(t):
potential = True
bestKnown = t
break
s = ""
for x in bestKnown:
s+=str(x)
return s
start = time.time()
print projectEulerProblemOneHundredThree()
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
20313839404245
--- 0.617619991302 seconds ---
for input of given problem.
'''
And with that, we’re done. I found it pretty funny that they explained the rule and gave one counterexample when the solution involved simply applying the rule once to the counterexample. This problem would probably be considerably more difficult if they hadn’t explained the rule in the problem statement.
Thanks for reading! See you tomorrow.
As soon as Dima, a good friend of Lesha, found out about the tree, he immediately wondered: "How many paths of total weight n (the sum of all weights of the edges in the path) are there, starting from the root of a k-tree and also containing at least one edge of weight at least d?".
Help Dima find an answer to his question. As the number of ways can be rather large, print it modulo 1000000007 (109 + 7).
Input
Three integers: n, k and d (1 ≤ n, k ≤ 100; 1 ≤ d ≤ k).
Output
Print a single integer — the answer to the problem modulo 1000000007 (10^9 + 7).
Test Cases:
input
3 3 2
output
3
input
3 3 3
output
1
input
4 3 2
output
6
input
4 5 2
output
7
The Inner Machinations of Walker 