Description
1. Earthquake Recovery (10 points)
https://www.hackerrank.com/contests/cst370-s19-hw6/challenges/hw6-earthquake
An Earthquake has knocked out a lot of roads in a county so citizens are cut off from essential
resources. The county’s repair crews are working overtime to get everyone reconnected to
the road network. You are given the towns and roads in the county, as well as the amount
of time it will take to repair damaged roads. You wil find the minimum amount of time it
will take to get everyone reconnected?
Input
• The first line will contain an integer n, the number of towns that are stranded.
• The next n lines will contain those towns.
• The next line will contain an integer r, the number of roads in need of repair.
• The next r lines will contain the roads in the format of comma-separated endpoints,
followed by an integer, the amount of time required to repair it.
All towns must be reachable after repairing the roads. Any town that is not unconnected
is a valid reconnection point. This input is very similar to the input for homework 5’s
Essential Services problem. You can reuse your input handling code that problem on this
problem.
Constraints
You can assume all the weights are positive (it takes time to repair a road) and that all
towns have unique names.
Page 3 of 13
CST 370 Homework 6 April 25, 2019
Output
A single line containing an integer, the amount of time it will take to get everyone reconnected.
Sample Input 1 Sample Output 1
6
Pacific Grove
Salinas
Monterey
Seaside
Marina
CSUMB
9
Pacific Grove , Monterey , 80
Pacific Grove , Pebble Beach , 10
Pacific Grove , CSUMB , 20
Monterey , Marina , 15
Monterey , Salinas , 30
Marina , Salinas , 45
Seaside , CSUMB , 25
Seaside , Marina , 15
CSUMB , Marina , 10
100
Page 4 of 13
CST 370 Homework 6 April 25, 2019
2. Coin change (10 points)
You will be given the denominations of coins in a monetary system and a required sum.
Your job is to find the number of ways you can make change for that sum assuming order
of coins does not matter.
Submission
• Use this link to submit a iterative dynamic programming solution to this problem:
https://www.hackerrank.com/contests/cst370-s19-hw6/challenges/hw6-coinchange-iterative
• Use this link to submit a recursive dynamic programming solution to this problem:
https://www.hackerrank.com/contests/cst370-s19-hw6/challenges/hw6-coinchange-recursive
Input
• The first line will contain an integer, n, the required sum.
• The second line will contain an integer, c, the number of coins in the monetary system.
• The third and final line will contain c space-separated integers, the denominations of
those coins.
Constraints
For simplicity, you can assume the required sum and all coin denominations are integers.
Output
The output will consist of a single line containing an integer, the number of ways to make
the required sum.
Sample Input 1 Sample Output 1
25
4
10 5 25 1
13
Sample Input 2 Sample Output 2
100
4
10 5 25 1
242
Page 5 of 13
This page is intentionally left blank.
CST 370 Homework 6 April 25, 2019
3. Leap Frog (10 points)
You will be given an array of integers representing the lily pads. Each integer indicats how
many lily pads forward the frog can jump in a single leap from that lily pad. Find the
minimum number of jumps the frog needs to reach shore (past the lily pads, i.e., the end of
the array).
Submission
• Use this link to submit a iterative dynamic programming solution to this problem:
https://www.hackerrank.com/contests/cst370-s19-hw6/challenges/hw6-leapfrog-iterative
• Use this link to submit a recursive dynamic programming solution to this problem:
https://www.hackerrank.com/contests/cst370-s19-hw6/challenges/hw6-learfrog-recursive
Input
• The first line will contain a single integer n, the number of lily pads.
• The second line contains n space-separated integers, the lily pads in order across the
pond.
Constraints
You can assume the frog starts on lily pad 0 (the first in the array). You can also assume
there are no negative numbers in the array.
Output
A single line consisting of either
• a single integer, the minimum number of jumps.
• −1 if the Frog can’t reach shore and should turn back.
Sample Input 1 Sample Output 1
11
1 3 5 8 9 2 6 7 6 8 9
3
Sample Input 2 Sample Output 2
6
1 0 10 5 11 3
-1
Page 7 of 13
This page is intentionally left blank.
CST 370 Homework 6 April 25, 2019
4. Maximum Sub-Square (10 points)
You will receive a square binary matrix representing unoccupied and occupied space in a
park.
You are trying to install a square garden and would like it to be as large as possible. Find
the dimension of the largest possible garden (i.e., the largest sub-square of just 0s, vacant
space).
Submission
• Use this link to submit a iterative dynamic programming solution to this problem:
https://www.hackerrank.com/contests/cst370-s19-hw6/challenges/hw6-subsquares-iterative
• Use this link to submit a recursive dynamic programming solution to this problem:
https://www.hackerrank.com/contests/cst370-s19-hw6/challenges/hw6-subsquares-recursive
Input
• The first line will contain an integer, n, the dimension of the park.
• The next n lines will contain n space-separated bits (0 or 1), indicating whether that
part of the park is vacant or occupied.
Constraints
You can assume n is positive.
Output
A single line containing an integer, the maximum dimension for the garden.
Sample Input 1 Sample Output 1
4
0 1 0 0
1 0 0 0
0 0 0 0
0 0 1 0
2
Sample Input 2 Sample Output 2
3
0 1 0
1 0 0
0 0 1
1
Page 9 of 13
This page is intentionally left blank.
CST 370 Homework 6 April 25, 2019
5. Climbing Stairs (10 points)
You have to climb a special staircase. It costs money to stand on each step so you want
to minimize the cost incurred by climbing the stairs. You are given an array of integers
representing the cost to stand on the i
th step where i is the index. You may start on either
step 0 or 1 and you can go up 1 or 2 steps each time. You must end on the last step.
Submission
• Use this link to submit a iterative dynamic programming solution to this problem:
https://www.hackerrank.com/contests/cst370-s19-hw6/challenges/hw6-stairs-iterative
• Use this link to submit a recursive dynamic programming solution to this problem:
https://www.hackerrank.com/contests/cst370-s19-hw6/challenges/hw6-stairs-recursive
Input
• The first line will contain an integer n, the number of steps.
• The second and final line will contain n space-separated integers, the cost of stepping
on each step.
Constraints
You can assume the cost of a step is non-negative.
Output
The output will consist of a single integer, n, the cheapest cost you can climb the stairs for.
Sample Input 1 Sample Output 1
5
7 10 15 3 11
24
Sample Input 2 Sample Output 2
12
11 9 2 4 15 19 3 25 18 8 0 1
48
Page 11 of 13
This page is intentionally left blank.
CST 370 Homework 6 April 25, 2019
6. Meeting Scheduling (10 points)
My company is perptually short on meeting rooms. A number of meetings have been scheduled for the same room but unfortunately they overlap in time so not all of them can occur.
Each meeting has a start and end time and a priority (importance). Find the maximum
cumulative priority we can accomplish with non-overlapping meetings.
Submission
• Use this link to submit a iterative dynamic programming solution to this problem:
https://www.hackerrank.com/contests/cst370-s19-hw6/challenges/hw6-meetings-iterative
• Use this link to submit a recursive dynamic programming solution to this problem:
https://www.hackerrank.com/contests/cst370-s19-hw6/challenges/hw6-meetings-recursive
Input
• The first line of the input will be an integer, n, the number of meetings.
• The next n lines will consist of three space separated integers: the start time, the end
time, and the priority, in that order.
Constraints
You can assume all the priorties are positive.
Output
The output will consist of a single line containing an integer, the maximum cumulative
priority we can get scheduled.
Sample Input 1 Sample Output 1
7
8 9 5
11 13 4
10 13 2
11 15 6
15 16 8
13 14 3
8 11 7
22
Page 13 of 13
This page is intentionally left blank.
