On Sunday, November 24, 2019, I participated in the ASU SoDA Coding Challenge VI. The ASU Software Developer’s Association (SoDA) is a club that is dedicated to teaching aspiring programmers how to solve complex problems that will prepare them for industry. The club runs recruiting events, Hackathons, Interview Prep sessions, and other activities that I have personally found invaluable during my first semester at ASU. I would strongly recommend anyone with a remote interest in computer science to join the club.
The SoDA Coding Challenge had 15 questions which were divided into three categories of three questions based on their respective difficulty levels. The Easy Questions, the Medium Questions, and the Hard Questions were made available to the contestants through Google Forms, and participants would have proctors manually check their code to make sure their programs worked.
Medium Question #5 involves determining paths along a weighted tree with certain properties. The question reads:
ASU SoDA Coding Challenge VI Medium Question 5: k-tree Quite recently a creative student Lesha had a lecture on trees. After the lecture Lesha was inspired and came up with the tree of his own which he called a k-tree. A k-tree is an infinite rooted tree where: each vertex has exactly k children; each edge has some weight; if we look at the edges that goes from some vertex to its children (exactly k edges), then their weights will equal 1, 2, 3, ..., k. The picture below shows a part of a 3-tree.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
This was easily my favorite question at this event, and based on the discussion after the event, I think a lot of people wanted to know a good solution for this question. Here’s the solution I used during the event:
Solution #1: Horrible Recursive Approach
During the event, I couldn’t think of a nice way to do this problem dynamically, so I used recursion. The recursive step stores the minimum maximum element that needs to be included in each path as well as the remaining sum of the path, and a bunch of conditions are given as the base case where the recursion ends. I don’t really feel like explaining it, so here’s an implementation of this in Python 2.7 that I used on the day of the competition:
'''
Author: Walker Kroubalkian
SoDA Coding Challenge VI Medium Problem #5
https://docs.google.com/document/d/14sk0u9ZVM1rrIsSCSwIWesI1ks8BukFMaT-NlJCr6FQ/edit
'''
import time
import sys
i = 0
for x in sys.stdin:
if i==0:
n = int(x)
elif i==1:
k = int(x)
else:
d = int(x)
i+=1
def nChooseR(n,r):
num = 1
for i in range(r):
num*=(n-i)
num/=(i+1)
return num
myMod = 10**9 + 7
def doProblem(n,k,d):
if(k<d):
return 0
if(n<d):
return 0
if(n==1 and d==1):
return 1
total = 0
if(n<=k):
total+=1
for x in range(1,d):
total+=doProblem(n-x, k, d)
total%=myMod
for x in range(d,k+1):
total+=doProblem(n-x, k, 1)
total%=myMod
return total
start = time.time()
print doProblem(n, k, d)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
7
--- 2.00271606445e-05 seconds ---
for input of n = 4, k = 5, d = 2.
'''
This manages to solve the problem for all of the sample test cases, but for the maximum input size given in the problem, it would take until the end of the universe for the program to execute. Luckily, on the day of the competition, the test cases they used to check our code for this problem were relatively small so this program seemed efficient enough. I feel a bit bad for using such inefficient code in a competition, but luckily I found a much faster solution after the fact. Here’s a more efficient solution:
Solution #2: Dynamic O(n) Approach
We can observe that this is simply the number of ordered partitions of n where the summands are at most k minus the number of ordered partitions of n where the summands are at most m-1. A well known algorithm can be used to find each of these values recursively in O(n) time complexity. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
SoDA Coding Challenge VI Medium Problem #5
https://docs.google.com/document/d/14sk0u9ZVM1rrIsSCSwIWesI1ks8BukFMaT-NlJCr6FQ/edit
'''
import time
import sys
i = 0
for x in sys.stdin:
if i==0:
n = int(x)
elif i==1:
k = int(x)
else:
d = int(x)
i+=1
myMod = 10**9 + 7
def nChooseR(n,r):
num = 1
for i in range(r):
num*=(n-i)
num/=(i+1)
return num
def countOrderedPartitions(n,m):
if(m<=0):
return 0
if(m>n):
m = n
values = []
for _ in range(m-1):
values.append(0)
values.append(1)
total = 1
l = m
for _ in range(n):
values.append(total)
total+=total
total-=values[l-m]
l+=1
return values[l-1]
def doProblem(n,k,d):
if(n<d or k<d):
return 0
return (countOrderedPartitions(n, k) - countOrderedPartitions(n, d-1))%myMod
start = time.time()
print doProblem(n, k, d)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
881051483
--- 8.41617584229e-05 seconds ---
for input of n = 100, k = 5, d = 2.
'''
I’m really kicking myself for not finding this approach on the day of the competition as many of the Project Euler problems I have solved have used this exact approach. Regardless, this was by far the most interesting problem I solved on the day of the competition.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 