Ankur's Blog

let's start Code

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

Segmented Sieve

, , No comments

Segmented Sieve [ Number Theory ]

Zobayer Blog

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>
using namespace std;
#define MAX 100009

typedef long long ll;

vector<int>primes;


void seiveOfEratosthenes()
{
  bool flag[MAX+1];

  for(int i = 0; i <= MAX; i++)
    flag[i] = true;
  primes.push_back(2);

  flag[0] = flag[1] = false;

  for(int i = 4; i <= MAX; i += 2) flag[i] = false;

    for(int i = 3; i <= MAX; i += 2){

      if(flag[i] == true){ // i is prime
        primes.push_back(i);
        for(int j = i+i; j <= MAX; j = j+i){
          flag[j] = false; // j is not prime
        }
      }
    }
}

 void segmentedSeive(ll L, ll R)
 {
  bool isPrime[R-L+1];
  for(int i = 0; i <= (R-L+1); i++)
    isPrime[i] = true;

  if(L == 1)isPrime[0] = false; 

  for(int i = 0; i < (int)primes.size() && primes[i]*primes[i] <= R; i++){
    ll curPrime = primes[i];
    ll base = curPrime * curPrime;
    if(base < L){
      base = ( (L+curPrime - 1)/curPrime)*curPrime;
    }

    for(ll j = base; j <= R; j += curPrime)
      isPrime[j - L] = false;
  }
  for(int i = 0; i <= R - L; i++){
    if(isPrime[i] == true)
      cout << L + i << endl;
  }
 } 


int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif
    double start_time = clock();
    seiveOfEratosthenes();
    ll L,R;
    cin >> L >> R;
    segmentedSeive(L,R);
    return 0;

    double end_time = clock();
   // printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
   
    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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
#define MAX 46656
#define LMT 216
#define LEN 4830
#define RNG 100032

unsigned base[MAX/64], segment[RNG/64], primes[LEN];

#define sq(x) ((x)*(x));
#define mset(x,v) memset(x,v,sizeof(x))
#define chkC(x,n) (x[n>>6]&(1<<((n>>1)&31)))
#define setC(x,n) (x[n>>6]|=(1<<((n>>1)&31)))

typedef long long ll;

//Generates all the necessary prime numbers and marks them in base.
void seive()
{
  unsigned i,j,k;
  for(i = 3; i < LMT; i += 2)
    if(!chkC(base, i))
      for(j = (i * i), k = (i << 1); j < MAX; j += k)
        setC(base, j);
      for(i = 3, j = 0; i < MAX; i += 2)
        if(!chkC(base, i))
          primes[j++] = i;
}

// Returns the prime-count within range [a,b] and marks them in sement.
 int segmentedSeive(int a, int b)
 {
  unsigned i,j,k, cnt = (a <= 2 && 2 <= b) ? 1 : 0;
  if(b < 2) return 0;
  if(a < 3) a = 3;
  if(a%2 == 0)a++;
  mset(segment,0);
  for(i = 0; ( primes[i] * primes[i] ) <= b; i++){
    j = primes[i] * ((a + primes[i] - 1) / primes[i]);
    if(j%2 == 0) j += primes[i];
    for(k = (primes[i] << 1); j <= b; j += k)
      if(j != primes[i])
        setC(segment, (j-a));
  }
  for(i = 0; i <= (b - a); i += 2)
    if(!chkC(segment, i)){
      cnt++;
    }
    return cnt;
 } 


int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif
    double start_time = clock();
    seive();
    int L,R;
    cin >> L >> R;
    cout << segmentedSeive(L,R)<<endl;
    return 0;

    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

1387 - Setu

, No comments

1387 - Setu

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
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    // freopen("in.txt", "r", stdin);
    int T;
    cin >> T;
    for(int cs = 1; cs <= T; ++cs){
        long long ans = 0;
        int n;
        cin >> n;
        cout << "Case "<<cs<< ":\n";
        while(n--){
            string s;
            cin >> s;
            if(s == "donate"){
                int x;
                cin >> x;
                ans += x;
            }
            else{
                cout << ans<<endl;
            }
        }
    }
}

Share:
Read More

12461 - Airplane

, , , No comments

12461 - Airplane

EXPLANATION

Solution:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include<bits/stdc++.h>
using namespace std;

