You are not logged in. Please login at www.codechef.com to post your questions!

×

DBOY - Editorial

16
6

PROBLEM LINKS

Practice
Contest

DIFFICULTY

SIMPLE

PREREQUISITES

Dynamic Programming

PROBLEM

There are N fuel stations numbered 1 through N. The i-th fuel station can fill exactly Ki liters at any time. You have N days. On the i-th day, you must have exactly 2 × Hi liters in your fuel tank. After that, you will have a round trip and the tank will become empty again. Determine the minimum number of times you must fill your fuel tank on the whole N days.

QUICK EXPLANATION

Use dynamic programming approach. Let dp[i][j] = the minimum number of times to fill exactly j liters using only fuel stations 1 through i. The answer to the problem is dp[N][2 × H1] + dp[N][2 × H2] + ... dp[N][2 × HN].

EXPLANATION

This is problem can be reduced to the traditional coin change problem. We have N types of coin, each having value K1, K2, ..., and KN. We want to make changes for N days, each for 2 × H1, 2 × H2, ..., and 2 × HN. What is the minimum number of coins needed?

Note that since each day is independent, we can minimize the number of coins on each day, and sum the results over N days.

Mathematically, for each day i, we want to minimize the value of

X1 + X2 + ... + XN

subject to

X1K1 + X2K2 + ... + XNKN = 2 × Hi
Xk ≥ 0 for 1 ≤ k ≤ N

We will use dynamic programming to solve this problem. Let dp[i][j] = the minimum number of coins needed to make changes for j, using only coins of types 1 through i. The base case is:

  • dp[0][0] = 0 (no coins needed)
  • dp[0][j] = infinity; for j ≠ 0 (it is impossible to make changes for j with no coins)

We can use a very large number such as 1,000,000,000 as infinity in our code.

We need to setup a recurrence relation. For each state dp[i][j], there are two possibilities:

  • We do not use any coin of type i. The minimum number of coins needed is then dp[i - 1][j].
  • We use at least one coin of type i. The minimum number of coins needed is then 1 + dp[i][j - Ki].

Therefore, we have

dp[i][j] = min(dp[i - 1][j], 1 + dp[i][j - Ki])

Both time and space complexity of this solution are in O(N × max{Hi}).

Here is a pseudocode of this solution.

read(N)
for i = 1; i ≤ N; i++:
    read(H[i])
for i = 1; i ≤ N; i++:
    read(K[i])

dp[0][0] = 0
for j = 1; j ≤ max{2 × H[i]}; j++:
    dp[0][j] = 1000000000

