Ankur's Blog

let's start Code

maximum XOR

, , No comments

Maximum XOR value of a pair from a range


 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
#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);
typedef long long ll;

int MaxXORInRange(int l, int r)
{
  int LXR = l ^ r; // xor limits
  int msbPos = 0;
  while(LXR){
    msbPos++;
    LXR >>= 1;
  }

  int maxXOR = 0;
  int two = 1;
  while(msbPos--){
    maxXOR += two;
    two <<= 1;
  }
  return maxXOR;
}

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 L,R;
    cin >> R >> R;
    cout << MaxXORInRange(L,R)<<endl;
    //double end_time = clock();
    //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
    return 0;
}

Find the maximum subarray XOR in a given array

 O(N^2) solution

Anther O(N) solution using Trie Tree:  Gist_Link



 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
#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);
typedef long long ll;
#define INT_SIZE 32

struct TrieNode
{
  int value;
  TrieNode *ar[2];
};

TrieNode *newNode()
{
  TrieNode *temp = new TrieNode;
  temp->value = 0;
  temp->ar[0] = temp->ar[1] = NULL;
  return temp;
}

void insert(TrieNode *root, int pre_xor)
{
  TrieNode *temp = root;

  for(int i = INT_SIZE - 1; i >= 0; i--){
    bool val = pre_xor & (1 << i);
    if(temp->ar[val] == NULL)
      temp->ar[val] = newNode();
    temp = temp->ar[val];
  }

  temp->value = pre_xor;
}

int query(TrieNode *root, int pre_xor)
{
  TrieNode *temp = root;
  for(int i = INT_SIZE - 1; i >= 0; i--){
    bool val = pre_xor & (1 << i);
    if(temp->ar[1-val] != NULL)
      temp = temp->ar[1-val];
    else if(temp->ar[val] != NULL)
      temp = temp->ar[val];
  }
  return pre_xor ^ (temp->value);
}


int maxSubarrayXOR(int ar[], int n)
{
  TrieNode *root = newNode();
  insert(root, 0);

  int res = INT_MIN, pre_xor = 0;
  for(int i = 0; i < n; i++){
    pre_xor = pre_xor ^ ar[i];
    insert(root, pre_xor);

    res = max(res, query(root, pre_xor));
  }
  return res;
}

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;
    cin >> n;
    int a[n+2];
    for(int i = 0; i < n; i++){
      cin >> a[i];
    }

    cout << maxSubarrayXOR(a,n)<< endl;

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

    return 0;
}

Share:
Read More

ট্রাই ট্রি ( 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

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