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

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

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

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

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

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

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

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

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

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

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

                            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]);     } ...

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

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

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

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

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