for i = 1; i ≤ N; i++:
    for j = 0; j ≤ max{2 × H[i]}; j++:
        dp[i][j] = dp[i-1][j]
        if K[i] ≤ j:
            dp[i][j] = min(dp[i][j], 1 + dp[i][j-K[i])

int res = 0
for i = 1; i ≤ N; i++:
    res = res + dp[N][2*H[i]]
println(res)

There is a solution that only uses O(max{Hi}) memory for the dp table. This solution uses the facts that:

  • dp[i][?] only refers dp[i-1][?]. So instead of keeping N rows in the DP table, we can store only the last two rows.
  • Furthermore, dp[i][x] only refers dp[i][y] for y < x. So we can store only the current row and fill the current row of the DP table from right to left.

read(N)
for i = 1; i ≤ N; i++:
    read(H[i])
for i = 1; i ≤ N; i++:
    read(K[i])

dp[0] = 0
for j = 1; j ≤ max{2 × H[i]}; j++:
    dp[j] = 1000000000

for i = 1; i ≤ N; i++:
    for j = K[i]; j < max{2 × H[i]}; j++:
        dp[j] = min(dp[j], 1 + dp[j-K[i])

int res = 0
for i = 1; i ≤ N; i++:
    res = res + dp[2*H[i]]
println(res)

Note that for the i-th row we fill the table from K[i] instead from 0. This is because for j < K[i] the DP values will not change.

Another solution is to use the so-called "forward DP", i.e. filling the latter entries of the DP table using the values of the current entry. This is just a matter of style.

read(N)
for i = 1; i ≤ N; i++:
    read(H[i])
for i = 1; i ≤ N; i++:
    read(K[i])

dp[0] = 0
for j = 1; j ≤ max{2 × H[i]}; j++:
    dp[j] = 1000000000

for i = 1; i ≤ N; i++:
    for j = 0; j+K[i] < max{2 × H[i]}; j++:
        dp[j+K[i]] = min(dp[j+K[i]], 1 + dp[j])

int res = 0
for i = 1; i ≤ N; i++:
    res = res + dp[2*H[i]]
println(res)

In all solutions above, we do not remove duplicate coin types as they do not affect the answer, although they will make us recompute the same coin types in the DP table.

SETTER'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 11 Dec '12, 18:13

fushar's gravatar image

3★fushar ♦♦
16345853
accept rate: 0%

edited 25 Dec '12, 14:38

admin's gravatar image

0★admin ♦♦
17.4k347486515


The O(max{H}) space approach is actually min-coin change problem.

link

answered 11 Dec '12, 19:09

sid_gup's gravatar image

4★sid_gup
8614715
accept rate: 14%

Can someone please tell me the recurrence tree of this problem.Thanks in advance.

link

answered 28 Jun '14, 18:14

ankitbisla21's gravatar image

4★ankitbisla21
312
accept rate: 0%

Hello coders,

I tried similar approach, but my code got TLE.

Any idea what's wrong?

link

answered 12 Dec '12, 03:19

betlista's gravatar image

3★betlista ♦♦
16.8k49115225
accept rate: 11%

I think in your code, there is an extra factor in the complexity. This is due to the fact that a coin can be used more than once. So, your worst case complexity is- O(N × max{Hi} × max{Hi}).

(15 Dec '12, 09:26) sameer474★

Hi

I have tried a similar approach but I am getting WA. Please help me find out the error. Code is here

link

answered 12 Dec '12, 10:21

kapilagarwal's gravatar image

2★kapilagarwal
2
accept rate: 0%

I had figured out that it is identical to coin change problem. I had used the below approach.

  1. First find max{H} = H_max;
  2. Allocate an integer array dp, of size (H_max*2+1)
  3. Initialize dp[i] = i for all i;
  4. Apply DP using recursive relation
    for(int i=1; i<=size{H}; i++) {
        for(int j=1; j<=size{K}; j++) {
            if(K[j] == i) {
                opt[i] = 1;
                break;
            } else if(K[j] < i) {
                if((opt[i - K[j]] + 1) < opt[i]) {
                    opt[i] = (opt[i - K[j]] + 1);
                }
            }
        }
    }

The space complexity is O(H_max*2) and time complexity is O(size{K} * size{H})
I was getting WA. It is pretty much on the same line as "forward DP" mentioned above. Tried with many variant of this, but couldn't get it through. Surely would have missed some corner case. Would be great if anybody can point out the mistake in the logic

link

answered 12 Dec '12, 20:52

prakash1529's gravatar image

3★prakash1529
16625
accept rate: 0%

edited 12 Dec '12, 22:58

betlista's gravatar image

3★betlista ♦♦
16.8k49115225

1

Hmmm.. Surprisingly, just interchanging for loops as given in the solution section is getting AC. How does it makes a difference whether we iterate over {K}-> {H} or {H}-> {K}. Interesting and frustrating!!!

(12 Dec '12, 23:04) prakash15293★

@prakash1529 Maybe taking into account cache misses in the target system , your observation makes sense :)

(04 Nov '14, 15:21) deepak_sirone3★

I tried solving this using recursion and wonder if anyone can spot what I am doing wrong in my code?

Code is here

link

answered 14 Apr '13, 13:16

haiderekarrar's gravatar image

1★haiderekarrar
1
accept rate: 0%

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;

int main() {
    int t;
    scanf("%d",&t);
    int H[501],K[501];


    int N,max;
    while(t--)
    {
        int dp[501][1001];
        max=0;
        scanf("%d",&N);
        for(int i=1;i<=N;i++)
        {
        scanf("%d",&H[i]);
        if(max<h[i]) max="H[i];" }="" for(int="" i="1;i&lt;=N;i++)" scanf("%d",&k[i]);="" dp[0][0]="0;" for(int="" j="1;j&lt;=max*2;j++)" dp[0][j]="1000000000;" for(int="" i="1;i&lt;=N;i++)" {="" for(int="" j="0;j&lt;=2*max;j++)" {="" dp[i][j]="dp[i-1][j];" if(k[i]<="j)" dp[i][j]="min(dp[i][j],1+dp[i][j-K[i]]);" }="" }="" int="" sum="0;" for(int="" i="1;i&lt;=N;i++){" sum="sum+dp[N][2*H[i]];" }="" printf("%d",sum);="" }="" your="" code="" goes="" here="" return="" 0;="" }="" <code="">
why my answer is giving WA pls help
link

answered 26 Jul '14, 18:13

neweffort's gravatar image

2★neweffort
1111
accept rate: 0%

The approach I have taken is like this.
Let M[1...1001] be an array , where M[i] denotes the minimum number of refills needed to cover a distance i.

From this we get the recurrence M[i] = min(k = 0 to (i/2)){ M[k] + M[i - k] }

Using a bottom up approach, we can build a solution.
Initially M[i] = inf for all i
IF i is an element of K[i], M[i] = 1
After this we can do the bottom up approach as follows:
for(i = 1 ; i <= 1000 ; i++) { for(j = 0 ; j <= (i / 2) ; j++) { if(M[i] > (M[j] + M[i - j])) M[i] = M[j] + M[i - j]; } }

Finally summing just the distances we need: sum = 0; for(i = 0 ; i < n ; i++) sum += M[2 * h[i]]; printf("%d\n" , sum); Hope this helps :)
Link to my solution:http://www.codechef.com/viewsolution/5265891

link

answered 04 Nov '14, 15:12

deepak_sirone's gravatar image

3★deepak_sirone
52448
accept rate: 0%

I know its a very old question but I was trying it as a practice and noticed a strange thing: Going by the for loops as in the solution setting give AC. But interchanging the order of for loops gives wrong answer. Any one who can throw some more light? @betista's solution and @prakash1529's comment also highlights the same phenomenon. Any pointers to this mistery?

link

answered 22 Dec '14, 00:02

lonecodertaken's gravatar image

2★lonecodertaken
10126
accept rate: 0%

can anyone tell me what's wrong with my code? here's my code https://www.codechef.com/viewsolution/7606972

link

answered 02 Aug '15, 11:14

nikhilp13's gravatar image

1★nikhilp13
212
accept rate: 0%

why my answer is TLE where i use O(n*n) solution here is my solution

link

answered 17 Nov, 17:26

akshaycs's gravatar image

3★akshaycs
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,235
×1,320
×801
×21
×7

question asked: 11 Dec '12, 18:13

question was seen: 8,168 times

last updated: 17 Nov, 17:26