Ankur's Blog

let's start Code

Showing posts with label DP. Show all posts
Showing posts with label DP. Show all posts

Sereja and Salesman

, , , No comments

Problem Link: SEAKAM

Topic: Bitmask Dp

Explanation: GKCS

implementation:


Share:
Read More

E. Tetrahedron

No comments

Explanation: tetrahedron, rachitJain


Share:
Read More

CodeMonk (Dynamic Programming Part- I )

, , No comments
Share:
Read More

Find if a string is interleaved of two other strings

No comments
Share:
Read More

Cutting a Rod

, No comments

Cutting a Rod


Tushar Roy Video 

Medium blog post 

Implementation 01:


 

 Aplication:


 

Share:
Read More

Edit Distance

, No comments
Share:
Read More

Word Wrap Problem (text justification)

, No comments
Share:
Read More

Longest Increasing Subsequence (LIS)

, No comments
Share:
Read More

Some Basic DP Problem Solution

No comments
Share:
Read More

Program for Fibonacci numbers

No comments

Code:


Share:
Read More

কয়েন চেঞ্জ + রক ক্লাইম্বিং

No comments
Share:
Read More

C. Codejamon Cipher

No comments
Share:
Read More

0/1 KnapSack

, No comments

Resources:

 GeeksForGeeks

HackerEarth 

Codeforces 

CF blog 

 

Code:


 

Code: (When Knapsack size is large)

 

 

 

ProblemList:

B. Checkout Assistant 

UVA 

A2Online Judge 

 

Share:
Read More

Longest Common Subsequence ( LCS )

, , No comments
Share:
Read More

Binomial Coefficient

, No comments
Share:
Read More

216 - Getting in Line

, No comments

216 - Getting in Line

Topic: Travelling Salesman Problem

Solution 01: Github gist


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define MAX 100005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

typedef long long ll;
vector<pair<int,int> >v;
double graph[20][20], TSP;
 int n;
 vector<int> path;

 void path_print(){
  //cerr<<"Enter---\n";
  //for(int i = 0; i < path.size(); i++)cout << path[i] << " ";
    //cout << endl;
  for(int i = 0; i < path.size()-1; i++){
    int x = path[i];
    int y = path[i+1];
    cout <<"Cable requirement to connect ("<<v[x].first<<","<<v[x].second<<") to ("<<v[y].first<<","<<v[y].second<<") is "<<fixed<<setprecision(2)<<graph[x][y]<<" feet.\n";
    cerr << v[x].first << " "<<v[x].second<<endl;
  }
 }

double tsp(int s, double mn)
{
    vector<int>vertex;
    for(int i = 0; i < n; i++){
        if(i != s)
            vertex.push_back(i);
    }

    double min_path = 99999999.0;
    do{
        double current_pathweight = 0.0;
        int k = s;
        for(int i = 0; i < vertex.size(); i++){
            current_pathweight += graph[k][vertex[i]];
            k = vertex[i];
        }
        //current_pathweight += graph[k][s];

        //min_path = min(min_path, current_pathweight);
        if(min_path > current_pathweight && mn > current_pathweight){
          min_path = current_pathweight;
          path.clear();
          path.push_back(s);
          for(int i = 0; i < vertex.size(); i++)path.push_back(vertex[i]);
        }
    }while(next_permutation(vertex.begin(), vertex.end()));
    return min_path;
}

void print()
{
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      cout << setw(3)<<graph[i][j] << " ";
    }
    cout << endl;
  }
}


int main()
{
    //FASTIO
   /* 
   //double start_time = clock();
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
  #endif
    //*/
    int cnt = 0;
    while(cin >> n && n){
      TSP = 0.0;
      for(int i = 0; i < n;i++){
        int x,y;
        cin >> x >> y;
        v.push_back({x,y});
      }
      for(int i = 0; i < n; i++){
        int x1 = v[i].first;
        int y1 = v[i].second;
        for(int j = i+1; j < n; j++){
          int x2 = v[j].first;
          int y2 = v[j].second;
          double D = sqrt(((x1-x2)*(x1-x2)) + ((y1-y2)*(y1-y2))) + 16.0;
          graph[i][j] = D;
          graph[j][i] = D;
         // cerr << x1 << " "<<y1 << " "<<x2 << " "<<y2<<endl;
        }
        //cerr<<"\n";
      }
      //print();
      double mn = 999999.0;
      for(int i = 0; i < n; i++){
         TSP = tsp(i, mn);
         mn = min(TSP, mn);
      }

      cout << "**********************************************************\n";
      cout << "Network #"<<++cnt<<"\n";
      path_print();
      cout <<"Number of feet of cable required is "<<fixed<<setprecision(2)<< mn<<".\n";
      path.clear();
      v.clear();
    }

        //double end_time = clock();
  //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
   
    return 0;
}

Share:
Read More

Travelling Salesman Problem

, , No comments

Travelling Salesman Problem

CODING BLOCKS

Geeks for Geeks

Using Branch and Bound

visualgo-tsp 

Implementation 01:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
int dp[1<<20][20];
int n = 4;
int dist[10][10] = {
        {0,20,42,25},
        {20,0,30,34},
        {42,30,0,10},
        {25,34,10,0}
};

void takeInput()
{
    cin >> n; // number of village.
    // now we input Cost Matrix.
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
                cin >> dist[i][j];
        }
    }
}

