SUPW(ZCO'14)

general
1

http://www.iarcs.org.in/inoi/2014/zco2014/zco2014-1b.php

How to create a dynamic programming solution to this zco problem?
After much efforts i was luckily able to solve the ipl problem but have got stuck on this problem. This looks similar to the ipl problem.
Any help will be highly encouraged.

2

The answer:

Work[0..N] time for each workload 
Best[j,0] means he does not work on day j
Best[j,1] means he does work on day j,not j+1
Best[j,2] means he does work on day j,j+1,not j+2

Initialize :
Best[N,0] = sum(Work[i],for all i from 0 to N-1)
Best[N,1] = sum(Work[i],for all i from 0 to N-1)-Work[N-1]
Best[N,2] = sum(Work[i],for all i from 0 to N-1)
Work[0]=0

Now:
For j=N-1 to 0  j--
Best[j,0] = min(Best[j+1,0],Best[j+1,1],Best[j+1,2])
Best[j,1] = Work[j] - Best[j+1,0]
Best[j,2] = Work[j] - Best[j+1,1]

Make a table on a paper and you’ll get it.

3

man simple speaking was unable to understand anything there… it was all messed up.
Could u tell me the logic! I’ll try to create the dp solution my self :smiley:

4

Well why would you use DP???

Isn’t the greedy method good here???

5

Nope. That gives the wrong answer majority of the times.

1 Like
6

Yeah It did now :frowning:

7

Can anyone tell me the recursive solution

8

If you solved IPL problem then just subtract your answer from total sum of array and you will get answer of SUPW problem. Check it out!!