int main()
{
int n;
while(cin >> n && n){
cout << "1/2\n";
}
return 0;
}

Share:
Read More

Kruskal’s Algorithm [ Minimum Spanning Tree ]

, , , , No comments

Kruskal’s Algorithm [ Minimum Spanning Tree ]

গ্রাফ থিওরিতে হাতেখড়ি ৬: মিনিমাম স্প্যানিং ট্রি(ক্রুসকাল অ্যালগোরিদম)

Visualization

Hackerearth

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
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
#include<bits/stdc++.h>
using namespace std;
const int maxn = (int) 2e5 + 5;

struct edge
{
    int u,v,w;
};

vector<edge>graph, output;
int parent[maxn], mstValue = 0;

bool cmp (edge a, edge b)
{
    return a.w < b.w;
}

int Find(int r)
{
    if(parent[r] == r)
        return r;
    return parent[r] = Find(parent[r]);
}

void initPar(int r)
{
    for(int i = 0; i <= r; i++)parent[i] = i;
}

void kruskals_Algorithm(int n)
{
    sort(graph.begin(), graph.end(), cmp);
    for(int i = 0; i < (int)graph.size(); i++){
        cout << graph[i].u << " "<<graph[i].v << " "<< graph[i].w<<endl;
    }
    initPar(n);
    int cnt = 0;

    for(int i = 0; i < (int)graph.size(); i++){
        int uPr = Find(graph[i].u);
        int vPr = Find(graph[i].v);

        if(uPr != vPr){
            if(cnt == n-1) break;

            output.push_back(graph[i]);
            mstValue += graph[i].w;
            parent[uPr] = vPr;
            cnt++;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
   cout.tie(nullptr);
   // freopen("in.txt", "r", stdin);

    int n,e;
    cin >> n >> e;
    cout << n << " & " << e << endl;
    for(int i = 0; i < e; i++){
        int u,v,w;
        cin >> u >> v >> w;
        edge input;
        input.u = u;
        input.v = v;
        input.w = w;
        graph.push_back(input);
    }

    kruskals_Algorithm(n);

    cout << "MST Value : " << mstValue << endl;

    for(int i = 0; i < (int)output.size(); i++){
        cout << output[i].u << " "<<output[i].v << " "<< output[i].w<<endl;
    }

    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
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
#include<bits/stdc++.h>
using namespace std;

const int MAX = 300005;
int id[MAX], nodes, edges, idx;

pair <int, pair<int, int> > p[MAX], output[MAX];

void initialize()
{
    for(int i = 0; i < MAX; i++)
    {
        id[i] = i;
    }
}

int root(int x)
{
    while(id[x] != x)
    {
        id[x] = id[ id[x] ];
        x = id[x];
    }
    return x;
}

void union1(int x, int y)
{
    int p = root(x);
    int q = root(y);
    id[p] = id[q];
}

int kruskal(pair <int, pair<int, int> > p[])
{
    idx = 0;
    int x,y;
    int cost, minimumcost = 0;

    for(int i = 0; i < edges; i++)
    {
        /// selecting edges one by one in increasing order from the beginning.
        x = p[i].second.first;
        y = p[i].second.second;
        cost = p[i].first;
        /// check if the selected edge is creating a cycle or not
        if(root(x) != root(y))
        {
            minimumcost += cost;
            output[idx++] = make_pair(cost, make_pair(x,y));
            union1(x,y);
        }
    }
    return minimumcost;
}

int main()
{
   // freopen("in.txt", "r", stdin);

        int x,y;
        int weight,cost,minimumcost,price;
        initialize();
        scanf("%d %d", &nodes, &edges);
        //cout << nodes << " & "<<edges<<endl;
        for(int i = 0; i < edges; i++)
        {
            cin >> x >> y >> weight;
            p[i] = make_pair(weight, make_pair(x,y));
        }
        sort(p, p+edges);
       // for(int i = 0; i < edges; i++){
           // cout << p[i].second.first << " "<<p[i].second.second << " "<<p[i].first<<endl;
        //}
        minimumcost = kruskal(p);
        cout << "MST :- ";
        cout << minimumcost<<endl;
        for(int i = 0; i < idx; i++){
            cout << output[i].second.first << " "<<output[i].second.second << " "<< output[i].first << endl;
        }
    return 0;
}

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...