Ankur's Blog

let's start Code

ট্রাই ট্রি ( Trie Tree )

, , No comments

ট্রাই ট্রি ( Trie Tree )

ডাটা স্ট্রাকচার: ট্রাই (প্রিফিক্স ট্রি/রেডিক্স ট্রি)

Trie (Keyword Tree) -- H1 ,  H2

Zobayer blog -- using static array

Quora Tutorial 

Implemention 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
 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
117
118
119
120
#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;

const int ALPHABET = 26;
#define scale(x) (x - 'a')

struct TrieTree
{
    struct TrieTree *children[ALPHABET];
    bool isEndOfWord;
};

struct TrieTree *getNode()
{
    struct TrieTree *Node = new TrieTree;
    Node->isEndOfWord = false;

    for(int i = 0; i < ALPHABET; i++)
        Node->children[i] = NULL;
    return Node;
}

void insert(struct TrieTree *root, string s)
{
    struct TrieTree *curr = root;
    for(int i = 0; i < s.size(); i++){
        int idx = scale(s[i]);
        if(!curr->children[idx])
            curr->children[idx] = getNode();

        curr = curr->children[idx];
    }
    // mark last node as leaf
    curr->isEndOfWord = true;
}

bool search(struct TrieTree *root, string s)
{
    struct TrieTree *curr = root;
    for(int i = 0; i < s.size(); i++){
        int idx = scale(s[i]);
        if(!curr->children[idx])
            return false;

        curr = curr->children[idx];
    }
    return (curr != NULL && curr ->isEndOfWord);
}

bool isEmpty(TrieTree* root)
{
    for(int i = 0; i < ALPHABET; i++)
        if(root->children[i])
            return false;
        return true;
}

TrieTree* Remove(TrieTree* root, string s, int depth = 0)
{
    if(!root)return NULL;
    if(depth == s.size()){
        if(root->isEndOfWord)
            root->isEndOfWord = false;

        if(isEmpty(root)){
            delete(root);
            root = NULL;
        }
        return root;
    }

    int idx = scale(s[depth]);
    root->children[idx] = Remove(root->children[idx], s, depth+1);

    if(isEmpty(root) && root->isEndOfWord == false){
        delete(root);
        root = NULL;
    }
    return root;
}


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
    //*/
    string str[] = { "the", "a", "there", 
                      "answer", "any", "by", 
                      "bye", "their", "hero", "heroplane"}; 


    int n = sizeof(str)/sizeof(str[0]);
    struct TrieTree *root = getNode();

    for(int i = 0; i < n; i++)
        insert(root, str[i]);

    // Search for different keys 
    search(root, "the")? cout << "FOUND!\n" : cout << "NOT FOUND\n"; 
    search(root, "these")? cout << "FOUND!\n" : cout << "NOT FOUND\n";

    Remove(root, "heroplane");
   //  Remove(root, "hero");
    search(root, "hero") ? cout << "FOUND!\n" : cout << "NOT FOUND\n";

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

Implementation02

Problem:

 EMOTICON - Emoticons

SUBXOR - SubXor 

MORSE - Decoding Morse Sequences 

PHONELST - Phone List 

4682 - XOR Sum   *Solution*

Equivalent Suffix Tries 

LightOj 

11362 - Phone List 

10226 - Hardwood Species 

11488 - Hyper Prefix Sets 

Shortest Prefixes (POJ) 

IMMEDIATE DECODABILITY (POJ) 

 

 

Share:
Read More

793 - Network Connections

, , No comments

793 - Network Connections

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
80
81
82
#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[MAX];

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 t;
    cin >> t;
    bool space = false;
    for(int cs = 0; cs < t; cs++, space = true){
      Initialization(MAX);
      if(space)cout << endl;
        int N;
        cin >> N;
        getchar();
        int yes = 0, no = 0;
           string str;
            int x,y;
        while(getline(cin, str)){
          if(str == "")break;
          char ch;
          stringstream S(str);
         // S >> ch;
          S >> ch >>x >> y;
            if(ch == 'c'){
                make_union(x,y);
            }
            else{
                //cerr << parent[x] << " "<<parent[y]<<endl;
                if(isUnion(x,y))yes++;
                else no++;
            }
        }
        cout << yes << ","<<no<<endl;
    }


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

Share:
Read More

Merging Communities

, , No comments

Merging Communities

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
#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(int n)
{
  for(int i = 0; i <= n; 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 N,Q;
        cin >> N >> Q;
        Initialization(N);
        int cnt = 1;
        map<string, int> mp;
        for(int i = 1; i <= Q; i++){
            int x,y;
            char ch;
            cin >> ch;
            if(ch == 'M'){
                cin >> x >> y;
                make_union(x,y);
            }
            else{
                cin >>x;
            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;
}


Another Solution

Share:
Read More

Disjoint Set Union

, , No comments
Share:
Read More

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

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