SPOJ

Problem Link #include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; const long long N = 100005, INF = 2e9; long long ans[N], d[N]; long long B[N]; int bsearch(int x, int n) { int low = 1; int high = n; int mid, res; res = 0; while(low <= high) { mid = (low + high) / 2; if(ans[mid] <= x) { res = mid; low = mid + 1; } else { high = mid - 1; } } return res; } int main() { int t, n, q, x; std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; B[0] = 1;     for (int i = 1; i <= 60; i++)         B[i] = B[i - 1] + B[i - 1]; while(t--) { cin >> n >> q; long long a[n]; for(int i = 1; i <= n; i++) { cin >> a[i]; } sort(a + 1, a + n + 1); for(int i = 1; i <= n; i++) { if(d[i - 1] > a[i]) { ans[i] = ans[i - 1]; ...

Problem Link #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int t, n, q, l, r; vector<int> v; string s; std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> t; while(t--) { cin >> n >> q; cin >> s; v.clear(); for(int i = 0; i < n - 2; i++) { if(s[i] == s[i + 1] || s[i + 1] == s[i + 2] || s[i] == s[i + 2]) { v.push_back(i); } } while(q--) { cin >> l >> r; l--; r--; if(r - l + 1 < 3) { cout << "NO\n"; continue; } auto x = upper_bound(v.begin(), v.end(), l - 1);     if(x == v.end())     {     cout << "NO\n";     }     else if(*x >= l && *x + 2 <= r)       cout << "YES" << endl;       else       co...

Problem Link #include <iostream> #include <vector> using namespace std; int main() { int n, q, l, r; cin >> n >> q; long arr[n]; vector<long> b[n]; for(int i = 0; i < n; i++) { cin >> arr[i]; long temp = arr[i]; int x = 0; for(int j = 0; j < 32; j++) { b[i].push_back(0); } while(temp) { b[i][x] = temp % 2; temp /= 2; x++; } } for(int i = 1; i < n; i++) { for(int j = 0; j < 32; j++) { b[i][j] += b[i - 1][j]; } } while(q--) { cin >> l >> r; l --; r--; long res = 0; for(int i = 0; i < 31; i++) { int setBits, unsetBits; if(l > 0) { setBits = b[r][i] - b[l - 1][i]; unsetBits = r - l + 1 - setBits; } else { setBits = b[r][i]; unsetBits = r - l + 1 - setBits; } if(setBits < unsetBits) { res |= (1 << i); } } cout << res << endl;...

Problem Link #include <iostream> using namespace std; int main() { int t, n, odd, even; cin >> t; while(t--) { cin >> n; int i,arr[n],freq[1100001]={0}; long res = 0; odd = even = 0; for(int i = 0; i < n; i++) { cin >> arr[i]; freq[arr[i]]++; } for(int i = 0; i < n; i++) { if(arr[i] & 1) { odd++; } else { even++; } } for(int i = 0; i < n; i++) { if(arr[i] % 2) { res += odd; } else { res += even; } res -= freq[arr[i] ^ 2]; res -= freq[arr[i]]; } cout << res / 2 << endl; } }

Problem Link #include <iostream> using namespace std; int main() { int t, n, k; cin >> t; while(t--) { cin >> n >> k; if(n == 1) { cout << k << endl; continue; } if(k == 1) { for(int j = 0; j < n; j++) { cout << "1 "; } cout << endl; continue; } if(k == 2) { cout << "2 "; for(int j = 1; j < n; j++) { cout << "1 "; } cout << endl; continue; } if(k == 3) { if(n % 2) { cout << "3 "; for(int j = 1; j < n; j++) { cout << "1 "; } cout << endl; } else { cout << "2 "; for(int j = 1; j < n; j++) { cout << "1 "; } cout << endl; } continue; } else { long res = 1; while(res <= k) { res = ...

Problem Link #include <iostream> #include <vector> #include <set> using namespace std; const int N = 10001; vector<int> graph[N]; set<int> res; int parent[N], dis[N], low[N]; bool visited[N]; int n, m, u, v, value; void dfs(int source) {         int dest, children;         children = 0;         visited[source] = true;         dis[source] = low[source] = ++value;         for(int i = 0; i < graph[source].size(); i++)         {                 dest = graph[source][i];                 if(!visited[dest])                 {                         children++;                       ...

