Codeforces Round #119 (Div. 2) A. Cut Ribbon

on March 29, 2019 in caching, codeforces, dp, dynamic programming, recursion with No comments

Problem Link
Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfills the following two conditions:

After the cutting, each ribbon piece should have length a, b or c.
After cutting the number of ribbon pieces should be maximum.

Help Polycarpus and find the number of ribbon pieces after the required cutting.
Input
The first line contains four space-separated integers n, a, b and c (1 ≤ n, a, b, c ≤ 4000) — the length of the original ribbon and the acceptable lengths of the ribbon pieces after the cutting, correspondingly. The numbers a, b and c can coincide.
Output
Print a single number — the maximum possible number of ribbon pieces. It is guaranteed that at least one correct ribbon cutting exists.
Examples
input

5 5 3 2

output

input

7 5 5 2

output

Note
In the first example, Polycarpus can cut the ribbon in such a way: the first piece has length 2, the second piece has length 3.
In the second example, Polycarpus can cut the ribbon in such a way: the first piece has length 5, the second piece has length 2.
Approach:
We are given a certain ribbon of length n and we are asked to cut the ribbon such that we have maximum pieces where each piece can be of length a, b, or c
Let f (n) be the function that gives the maximum number of pieces that a ribbon of length n be cut. Then,

  f(n)  =  1  + max(f(n - a),
                    f(n - b),
                    f(n - c))

The base case is when n becomes 0 which means that it is not possible to cut the ribbon into further pieces
so, f(0) = 0
After, cutting the ribbon of length n we get a similar problem with reduced length(optimal substructure) and many repeating subproblems(try drawing recursion tree for the first test case). This is the characteristics of DP problems. So we can apply DP.
As top-down approach looks more natural let’s first implement this solution.
I’m going to use Python for this problem. The only problem with python is it has a recursion limit. So I’ve to explicitly set recursion limit to some maximum value.

import sys
sys.setrecursionlimit(500000000)

Let’s dive into our code

#Author: Bishal Sarang
import sys
sys.setrecursionlimit(500000000)

def f(n):
    """
    returns maximum number of pieces that can be cut for ribbon with length n
    """
    
    # If maximum num of pieces for length n is already computed simply return it
    if n in memo.keys():
        return memo[n]
   
    ans = float("-inf")
    if n == 0:
        return 0
    for length in l:
        # Cut into pieces if only we wont have negative length of ribbon
        if n >= length:
            ans = max(ans, 1 + f(n - length))
    #Cache the result
    memo[n] = ans
    return ans
    
#Dict to store computed values
memo = dict()

# Read Input
l = list(map(int, input().split()))
n, l = l[0], l[1:]
print(f(n))

As we have seen the issue with some languages like Python, there is some recursion limit, bottom-up dp seems more convenient.
The solution for bottom of dp is just translating the above approach by building the solution for length 1, length 2, length 3 ....upto length n.
Let dp[n] gives the maximum number of pieces possible for length n such that dp[i] gives the maximum number of pieces possible for length i where 1 <= i <= n.
Initialize an array of length (n + 1) with negative infinity denoting initially all length are not possible.
Base case:

dp[0] = 0

Iteratively build the solution by calculating

dp[i] = max(dp[i],
            1 + dp[i - a],
            1 + dp[i - b],
            1 + dp[i - c])

We can write dp[i] in a more readable format using loop.

for length in l:
    # Cut into pieces if only we dont have negative length of ribbon
    if i - length >= 0:
        dp[i] = max(dp[i], 1 + dp[i - length])

Let’s see the complete bottom-up implementation.

#Author: Bishal Sarang

def f(n):
    # Build maximum number of pieces for
    #length 1 upto n in bottom up manner
    dp = [float("-inf")] * (n + 1)

    # Base Case
    dp[0] = 0

    # dp[i] gives maximum number of pieces that can
    # be obtained by cutting ribbon of length  i into pieces
    # of length a, b or c
    # dp[i] = -inf if it is not possible to cut the ribbon into pieces
    for i in range(1, n + 1):
        for length in l:
            # Cut into pieces if only we dont have negative length of ribbon
            if i - length >= 0:
                dp[i] = max(dp[i], 1 + dp[i - length])
    # return maximum number of pieces possible for ribbon with length n
    return dp[n]

