SPOJ

                            Watching Video                                                                   binary search Problem Link #include <iostream> using namespace std; long n, d; long arr[1000001]; bool func(int t) {     long long tmp=0;     for(int i=1;i<=t;i++)         tmp+=arr[i];     t++;          while(tmp>=d && t < n+1) {         if(tmp <d)             return false;         tmp -= d;         tmp+=arr[t];         t++;     }          if(t==n+1)         return true;     else         return false; } int bs(int low, int high) {     int mid;     while(low < high)     {         mid = (low + high) / 2;                 if(func(mid))         {             high = mid;         }         else         {             low = mid + 1;         }     }     return high; } int main() {     cin >> n >> d;     for(int i = 1; i <= n; i++)     {         cin >> arr[i];     }     for(int i

                          Round Table Meeting Problem Link #include <iostream> #include <cmath> #include <climits> using namespace std; int main() {     int n, q;     int x, y;     cin >> n >> q;     int arr[2 * n + 1];     for(int i = 1; i <= n; i++)     {         cin >> arr[i];         arr[i + n] = arr[i];     }     for(int k = 0; k < q; k++)     {         cin >> x >> y;         int dist = INT_MAX;         int minDist = INT_MAX;         int posx = -1;         int posy = -1;                 if(x == y)         {                       minDist = 0;                     }                 else         {                                 for(int i = 1; i <= 2 * n; i++)             {                 if(arr[i] == x)                 {                       posx = i;                                 }                 else if(arr[i] == y)                 {                       posy = i;

                                     Architect's Dilemma..!                                                                     Binary Search Problem Link #include <iostream> #include <algorithm> using namespace std; typedef long long ll; ll n, w, a[100005], pre[100005], maxx[100005]; bool f(int x) {     for(int i = 0, j = x; j <= n; j++, i++)     {         if((x * maxx[j] - (pre[j] - pre[i])) <= w)             return 1;     }     return 0; } int main() {     cin >> n >> w;     for(int i = 1; i <= n; i++)         cin >> a[i];     sort(a + 1, a + n + 1);     for(int i = 1; i <= n; i++)     {         pre[i] = pre[i - 1] + a[i];         maxx[i] = max(maxx[i - 1], a[i]);     }     int l = 1, r = n, ans;     while(l <= r)     {         int mid = (l + r) / 2;         if(f(mid))         {             ans = mid;             l = mid + 1;         }    

                      Moving to New Office                                   DP Problem Link #include <iostream> #define INF 99999999 using namespace std; int main() {     int t, x, y, n;     int m[100];     long dp[101][101];     cin >> t;     while(t--)     {         cin >> x >> y;         cin >> n;         for(int i = 0; i < n; i++)         {             cin >> m[i];         }         for(int i = 0; i < n; i++)         {             for(int j = 0; j < n; j++)                 dp[i][j] = INF;         }         for(int l = 2; l <= n; l++)         {             for(int i = 0; i <= n - l; i++)             {                 int j = i + l - 1;                 if(l == 2)                 {                     dp[i][j] = 0;                     //cout << "i = " << i << " j = " << j << " Val = " <&

                                Numbers II                                               Binary Search Program Link #include <iostream> #include <algorithm> using namespace std; typedef long long ll; ll findTerm(ll a, ll b, ll lcm, ll value) {     return (value / a) + (value / b) - (value / lcm); } ll  solve(ll a, ll b, ll n) {     ll gcd  = __gcd(a,b);     ll lcm = (a * b) / gcd;     ll rema = lcm / a;     ll remb = lcm / b;     ll low = (n / (rema + remb - 1))  * lcm;     ll high = min(a, b) * n;     ll ans;     while(low <= high)     {         ll mid = (low + high) / 2;         ll term = findTerm(a, b, lcm, mid);         if(term >= n)         {             ans = mid;             high = mid - 1;         }         else         {             low = mid + 1;         }     }     return ans; } int main() {     int t;     ll a, b, n;     cin >> t;     while

