Ankur's Blog

let's start Code

11503 - Virtual Friends

, , , No comments

11503 - Virtual Friends

Topic: DSU

solution 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
#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);

int parent[MAX*2], Rank[MAX];

void Initialization()
{
  for(int i = 0; i <= MAX; i++)
    parent[i] = i, Rank[i] = 1;
}

int find_parent(int x)
{
  if(parent[x] == x)
    {
        return x;
    }
  return parent[x] = find_parent(parent[x]);
}

void make_union(int x, int  y)
{
    int p = find_parent(x);
    int q = find_parent(y);
    if(p != q){
        if(Rank[p] < Rank[q])
            swap(p,q);
        parent[q] = p;
        Rank[p] += Rank[q];
    }
}

bool isUnion(int x, int y)
{
  return find_parent(x) == find_parent(y);
}

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 t;
    cin >> t;
    while(t--){
        Initialization();
        int F;
        cin >> F;
        int cnt = 1;
        map<string, int> mp;
        map<int, int>res;
        map<int,int>visit,ans;
        for(int i = 1; i <= F; i++){
            string s1,s2;
            cin >> s1 >> s2;
            if(mp[s1] == 0)mp[s1] = cnt++;
            if(mp[s2] == 0)mp[s2] = cnt++;
            int x = mp[s1];
            int y = mp[s2];
            make_union(x,y);
            cout << Rank[find_parent(x)]<<endl;
            //cerr << Rank[find_parent(x)] << " " <<Rank[find_parent(y)]<<endl;
        }
    }

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

Share:
Read More

10685 - Nature

, , No comments

10685 - Nature

Topic: ডিসজয়েন্ট সেট

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

#define INF 1<<30
#define MAX 10005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

int parent[5005];

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

int find_parent(int x)
{
  if(parent[x] == x)
    {
        return x;
    }
  return parent[x] = find_parent(parent[x]);
}

void make_union(int x, int  y)
{
  parent[find_parent(x)] = find_parent(y);
  //parent[find_parent(y)] = find_parent(x);
}

bool isUnion(int x, int y)
{
  return find_parent(x) == find_parent(y);
}

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 c,r;
    while(1){
        cin >> c >> r;
        if(c == 0 && r == 0)break;
        map<string, int> mp;
        for(int i = 1; i <= c; i++){
            string s;
            cin >> s;
            mp[s] = i;
        }
        Initialization(c);
        for(int i = 1; i <= r; i++){
            string str1, str2;
            cin >> str1 >> str2;
            int x = mp[str1];
            int y = mp[str2];
                make_union(y,x);
        }
        int mx = 0;
        map<int,int>ans;
        for(int i = 1; i <= c; i++){
            int k = find_parent(i);
            //cerr << i << "---->"<<k<< endl;
            ans[k]++;
            mx = max(mx,ans[k]);
        }
        cout << mx << endl;
    }

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

Share:
Read More

459 - Graph Connectivity

, , , No comments

459 - Graph Connectivity

Topic: Union Find Algorithm

ডাটা স্ট্রাকচার: ডিসজয়েন্ট সেট(ইউনিয়ন ফাইন্ড)

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

#define INF 1<<30
#define MAX 10005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

int parent[100];

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

int find_parent(int x)
{
  if(parent[x] == x)return x;
  return parent[x] = find_parent(parent[x]);
}

void make_union(int x, int  y)
{
  parent[find_parent(x)] = find_parent(y);
}

bool isUnion(int x, int y)
{
  return find_parent(x) == find_parent(y);
}