l = list(map(int, input().split()))
n, l = l[0], l[1:]
print(f(n))

Codeforces Round #345 (Div. 2) A. Joysticks

on March 28, 2019 in caching, codeforces, dp, dynamic programming, recursion with No comments

Friends are going to play console. They have two joysticks and only one charger for them. Initially first joystick is charged at a1 percent and second one is charged at a2 percent. You can connect charger to a joystick only at the beginning of each minute. In one minute joystick either discharges by 2 percent (if not connected to a charger) or charges by 1 percent (if connected to a charger).

Game continues while both joysticks have a positive charge. Hence, if at the beginning of minute some joystick is charged by 1 percent, it has to be connected to a charger, otherwise the game stops. If some joystick completely discharges (its charge turns to 0), the game also stops.

Determine the maximum number of minutes that game can last. It is prohibited to pause the game, i. e. at each moment both joysticks should be enabled. It is allowed for joystick to be charged by more than 100 percent.

Input

The first line of the input contains two positive integers a1 and a2 (1 ≤ a1, a2 ≤ 100), the initial charge level of first and second joystick respectively.

Output

Output the only integer, the maximum number of minutes that the game can last. Game continues until some joystick is discharged.

Examples

input

Copy
3 5

output

Copy
6

input

Copy
4 4

output

Copy
5

Note

In the first sample game lasts for 6 minute by using the following algorithm:

at the beginning of the first minute connect first joystick to the charger, by the end of this minute first joystick is at 4%, second is at 3%;
continue the game without changing charger, by the end of the second minute the first joystick is at 5%, second is at 1%;
at the beginning of the third minute connect second joystick to the charger, after this minute the first joystick is at 3%, the second one is at 2%;
continue the game without changing charger, by the end of the fourth minute first joystick is at 1%, second one is at 3%;
at the beginning of the fifth minute connect first joystick to the charger, after this minute the first joystick is at 2%, the second one is at 1%;
at the beginning of the sixth minute connect second joystick to the charger, after this minute the first joystick is at 0%, the second one is at 2%.

After that the first joystick is completely discharged and the game is stopped.

Solution:

This problem can be solved recursively with caching.

Let's say we are given initial charges of joystick as a and b.

Let f(a, b) gives the maximum amount of time. Then at any instance we have two options:

Charge first joystick i.e a becomes a + 1 and b becomes b - 2. So charge_first = 1 + f(a + 1, b - 2)
Charge second joystick i.e a becomes a - 2 and b becomes b + 1. So charge_second= 1 + f(a - 2, b + 1)

Then:

f(a, b) = max(charge_first, charge_second)
Also, we have to consider two base cases:

Charge of either a or b becomes less than or equal to 0.
Charge of both the joystick is 1

For both the cases there is no way the game can be played. So we return 0

Instead of simply using recursion we use caching to save the states instead of re-calculating it. Particularly we use tuple (a, b) as keys in dictionary

Implementation:

At Coder Educational DP Contest Frog 2

on March 26, 2019 in dp, dynamic programming with No comments

Problem Link:

https://atcoder.jp/contests/dp/tasks/dp_b

Problem Statement

There are N stones, numbered 1,2,…,N. For each i (1≤i≤N) the height of Stone i is h
There is a frog who is initially on Stone 1. He will repeat the following action some number of times to reach Stone N:
If the frog is currently on Stone i jump to one of the following: Stone i+1,i+2,…,i+K. Here, a cost of |hi−hj| is incurred, where j is the stone to land on.
Find the minimum possible total cost incurred before the frog reaches Stone N.

Constraints

All values in input are integers.
2≤N≤105
1≤K≤100
1≤hi≤104

Input

Input is given from Standard Input in the following format:
N K
h1 h2 … hN

Output

Print the minimum possible total cost incurred.
5 3
10 30 40 50 20

Sample Output 1
30
If we follow the path 11 → 22 → 55, the total cost incurred would be |10−30|+|30−20|=30.

Solution:

