## 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.