Day: June 5, 2019

AtCoder Educational DP Contest : B Frog – 2

~ Suraj Shaw ~ Leave a comment

Problem Statement – https://atcoder.jp/contests/dp/tasks/dp_b

This problem is similar to Frog – 1, but this time from ‘i’ we could jump to i+1, i+2, … i+K , few changes in the previous code is needed.

Implementation

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define INF 1e9
#define FOR(i,s,e) for(int i=s; i<=e; i++)
int cost[MAXN], memo[MAXN];
int n, k;
class fastio {
public:
    fastio() {
        ios_base::sync_with_stdio(false);
        cout.tie(nullptr);
        cin.tie(nullptr);
    }
} __fastio;
int f(int i) {
    if(i > n) return INF;
    if(i == n) return 0;
    if(memo[i] != -1) return memo[i];
    else {
        int ans = INF;
        FOR(j,1,k) {
            ans = min(ans, f(i+j) + abs(cost[i] - cost[i+j]));
        }
        return memo[i] = ans;
    }
}
void solve() {
    cin >> n >> k;
    FOR(i,1,n) {
        cin >> cost[i];
    }
    memset(memo, -1, sizeof(memo));
    cout << f(1) << endl;
}
int main() {
  __fastio;
  solve();
  return 0;
}

AtCoder Educational DP Contest : A Frog – 1

~ Suraj Shaw ~ Leave a comment

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

At every instance we have two choices, i.e either jump to ‘i+1’ th or ‘i+2’ th rock, and the cost of jumping for the former is |cost[i] – cost[i+1]| and for the latter it’s |cost[i] – cost[i+2]| and minimum of them is the answer, therefore the recurrence relation would be.

min{f(i+1) + |cost[i] – cost[i+1]| , f(i+2) + |cost[i] – cost[i+2]|}

Here, |x| denotes absolute value of ‘x’

The implementation is rather straight forward.

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define INF 1e9
#define FOR(i,s,e) for(int i=s; i<=e; i++)
int cost[MAXN], memo[MAXN];
int n;
class fastio {
public:
    fastio() {
        ios_base::sync_with_stdio(false);
        cout.tie(nullptr);
        cin.tie(nullptr);
    }
} __fastio;
int f(int i) {
    if(i > n) return INF;
    if(i == n) return 0;
    if(memo[i] != -1) return memo[i];
    return memo[i] = min(f(i+1) + abs(cost[i] - cost[i+1]), f(i+2) + abs(cost[i] - cost[i+2]));
}
void solve() {
    cin >> n;
    FOR(i,1,n) {
        cin >> cost[i];
    }
    memset(memo, -1, sizeof(memo));
    cout << f(1) << endl;
}
int main() {
  __fastio;
  solve();
  return 0;
}