This problem is similar to Frog A . The only difference is that if the frog is at ith stone, it can jump upto k stones from the current stone.
Let’s say the frog is currently at i = 0 stones and k = 3, in one hop it can jump to one of the {1, 2, 3} stone.
The task is to find the minimum cost to reach (n - 1)th stone (0 based indexing as I find it easier)
Make an array dp[n] and initialize with infinite distance.Here, dp[i] gives the cost to reach ith stone. So,

dp[0] = 0;
dp[1] = abs(h[1] - h[0])

For every other stones 2 <= i < n, the frog can jump from from the stone before it, as long as the distance is less than or equal to k.

for(int j = i - 1, jump = 0; j >= 0 && jump < k; j--, jump++){
     dp[i] = min(dp[i], dp[j] + abs(h[j] - h[i]));
}

Implementation:

#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
    int n, k; cin >> n >> k;
    vector<int> h(n);
    for(int i = 0; i < n; i++){
        cin >> h[i];
    }
    
    //dp[i] denotes the minimum cost to reach ith stone
    // 0 < i < n - 1 are the stones
    //We are asked to dind the cost to reach last stone i.e dp[n - 1]
    //Initially there is infinite cost to reach ith stones
    vector<int> dp(n, INT_MAX);
  
    //To reach first stone there is no cost. SO dp[0] = 0
    dp[0] = 0;
   //To reach second stone the frog can jump from 0th stone costing dp[1] = abs(h[1] - h[0])
    dp[1] = abs(h[1] - h[0]);
    
    //For every other stones 2 <= i < n, the frog can jump from the (i - 1), (i - 2)...(i - k)th stones 
    for(int i = 2; i < n; i++){
      for(int j = i - 1, jump = 0; j  >= 0 && jump < k; j--, jump++){
        dp[i] = min(dp[i], dp[j] + abs(h[j] - h[i]));
      }
    }
    //Print minm cost to reach (n - 1)th stone
    cout << dp[n - 1];
    return 0;
}

AtCoder Educational DP Contest Frog 1

on March 25, 2019 in dp, dynamic programming with No comments

Problem Link:
https://atcoder.jp/contests/dp/tasks/dp_a

Problem Statement

There are $N$ stones, numbered $1, 2, \dots, N$ . For each $i$ ( $1 \leq i \leq N$ ), the height of Stone $i$ is $h_{i}$ .

There is a frog who is initially on Stone $1$ . He will repeat the following action some number of times to reach Stone $N$ :

If the frog is currently on Stone $i$ , jump to Stone $i + 1$ or Stone $i + 2$ . Here, a cost of $| h_{i} - h_{j} |$ is incurred, where $j$ is the stone to land on.

Find the minimum possible total cost incurred before the frog reaches Stone $N$ .

Constraints

All values in input are integers.
$2 \leq N \leq 10^{5}$
$1 \leq h_{i} \leq 10^{4}$

Input

Input is given from Standard Input in the following format:

 $N$ 
 $h_{1}$   $h_{2}$   $\dots$   $h_{N}$

Output

Print the minimum possible total cost incurred.

Sample Input 1 Copy

Copy

4
10 30 40 20

Sample Output 1 Copy

Copy

If we follow the path $1$ → $2$ → $4$ , the total cost incurred would be $| 10 - 30 | + | 30 - 20 | = 30$ .

Sample Input 2 Copy

Copy

2
10 10

Sample Output 2 Copy

Copy

If we follow the path $1$ → $2$ , the total cost incurred would be $| 10 - 10 | = 0$ .

Sample Input 3 Copy

Copy

6
30 10 60 10 60 50

Sample Output 3 Copy

Copy

If we follow the path $1$ → $3$ → $5$ → $6$ , the total cost incurred would be $| 30 - 60 | + | 60 - 60 | + | 60 - 50 | = 40$ .

Solution:

This problem can be solved using dynamic programming.

Let dp[i] be the minimum total cost to reach i^th stone.
Then :

dp[i] = min(dp[i - 2] + abs(h[i] - h[i - 2] ,

dp[i - 1] + abs(h[i] - h[i - 1]]);

For 0th and 1st stones:

dp[0] = 0;

dp[1] = abs(h[1] - h[0])