Problem Link #include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> v[701]; vector<pair<int, int>> res; int in[701], low[701], parent[701]; bool visited[701]; int n, m, a, b, test; int value = 0; bool isBridge; void dfs(int s) { visited[s] = true; int d; low[s] = in[s] = ++value; for(int i = 0; i < v[s].size(); i++) { d = v[s][i]; if(!visited[d]) { parent[d] = s; dfs(d); low[s] = min(low[s], low[d]); if(low[d] > in[s]) { isBridge = true; if(s < d) { res.push_back(make_pair(s, d)); } else res.push_back(make_pair(d, s)); } } else if(d != parent[s]) { low[s] = min(low[s], in[d]); } } } int main() { cin >> test; for(int i = 1; i <= test; i++) { isBridge = false; value = 0; for(int j = 0; j <= 700; j++) { visited[j] = false; parent[j] = j; v[j].clear(...

Problem Link #include <iostream> #include <map> #include <vector> using namespace std; struct edge {      int s, d;      double c; }; map<string, int> nodes; double v[50]; vector<edge> e; bool bellmanFord(int s, int n) {      v[s] = 1;      int source, dest;      double rate;      for(int j = 0; j < n - 1; j++)      {           for(int i = 0; i < e.size(); i++)           {                source = e[i].s;                dest = e[i].d;                rate = e[i].c;                if(v[dest] < v[source] * rate)                {            ...

Problem Link Ref Link #include <iostream> #include <vector> using namespace std; struct node {     int vol,profit, p; }; int main() {     int t, n, vmax;     long dp[32001][61];     node parent[62];     vector<node> child[62];     cin >> t;     while(t--)     {         cin >> vmax >> n;               for(int i = 0; i < 62; i++)         {             parent[i].vol = -1;             child[i].clear();         }         for(int i = 1; i <= n; i++)         {             node temp;             cin >> temp.vol >> temp.profit >> temp.p;           ...

Problem Link Reference Link #include <iostream> #include <cmath> using namespace std; long INF = 9999999; int main() {     int n, x, y;     int assistant[10000], captain[10000];     long dp[2][5001];     cin >> n;     for (int i = 0; i < n; ++i)     {         cin >> captain[i] >> assistant[i];     }     for (int i = 0; i < 2; ++i)     {         for (int j = 0; j <= n / 2; ++j)         {             dp[i][j] = INF;         }     }     dp[1][1] = assistant[0];     for (int i = 2; i <= n; ++i)     {         int m = min(i, n / 2);         int index = i % 2;         // if we have to make 0 extra assistant then last one h...

Problem Link Reference #include <iostream> using namespace std; long long int dp[40][40]; int main() { int d, n, k, pos; cin >> d; char arr[40]; while(d) { cin >> n >> k; for(int i = 0; i < 2 * n; i++) { arr[i] = '?'; } arr[2 * n] = '\0'; for(int i = 0; i < k; i++) { cin >> pos; arr[pos - 1] = '['; } n = 2 * n; for(int i = 0; i <= n; i++) { for(int j = 0; j <= n; j++) { if(i == 0 && j == 0) { dp[i][j] = 1; } else if((i == 0 && j != 0)) { dp[i][j] = 0; } else { if(arr[i - 1] == '?') { dp[i][j] = dp[i - 1][j + 1] + dp[i - 1][j - 1]; } else { dp[i][j] = dp[i - 1][j - 1]; } } } } cout << dp[n][0] << endl; d--; } return 0; }

Problem Link #include <iostream> using namespace std; long long int dp[40][40]; int findPermutation(char s[], int i, int j) { if(s[i] == '?' &&  s[j] == ']') return 1; if(s[j] == '?' && s[i] == '[') { return 1; } if((s[i] == '[' && s[j] == ']')) return 1; if(s[i] == '?' && s[j] == '?') return 1; return 0; } int main() { int d, n, k, pos; cin >> d; char arr[40]; while(d) { cin >> n >> k; for(int i = 0; i < 40; i++) { for(int j = 0; j < 40; j++) { dp[i][j] = 0; if(i > j){ dp[i][j] = 1; } } } for(int i = 0; i < 2 * n; i++) { arr[i] = '?'; } arr[2 * n] = '\0'; for(int i = 0; i < k; i++) { cin >> pos; arr[pos - 1] = '['; } n = 2 *...

Problem Link #include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; struct Card { int color, value; }; int bsearch(vector<int> v, int low, int high, int value) { int result = -1; while(low <= high) { int mid = (low + high) / 2; if(v[mid] < value) { result = mid; low = mid + 1; } else { high = mid - 1; } } return result; } int findLis(vector<int> lis, int totalCards) { vector<int> v; v.push_back(lis[0]); for(int i = 1; i < totalCards; i++) { int index = bsearch(v, 0, v.size() - 1, lis[i]); if(index + 1 == v.size()) { v.push_back(lis[i]); } v[index + 1] = lis[i]; } return v.size(); } int main() { int c, n, totalCards, i, maxLength; vector<int> per; cin >> c >> n; totalCards = c * n; Card arr[totalCards]; vector<int> lis; for(i = 0; i < totalCards; i...