int VISITED_ALL = (1 << n) - 1;
// mask = friends I already visited
// At = last visited friend
int tsp(int mask, int pos)
{
    if(mask == VISITED_ALL) return dist[pos][0];

    if(dp[mask][pos] != -1) return dp[mask][pos];

    //  Now from current node, we will try to go to every other node and take the min ans
      int ans = INT_MAX;

      for(int city = 0; city < n; city++){
        if( (mask & (1 << city ) ) == 0){
            int newAns = dist[pos][city] + tsp(mask | (1 << city), city);
            ans = min(ans, newAns);
        }
      }

      return dp[mask][pos] = ans;
}

int main()
{
     //freopen("in.txt", "r", stdin);
     memset(dp, -1, sizeof(dp));
    /// takeInput();
     cout << "Total minimum Distance---> "<<tsp(1,0);
     return 0;
}

Implementation 02:




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
int n;
int dist[10][10];
int graph[20][20];
void takeInput()
{
    cin >> n; // number of village.
    // now we input Cost Matrix.
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
             cin >> graph[i][j];
        }
    }
}

int tsp(int s)
{
    vector<int>vertex;
    for(int i = 0; i < n; i++){
        if(i != s)
            vertex.push_back(i);
    }

    int min_path = INT_MAX;
    do{
        int current_pathweight = 0;
        int k = s;
        for(int i = 0; i < vertex.size(); i++){
            current_pathweight += graph[k][vertex[i]];
            k = vertex[i];
        }
        current_pathweight += graph[k][s];

        min_path = min(min_path, current_pathweight);
    }while(next_permutation(vertex.begin(), vertex.end()));
    return min_path;
}

int main()
{
    takeInput();
    int s = 0;
    cout << tsp(s)<<endl;
    return 0;
}

Share:
Read More

B - Frog 2

, , No comments

B - Frog 2

Complexity: O(n*k)

Topic: Basic DP


 solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define MAX 100005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

typedef long long ll;

int main()
{
    FASTIO
   /* 
   double start_time = clock();
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif
    */
    int n,k;
    cin >> n >> k;
    vector<int> H(n+10, 0);
    for(int i = 0; i < n; i++) cin >> H[i];

      vector<int> ans(n+5, INF);
    ans[0] = 0;
    for(int i = 0; i < n; i++){
      for(int j = 1; j <= k && (i+j) < n; j++){
      ans[i+j] = min(ans[i+j], ans[i] + abs(H[i+j] - H[i]));
    }
  }
    cout << ans[n-1]<<endl;

     //double end_time = clock();
  //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
   
    return 0;
}
Share:
Read More

A - Frog 1

, , No comments

A - Frog 1

Solution 01: IH19980412

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
#define INF 1<<28
#define MAX 100005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

typedef long long ll;

int n, a[100005];
int dp[MAX];

int main()
{
    FASTIO
   /* 
   double start_time = clock();
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif
    */
    cin>>n;
    for(int i = 1; i <= n; i++)
        cin>>a[i];
    dp[1] = 0;
    for(int i = 2; i <= n; i++){
        dp[i] = dp[i-1] + abs (a[i] - a[i-1]);
        if(i > 2){
            dp[i] = min(dp[i], dp[i-2] + abs(a[i] - a[i-2]));
        }
    }
    cout << dp[n]<<endl;

  //   double end_time = clock();
  //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
   
    return 0;
} 

Solution 02: colun


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
#define INF 1<<28
#define MAX 100005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

typedef long long ll;

int main()
{
    FASTIO
   /* 
   double start_time = clock();
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif
    */
    int n,a,b,c,d;
    cin >> n;
    a = b = 0;
    cin >> c;
    d = c;

    for(int i = 1; i < n; i++)
        {
          int x;
          cin >> x;
          a = min(a+abs(x-c), b + abs(x - d));
          swap(a,b);
          c = d;
          d = x;
        }
        cout << b << "\n";

    // double end_time = clock();
  //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
   
    return 0;
}

Solution 03: 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define MAX 100005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

typedef long long ll;

int main()
{
    FASTIO
   /* 
   double start_time = clock();
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif
    */
    int n;
    cin >> n;
    vector<int> H(n+10, 0);
    for(int i = 0; i < n; i++) cin >> H[i];

      vector<int> ans(n+5, INF);
    ans[0] = 0;
    for(int i = 0; i < n; i++){
      ans[i+1] = min(ans[i+1], ans[i] + abs(H[i+1] - H[i]));
      ans[i+2] = min(ans[i+2], ans[i] + abs(H[i+2] - H[i]));
    }
    cout << ans[n-1]<<endl;

     //double end_time = clock();
  //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
   
    return 0;
}

Share:
Read More

Construct the Array

, , No comments

Construct the Array

Topic: DP

Complexity: O(n) 

Solution:

Code:

const long long mod = 1000000000+7;
long countArray(int n, int k, int x) {
    // Return the number of ways to fill in the array.
    vector<long long> a(n), b(n);
    a[0] = x == 1 ? 1 : 0;
    b[0] = x == 1 ? 0 : 1;

    for(int i = 1; i < n; i++){
        a[i] = b[i - 1] % mod;
        b[i] = (a[i- 1]*(k-1) + b[i-1] * (k-2) )%mod;
    }
    return a[n-1];
}

Share:
Read More

About

let's start CODE

Popular Posts

  • E-maxx training part - 01
                             Binary Exponentiation 1230 - MODEX              Solution 11029 - Leading and Trailing      Solution I...
  • 11029 - Leading and Trailing
    11029 - Leading and Trailing  Topic: Binary Exponentiation  
  • A - Frog 1
    A - Frog 1 Solution 01: IH19980412 //copy 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 2...