int main()
{
 // FASTIO
   /*
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
   #endif
    //*/
     int t,i , cs;
    bool space = false;
    scanf("%d",&t);
    getchar();
    for ( cs = 1 ; cs <= t ; cs++ , space = 1)
    {    if(space) printf("\n");
         char lim;
         string str;
        cin>>lim;
        getchar();
        Initialization(lim-'A');
        int ans = lim-'A' + 1;
        while(getline(cin,str) && str!="")
        {
           // cerr << str << endl;
            int x = str[0]-'A';
            int y = str[1]-'A';
            if(!isUnion(x,y)) make_union(x,y) , ans-- ;

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

Share:
Read More

B. F1 Champions

, No comments

B. F1 Champions

operatopr overloading conecpt 

Solution 01: help from rng_58


 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
#include<bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define MAX 10005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);


 int p[] = {25, 18, 15, 12, 10, 8, 6, 4, 2, 1};
 map <string, int> mp;
 string name[1010];
 int a[1000][1000], point[1000];
 vector<pair<string, int> > v;

 bool cmp1(int x, int y)
 {
    if(point[x] != point[y]) return (point[x] > point[y]);
    if(a[x][0] != a[y][0]) return (a[x][0] > a[y][0]);

    for(int i = 0; i < 100; i++) if(a[x][i] != a[y][i]) return a[x][i] > a[y][i];
    
    return true;
 }

 bool cmp2(int x, int y)
 {
    if(a[x][0] != a[y][0]) return (a[x][0] > a[y][0]);
    if(point[x] != point[y]) return (point[x] > point[y]);
    for(int i = 0; i < 100; i++) if(a[x][i] != a[y][i]) return a[x][i] > a[y][i];
    
    return true;
 }

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 T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        for(int i = 0; i < n; i++){
            string s;
            cin >> s;
            v.push_back({s,i}); // string + position
        }
    }

    int N = 0;
    for(int i = 0; i < v.size(); i++){
        mp[v[i].first] = 0;
       // cerr<<v[i].first << " "<<v[i].second << endl;
    }
    for(auto it = mp.begin(); it != mp.end(); it++){
       // cerr << it->first << " "<<it->second << endl;
        name[N] = it->first;
        it->second = N;
        N++;
        // cerr << it->first << " "<<it->second << endl;
        //cerr << name[N-1]<< "\n";
    }

    for(int i = 0; i < v.size(); i++){
        int player = mp[v[i].first];
        int rank = v[i].second;
        a[player][rank]++;
        if(rank < 10) point[player] += p[rank];
    }

    /*for(int i =0; i < 10; i++){
        for(int j = 0; j < 10; j ++){
            cerr << setw(2) << a[i][j];
        }
        cerr << endl;
    }*/

    int cnt = 0, cnt2 = 0;
    for(int  i =0; i < N; i++){
        if(cmp1(i,cnt)) cnt = i;
        if(cmp2(i, cnt2)) cnt2 = i;
    }

    cout << name[cnt] << "\n" << name[cnt2] << "\n";
    

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

    return 0;
}


         Another solution Github gist link

Share:
Read More

Fenwick (Binary Indexed) Trees

, No comments

Fenwick প্রোগ্রামিং প্রবলেম (Programming Problem in Bengali)(Binary Indexed) Trees

Fenwick Tree 

Where's the tree in Fenwick tree? 

visualgo

kartikkukreja 

ডাটা স্ট্রাকচার: বাইনারি ইনডেক্সড ট্রি

Topcoder Algorithm 

Zobayer blog ( see also Felix halim comment) 

CF blog 

Youtube Video:

Algorithms live 

Bangla Tutorial 

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
//Space Complexity: O(N)
// Time Complexity: O(NlogN)
#include<bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define MAX 10005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

int BIT[MAX], n;
int a[MAX] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};

void update(int x, int val)
{
    for(; x <= n; x += x & (-x))
        BIT[x] += val;
}

int query(int x)
{
    int sum = 0;
    for(; x > 0; x -= x & (-x))
        sum += BIT[x];
    return sum;
}

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
    //*/
    scanf("%d", &n);
    int i;
    for(i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        update(i, a[i]);
    }
    printf("sum of first 10 elements is %d\n", (query(10)) );
    printf("sum of all elements in range [2, 7] is %d\n", (query(7) - query(2 - 1)) );

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

    return 0;
}


2D BIT:


Problem:

Binary Indexed Trees with some Solved Example.

Spoj:

TRIPINV - Mega Inversions 

INVCNT - Inversion Count 

YODANESS - Yodaness Level 

INCSEQ - Increasing Subsequences 

HORRIBLE - Horrible Queries 

CTRICK - Card Trick 

MATSUM - Matrix Summation 

NICEDAY - The day of the competitors 

DQUERY - D-query 

MCHAOS - Chaos Strings 

Codeforces:

C. Little Girl and Maximum Sum 

D. Pashmak and Parmida's problem 

LightOj:

1112 - Curious Robin Hood  Solution

 

 

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

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