FREQUENT                                                         segment tree #include <iostream> #include <algorithm> #include <stdio.h> #define sf(i) scanf("%d", &i) #define pf(i) printf("%d\n", i) #define pii pair<int, int> #define mp make_pair #define f first // value #define s second //frequency #define FOR(a, b) for(int i = a; i < b; i++) using namespace std; const int N = 100001; struct node {     pii m;     pii l;     pii r; }; int n, q; int arr[N]; node seg[4 * N]; node combine(node &a, node &b) {     node res;     if(a.l.f == b.r.f) //if all the elements are same     {         res.l.f = res.r.f = res.m.f = a.l.f;         res.l.s = res.r.s = res.m.s = a.l.s + b.r.s;     }     else     {         res.l = a.l;         res.r = b.r;         if(a.l.f == b.l.f) //if first element of left is same as first element of right         {    

                                              D-Query                                            segment tree + offline method #include <iostream> #include <algorithm> #include <stdio.h> #include <map> #define sf(i) scanf("%d", &i) #define pf(i) printf("%d\n", i) using namespace std; const int N = 30001; const int Q = 200001; struct node {     int l, r;     int pos,     int val; }; int n, q; node arr[N + Q]; int result[Q]; int seg[4 * N]; map<int, int> last_pos; node makenode(int l, int r, int pos, int val) {     node temp;     temp.l = l;     temp.r = r;     temp.pos = pos;     temp.val = val;     return temp; } void update(int l, int r, int index, int pos, int val) {     if(l == r)     {         seg[index] = val;     }     else     {         int mid = (r + l) / 2;         if(pos <= mid)         {             update(l, mid, 2 * i

                                                     GSS1                                                                 segment tree Problem Link #include <iostream> #include <stdio.h> using namespace std; struct node {     long bestSum, leftSum, rightSum, totalSum; }; int n; long t; node seg[200003]; long arr[50003]; node combine(node &lc, node &rc) {     node temp;     temp.totalSum = lc.totalSum + rc.totalSum;     temp.leftSum = max(lc.leftSum, lc.totalSum + rc.leftSum);     temp.rightSum = max(rc.rightSum, rc.totalSum + lc.rightSum);     temp.bestSum = max(lc.rightSum + rc.leftSum, max(lc.bestSum, rc.bestSum));     return temp; } void buildTree(int l, int r, int index) {     if(l == r)     {         seg[index].bestSum = seg[index].rightSum = seg[index].leftSum = seg[index].totalSum = arr[l];     }     else     {         int mid =  l + ((r - l) >> 1);         int lchild = (index &l

                                Sereja and Brackets                                   segment tree Problem Link #include <iostream> #include <cmath> #include <cstring> using namespace std; string s; struct node {     long int len; //max length of matched brackets     int tn, tp; // tp = total number of '(' brackets                 //tn = total number of ')' brackets }; node func(node a, node b) {     node temp;     int len = min(a.tp, b.tn);     temp.len = a.len + b.len + 2 * len;     temp.tp = a.tp + b.tp - len;     temp.tn = a.tn + b.tn - len;     return temp; } void buildTree(node seg[], int l, int r, int index) {     if(l == r)     {         seg[index].len = seg[index].tp = seg[index].tn = 0;         if(s[l] == ')')         {             seg[index].tn = 1;         }         else         {             seg[index].tp = 1;         }      }      el

                      Chef and Sub Array Problem Link #include <iostream> #include <stdio.h> #define sf(i) scanf("%d", &i) #define pf(i) printf("%d\n", i) using namespace std; int n, k, p; int a[100005], b[300005]; int sum[300005], tree[700005]; string s; void buildTree(int index, int s, int e) {     if(s == e)     {         tree[index] = sum[s];     }     else     {         int mid = (s + e) / 2;         buildTree(2 * index + 1, s, mid);         buildTree(2 * index + 2, mid + 1, e);         tree[index] = max(tree[2 * index + 1], tree[2 * index + 2]);     } } int query(int index, int s, int e, int qs, int qe) {     if(qs > e || qe < s)         return 0;     if(qs <= s && qe >= e)         return tree[index];     int mid = (s + e) / 2;     int left = query(2 * index + 1, s, mid, qs, qe);     int right = query(2 * index + 2, mid + 1, e, qs , qe);

                                        Book of Evil Problem Link #include <iostream> #include <vector> #include <cstring> #include <stdio.h> #define sf(i) scanf("%d", &i) #define pf(i) printf("%d\n", i) #define pb push_back using namespace std; const int N = 1e5 + 1; int h[N]; bool mark[N],ans[N]; vector<int> g[N]; int n, m, d, D, R; void dfs(int s, int p) {     h[s] = h[p] + 1;     ans[s] &= (h[s] <= d);     if(mark[s] && h[s] > D)     {         D = h[s], R = s;     }     for(int i = 0; i < g[s].size(); i++)     {         int v = g[s][i];         if(v == p)             continue;         dfs(v,s);     } } int main() {     sf(n), sf(m), sf(d);     int a, b;     D = 0;     h[0] = -1;     for(int i = 1; i <= m; i++)     {         sf(R);         mark[R] = true;     }     for(int i = 1; i <= n - 1; i++)     {

                            Chloe and pleasant prizes Problem Link #include <iostream> #include <vector> #define pb push_back using namespace std; typedef long long int li; const li N = 2 * 1e5 + 5; const li inf = 1LL<<60; vector<li> g[N];  li p[N]; li sum[N]; li dp[N]; li n, u, v; li ans = -inf; void dfs(int s, int t) {          dp[s] = -inf;     sum[s] = p[s];     for(int i = 0; i < g[s].size(); i++)     {         int v = g[s][i];         if(v == t)            continue;         dfs(v, s);         sum[s] += sum[v];         if(dp[s] > -inf)ans=max(ans,dp[s]+dp[v]);         dp[s]=max(dp[s],dp[v]);     }     dp[s] = max(dp[s], sum[s]); } int main() {     cin >> n;     for(li i = 1; i <= n; i++)     {         cin >> p[i];             }     for(li i = 0; i < n - 1; i++)     {         cin >> u >> v;         g[u].pb(v);         g[v

                                           Civilization Problem Link #include <iostream> #include <vector> #include <stdio.h> #define sf(i) scanf("%d", &i) #define pf(i) printf("%d\n", i) #define pb push_back using namespace std; const int N = 3e5 + 1; vector<int> g[N]; int parent[N]; int diameter[N]; bool isUsed[N]; int n, m, q, maxi, maxiv; int rad(int a) {     return (diameter[a] + 1) / 2; } int find(int a) {     if(parent[a] == a)     {         return a;     }     return parent[a] = find(parent[a]); } void unite1(int a, int b) {     a = find(a);     b = find(b);     if(a > b)         swap(a, b);     parent[b] = a; } void unite(int a, int b) {     a = find(a);     b = find(b);     if(a > b)     {         swap(a, b);     }     parent[b] = a;     diameter[a] = max(rad(a) + rad(b) + 1, max(diameter[a], diameter[b])); } vo

                        Forming Quiz Teams                                                       dp + bitmasking Problem Link   #include <iostream> #include <cstdio> #include <math.h> #include <cstring> #define sf(a) scanf("%d", &a) #define REP(i, n) for(int i = 0; i < n; i++) using namespace std; int n, posx, posy; char name[21]; double dist[17][17]; double dp[1 << 16]; int xy[17][2]; double solve(int bits) {     if(dp[bits] != -1)         return dp[bits];     if(bits == (1 << n) - 1)         return 0;     double ans = 1 << 30; // random big number     for(int i = 0; i < n; i++)     {         if(!(bits & (1 << i)))         {             for(int j = i + 1; j < n; j++)             {                 if(!(bits & (1 << j)))                 {                     ans = min(ans, solve(bits | (1 << i) | (1 << j)) +

                                      Jogging Trails                                                        bitwise DP  Problem Link #include <iostream> #include <cstring> #include <climits> #include <cstdio> #define INF INT_MAX #define sf(a) scanf("%d", &a) #define set(b, pos) ( b | (1 << pos) ) #define off(b, pos) ( b & ~( 1 << pos) ) #define test(b, pos) (b & (1 << pos) ) using namespace std; int v, e, st, en, wt, weight, bits; int graph[15][15]; int deg[15]; //stores degree of a node int memo[1 << 15]; int solve(int bits) {     if(memo[bits] >= 0)         return memo[bits];     int ans = INF;     int b;     for(int i = 0; i < v; i++)     {         for(int j = i + 1; j < v; j++)         {             if(test(bits, i) && test(bits, j))             {                 b = bits;                 b = off(b, i);            

                                 Twenty Questions                                                  DP + bitmasking Problem Link #include <iostream> #include <cstring> #include <string> #include <algorithm> using namespace std; int F[128]; //feature set int dp[1 << 11][1 << 11]; //set of question and answer //denotes bitmask of question and answer int n, m; int solve(int Q, int A) {     if(dp[Q][A] != -1)         return dp[Q][A];     int nObjects = 0; //number of objects remaining after asking Q     for(int i = 0; i < n; i++)     {         if((F[i] & Q) == A)             nObjects++;     }     if(nObjects <= 1)     {         return dp[Q][A] = 0;     }     int nQuestions = m + 1;     //one by one ask each question and take the min number o question required to identify each object     for(int i = 0; i < m; i++)     {         if((Q & (1 << i)) == 0)

                                  Pebble Solitaire                                                 DP + bitmasking Problem Link #include <stdio.h> #include <string.h> #define min(a,b) a > b ? b: a void on( int &mask ,int pos){      mask |= ( 1 << pos) ; } void  off(int &mask,int pos){     mask = mask & ~( 1 << pos) ; } bool check( int mask , int pos ){      return bool( mask & ( 1 << pos) ) ; } int dp[ 1<<12 + 5 ] ; int solve( int mask) {     int &ret = dp[mask];     if( ret != -1 ) return ret;     ret = __builtin_popcount(mask);     for( int pos = 0 ; pos < 12 ; pos ++ )     {          if( pos < 10 && check(mask,pos) && check(mask,pos+1) && !check(mask,pos+2)){               int newmask = mask;               off(newmask,pos) , off( newmask , pos +1 ) , on(newmask,pos+2);               ret = min( ret , solve(newmask));          }