Problem Link #include<iostream> #include <vector> #include <algorithm> using namespace std; struct box { int w, h; }; bool customSort(box a, box b) { if(a.w == b.w) { return a.h < b.h; } return a.w > b.w; } vector<box> v; int bsearch(int w, int h, int low, int high) { int mid; int ans = 100000; while(low <= high) { mid = (low + high) / 2; int width = v[mid].w; int height = v[mid].h; if(height > h) { ans = mid; high = mid - 1; } else { low = mid + 1; } } return ans; } int main() { int t, m, w, h, n, i; cin >> t; while(t--) { cin >> m; box arr[m]; n = 1; v.clear(); for(i = 0; i < m; i++) { cin >> arr[i].w >> arr[i].h; } sort(arr, arr + m, customSort); i = 1; v.push_back(arr[0]); while(i < m) { int index = bsearch(arr[i].w, arr[i].h, 0, v.size() - 1); if(index <= m - 1) ...

Problem Link #include <iostream> using namespace std; int main() { int t, n, k; int arr[1001]; bool dp[1001][1024]; cin >> t; while(t--) { cin >> n >> k; for(int i = 0; i < n; i++) { cin >> arr[i]; } for(int i = 0; i <= n; i++) { for(int j = 0; j <= 1023; j++) { dp[i][j] = false; if(j == 0) { dp[i][j] = true; } else if(i > 0) { dp[i][j] = dp[i - 1][j] || dp[i - 1][j ^ arr[i - 1]]; } } } int maxVal = k; for(int i = 0; i <= 1023; i++) { if(dp[n][i]) { maxVal = max(maxVal, k ^ i); } } cout << maxVal << endl; } return 0; }

Problem Link #include <iostream> #include <climits> using namespace std; int h[501], k[501]; const int maxVal  = 99999; int main() { int t, n; cin >> t; while(t--) { cin >> n; int dp[1001][n + 1]; for(int i = 0; i < n; i++) { cin >> h[i]; h[i] = 2 * h[i]; } for(int i = 0; i < n; i++) { cin >> k[i]; } for(int i = 0; i <= 1000; i++) { for(int j = 0; j <= n; j++) { if(i == 0) { dp[i][j] = 0; continue; } else if(j == 0) { dp[i][j] = maxVal; } else { if(k[j - 1] > i) { dp[i][j] = dp[i][j - 1]; } else dp[i][j] = min(dp[i][j - 1], dp[i - k[j - 1]][j] + 1); } } } long minVal = 0; for(int i = 0; i < n; i++) { minVal += dp[h[i]][n]; } cout << minVal << endl; } return 0; }

Problem Link #include <iostream> #include<cmath> #define max(a,b) (a>b ? a : b) #define min(a,b) (a<b ? a : b) using namespace std; long long int leftdp[1000004][2],rightdp[1000004][2], dish[1000004]; int main() { int t, n; cin >> t; while(t--) { cin >> n; for(int i = 0; i < n; i++) { cin >> dish[i]; } leftdp[0][0] = dish[0]; leftdp[0][1] = dish[0]; for(int i = 1; i < n; i++) { leftdp[i][0] = max(leftdp[i - 1][0], 0) + dish[i]; leftdp[i][1] = min(leftdp[i - 1][1], 0) + dish[i]; } rightdp[n - 1][0] = dish[n - 1]; rightdp[n - 1][1] = dish[n - 1]; for(int i = n - 2; i >= 0; i--) { rightdp[i][0] = max(rightdp[i + 1][0], 0) + dish[i]; rightdp[i][1] = min(rightdp[i + 1][1], 0) + dish[i]; } long long int ans = 0; for(int i = 0; i < n-1; i++) {     ans = max(ans,abs(leftdp[i][0] - rightdp[i+1][1]));     ans = max(ans,abs(left...

Problem Link #include <iostream> #include <vector> using namespace std; const int MAXN = 3000; const int MAXPRICE = 1010; long long dp[MAXN][MAXPRICE], albumGreatness[MAXN]; vector<pair<int, int> > album[MAXN]; int main() { int n, m, totalPrice, index; cin >> n >> m  >> totalPrice; int greatness, price, a, albumPrice[m]; for(int i= 0; i < n; i++) { cin >> a >> price >> greatness; //greatness and price of individual song album[a].push_back(make_pair(price, greatness)); albumGreatness[a] += greatness; } for(int i = 1; i <= m; i++) { cin >> albumPrice[i]; } index = 0; for(int i = 1; i <= m; i++) { for(auto songs : album[i]) { index++; for(price = 1; price <= totalPrice; price++) { dp[index][price] = max(dp[index - 1][price], (price >= songs.first) ? dp[index - 1][price - songs.first] + songs.second : 0); } } ...

