Ankur's Blog

let's start Code

Showing posts with label Codechef. Show all posts
Showing posts with label Codechef. Show all posts

Sereja and Salesman

, , , No comments

Problem Link: SEAKAM

Topic: Bitmask Dp

Explanation: GKCS

implementation:


Share:
Read More

GCD and LCM

, , No comments
Share:
Read More

SUBXOR - SubXor

, , , , No comments

SUBXOR - SubXor

Subarray Xor

Topic: Trie Tree 

Explanation 

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
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define MAX 200005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;


struct trie
{
  int L,R;
  int lft, rgt;

  trie(){
    L = R = 0;
    lft = rgt = -1;
  }
};

int Index = 0;

void Insert(int value, int idx, int depth, trie *tree)
{
  for(int i = depth-1; i >= 0; i--){
    int bit = (value >> i ) & 1;
    if(bit){
      tree[idx].R++;
      if(tree[idx].rgt == -1){
        tree[idx].rgt = ++Index;
        idx = Index;
      }
      else idx = tree[idx].rgt;
    }
    else{
      tree[idx].L++;
      if(tree[idx].lft == -1){
        tree[idx].lft = ++Index;
        idx = Index;
      }
      else idx = tree[idx].lft;
    }
  }
}

int Query(int value, int cmp, int idx, int depth, trie* tree)
{
  int ans = 0;
  for(int i = depth-1; i >= 0; i--){
    int vBit = (value >>i) & 1;
    int cBit = (cmp >> i) & 1;
    if(cBit){
      if(vBit){
        ans += tree[idx].R;
        idx = tree[idx].lft;
      }
      else{
        ans += tree[idx].L;
        idx = tree[idx].rgt;
      }
    }
    else{
      if(vBit) idx = tree[idx].rgt;
      else idx = tree[idx].lft;
    }
    if(idx == -1)break;
  }
  return ans;
}

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--){
      trie tree[MAX];
      Index = 0;
      int n,k;
      cin >> n >> k;
      int XOR = 0;
      ll  ans = 0;
      Insert(0,0,20,tree);
      for(int i =0; i < n; i++){
        int x;
        cin >> x;
        XOR = XOR ^ x;
        ans += Query(XOR,k,0,20,tree);
        Insert(XOR,0,20,tree);
      }
      cout << ans << endl;
    }
    

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

    return 0;
}

Solution 02

Solution 03

Share:
Read More

Max and Electrical Panel

, , No comments

Max and Electrical Panel

 Solution 01:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,c;
    cin >> n >>c;
    int lo = 0, hi = n, res = 0;
    while(hi-lo > 1){
        if(res)cout << 2<<endl<<flush;
        int mid = lo + (hi-lo-1)/8+1;
        cout << 1 << " "<<mid<<endl<<flush;
        cin >> res;
        if(res)hi = mid;
        else lo = mid;
    }
    cout << 3 << " "<<hi<<endl<<flush;
    return 0;
}

Solution 02:



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,c;
    cin >> n >>c;
    int lo = 1, hi = n+1, res = 0;
    while(hi-lo > 1){
        if(res)cout << 2<<endl<<flush;
        int mid = lo + (hi-lo)/60;
        cout << 1 << " "<<mid<<endl<<flush;
        cin >> res;
        if(res)hi = mid+1;
        else lo = mid+1;
    }
    cout << 3 << " "<<lo<<endl<<flush;
    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
37
#include<bits/stdc++.h>
using namespace std;

bool solve(int x)
{
    cout << "1 "<<x<<endl<<flush;
    int a;
    cin >> a;
    return a;
}

int main()
{
    int n,c;
    cin >> n >>c;
    int ans = -1, lg = 0, le = -1;
    int range = sqrt(n);
    //cout << range<<endl;
    for(int i = 1; i <= n; i += range){
           // cout << i << endl;
        if(solve(i)){
            ans = i;
            break;
        }
        lg = i;
        le = min(i+range-1, n);
    }
    cout << 2<<endl<<flush;
    for(int i = lg; i <= le; i++){
        if(solve(i)){
            ans = i;
            break;
        }
    }
    cout << 3 << " "<<ans<<endl<<flush;
    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...

Categories