In a city, located on a straight line, there are $n$ houses and $m$ cell towers. You know the locations

of all houses $(h_1,$dots,$h_n)$ and all towers $(t_1,$dots,$t_m).$ You would like to purchase some towers so that

every house is within a range of some tower; each tower $j$ has purchasing cost $c_j$ and the coverage

radius $r_j.$

Thankfully, you also have $k$ coupons; when you buy a tower, of you use a coupon, the cost of the

tower is halved $($and the coupon disappears$)!$ For each tower, you can apply a coupon only once.

Your goal is to purchase the towers so that:

Each house is covered by some tower $($formally$,$ for each i there exists $j$ such that $|h_i-t_j|d_i).$

A house can be covered by more than one tower.

The total cost of purchased towers is minimized.

Note If you solve the problem only for $k=0,$ you'll get $70\%$ of the grade.

Please do the following:

Formulate the subproblem. Please state it as precisely as possible.

Design a dynamic programming algorithm for solving this problem:

State the base case.

State the recurrence relation.

Explain why the recurrence relation is correct.

Please provide the pseudocode. Please use the bottom$-$up approach.

Explain:

What is the running time of your algorithm.

How to recover the minimum total cost.

How to recover the set of the purchased towers $($and which towers are purchased

with coupons$).$ You don't need to write a pseudocode.

Why your algorithm correctly handles the case when an optimal solution doesn't

exist.

Example Let house locations be $h_1=1,h_2=4,h_3=5,$ and the towers be

$1,$ and the number of coupons $k=1.$ The optimal

solution is to purchase towers $2$ and $3,$ and apply a coupon to tower $3.$ This way:

House $1$ is covered by tower $2(|h_1-t_2|=|1-0|1=r_2).$

Houses $2$ and $2$ are covered by tower $3.$

The cost is $c_2+\frac{c_3}{2}=6,$ which is optimal.