Problem Link #include <iostream> #include <algorithm> using namespace std; int main() { int t, n, index, count; bool isPossible; cin >> t; while(t--) { cin >> n; pair<int, int> arr[n]; int b[n]; int result[n]; index = 0; isPossible  = true; for(int i = 0; i < n; i++) { cin >> arr[i].first; arr[i].second = i; } sort(arr, arr + n); /* We can have atmost floor(n/2) same colors and still colors of marker and cap can be                             different. If number of same colors > floor(n/2) then atleast one pen will have same                            colored cap. So we are checking if color at position i and i + (n + 1) / 2 position is same                        or no...

Problem Link #include<iostream> #include <algorithm> #include <cstring> using namespace std; int freq[26]; int main() { int t, len, maxFreq, diff, diffa, diffb, ans; string s; cin >> t; while(t--) { cin >> s; memset(freq, 0, sizeof(freq)); len = s.length(); for(int i = 0; i < len; i++) { freq[s[i] - 'A']++; } sort(freq, freq + 26, greater<int>()); ans = len; for(int i = 1; i <= 26; i++) { if(len % i != 0) continue; maxFreq = len / i; diffa = diffb = 0; for(int j = 0; j < i; j++) { if(freq[j] == 0) break; diff = freq[j] - maxFreq; if(diff > 0) { diffa += diff; } else { diffb -= diff; } } ans = min(ans, max(diffa, diffb)); } cout << ans << endl; } return 0; }

Problem Link #include <iostream> using namespace std; int main() { int n, t, dish; long long maxDish; cin >> t; while(t--) { cin >> n; maxDish = 0; while(n--) { cin >> dish; maxDish += (dish - 1); } cout << maxDish + 1 << endl; } return 0; }

Problem Link #include <iostream> #include <vector> #include <cstdio> using namespace std; const int N = 100001; int arr[N]; vector<pair<int, int> > range; int preK[N]; // ith position store number of values equal to k till index i int preK1[N]; // ith position store number of values equal to k + 1 till index i void resetArray() { range.clear();     for(int i = 0; i < N; i++)     {         arr[i] = 0;         preK[i] = preK1[i] = 0;     } } int main() {     int t, n, k, l, r, count, maxCount, maxN, i;     cin >> t;     while(t--)     {         scanf("%d%d", &n,&k);         count = maxCount = maxN = 0;         resetArray();         for(i = 1; i <= n; i++)         {         ...

#include <iostream> #include <vector> #include <cmath> using namespace std ; int pre[ 2005 ][ 2005 ]; int fre[ 2005 ][ 2005 ]; int arr[ 2005 ]; int bsearch ( int i, int j, int k) { int len = j - i + 1 ; int m = ceil (( double )k / len); int mid, pos; m = ceil (( double )k / m); int low = 1 ; int high = 2000 ; while (low < high) { mid = (low + high) / 2 ; pos = (pre[mid][j] - pre[mid][i - 1 ]); if (pos < m) { low = mid + 1 ; } else { high = mid; } } if (low == high - 1 ) { pos = (pre[low][j] - pre[low][i - 1 ]); if (pos >= m) { high = low; } } return high; } void resetArray () { for ( int i = 0 ; i < 2005 ; i++) { arr[i] = 0 ; for ( int j ...

Problem Link #include <iostream> #include <vector> #include <queue> #include <cstdio> using namespace std ; const long INF = 9999999 ; void dijkstra ( int source, long dist[], vector< pair< int , long > > maze[]) { priority_queue< pair< long , int > > pq; dist[source] = 0 ; pq. push ( make_pair ( 0 , source)); int neighbor; long t; while (!pq. empty ()) { int s = pq. top (). second ; pq. pop (); for ( int i = 0 ; i < maze[s]. size (); i++) { neighbor = maze[s][i]. first ; t = maze[s][i]. second ; if (dist[neighbor] > dist[s] + t) { dist[neighbor] = dist[s] + t; pq. push ( make_pair (dist[neighbor], neighbor)); } } } } int main () { int n, exitCell, timer, edges, u, v, t; ...

Problem Link #include <iostream> #include <vector> using namespace std; bool isParadox; int stmt[101]; // 0 if stmt[i] is false, 1 if true,  -1 if not yet decided int p[101]; // store root of a component void dfs(int s, vector<pair<int,int> > graph[], int root) {       p[s] = root;     for(int i = 0; i < graph[s].size(); i++)     {         int v = graph[s][i].first;         int c = graph[s][i].second;         if(stmt[v] == -1)         {             //if stmt s is true then whatever it says about other stmt is true             //else whatever it says is false. so we have to take its complement             stmt[v] = stmt[s] == 1 ? c : 1 - c;                       dfs(v, graph, ...