- Misa's Love -
- Solution :
Let s_1, s_2, ..., s_n be the prefixes of string S where |S| is equal to n and s_i represents prefix of length i. A function f(x) is defined as the count of string x as a substring in the string S. As every i_{th} prefix will be the prefix of j_{th} prefix where j >= i. So, we can say that f(s_1) >= f(s_2) ... f(s_n). Therefore the maximum time occurring nonempty prefix is the s_1 and answer to the problem is f(s_1). Complexity - O(n) Tags - Observation, Ad-hoc
- C++ Code :
#include <bits/stdc++.h> #define int long long #define end "\n" using namespace std; int32_t main() { string s; cin >> s; int n = s.size(); assert(1 <= n && n <= 100); for(int i=0;i<n;i++) assert(s[i] >= 'a' && s[i] <= 'z'); int count = 0; for(int i=0;i<n;i++) { if(s[i] == s[0]) count++; } cout << count << endl; }
- L's Meal -
- Solution :
This problem is similar to the inversion count problem. Let assume in the given string S, the character at i_{th} index is c and the character at j_{th} index is p for i < j, the pair (p,c) is called an inversion. In this problem, you have to minimize the number of (p,c) pair of inversions. If we swap the first occurrence of c and last occurrence of p then we decrease the maximum inversions as they are both the maximum contributors. However, there is a corner case. We don't need to swap if the last occurrence of p is before the first occurrence of c as this string initially has zero inversions which is minimum possible. Complexity - O(n) Tags - Observation, Inversion Count, Simple Math
- C++ Code :
#include <bits/stdc++.h> #define int long long #define endl "\n" using namespace std; int32_t main() { string s; cin >> s; int n = s.size(); for(int i=0;i<n;i++) assert(s[i] == 'p' || s[i] == 'c'); int c1,c2; for(int i=0;i<n;i++) { if(s[i] == 'c') { c1 = i; break; } } for(int i=n-1;i>=0;i--) { if(s[i] == 'p') { c2 = i; break; } } if(c1 < c2) swap(s[c1],s[c2]); int cnt = 0; int ans = 0; for(int i=0;i<n;i++) { if(s[i] == 'c') cnt++; else ans += cnt; } cnt = 0; for(int i=n-1;i>=0;i--) { if(s[i] == 'p') cnt++; else ans += cnt; } cout << ans << endl; }
- Watari queries -
- Solution :
This problem is based completely on observation and pigeon hall principal. First of all, there is always possible to find a non-empty subset in some range [l,r] for which some of its elements is divisible by (r-l+1) where l <= r and not only subset even a subarray. To prove this let consider an array A of integers of size n. If we can prove that there always exists a subarray for which some of its element is divisible by n irrespective of elements of the array then we can solve the original problem. Make a prefix sum array B of A. If we take the modulus of every prefix sum under n then there are two possibilities. First, we get all the remainder unique. There is n different possibilities from (0,1,2,...,n-1). As in this case, we should get a zero that means that the prefix sum is divisible by n. Hence, a subarray exist. Second, we get at least one remainder that occurs more than once since our possible choices of the remainder are 1 to n-1 which should belong to n integers. Let x (x >= 0 && x < n) be the remainder which occurs more than once at index i and j(i<j). The sum of subarray a_{i+1}, a_{i+2}, ..., a_j under modulo n will be equal to b_j - b_i. Since b_i = b_j, the sum of the given subarray is 0 under modulo n and hence is divisible by n. Complexity - O(q) Tags - Observation, Ad-hoc, Simple Math, Pigeon Hall Principle.- C++ Code :
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, q, a, t, l, r, x; cin >> n >> q; assert(n >= 1 && n <= 100000); assert(q >= 1 && q <= 100000); for (int i = 0; i < n; ++i) { cin >> a; assert(a >= 1 && a <= 1000000000); } while (q--) { cin >> t; assert(t == 1 || t == 2); if (t == 1) { cin >> l >> r >> x; assert(l >= 1 && l <=r && l <= n); assert(r >= 1 && r >= l && r <= n); assert(x >= 1 && x <= 1000000000); } else { cin >> l >> r; assert(l >= 1 && l <=r && l <= n); assert(r >= 1 && r >= l && r <= n); cout << "YES\n"; } } return 0; }- Shinigami Eyes -
- Solution :
The possible value of k is 1, 2, 4 or 8. Let's solve the problem for each of values independently. for k = 1, the minimum number of deletion is zero as any number is divisible by 1. for k = 2, the number is divisible by 2 if it's the last digit is divisible by 2. Since we need to minimize the number of deletions, we have to find from last the first digit which is divisible by 2. If it is found at index i we need to delete all digits with index > i. This will be the minimum possible deletion for k = 4, the number is divisible by 4 if it's last two digits is divisible by 4 i.e belongs to the set {00, 04, ..., 96}. For each element in the set, we need to find whether it is present in the number as a subsequence. If the two digits of the set are found at index i and j(i<j), we should be deleting all the digits with an index between i and j and the index is greater than j. This way our resulting number will be divisible by 4. To minimize the number of deletions, we need to find our subsequence from last. It will take O(n) to check for each element in the set. Thus, total complexity will be O(n*(element in the set)). Besides, we need to handle cases when the number can be reduced to a single digit after deletions. For divisibility by 4, the number should be reduced in either of 0, 4, 8. for k = 8, we similarly need to check for the set {000, 008, 016, ..., 992}. Besides we also need to handle the cases when the number can be reduced to the length of either 2 or 1. For length 2, we need to find the subsequence of {00, 08, 16, ..., 96} and delete all the remaining digits. For length 1, we are required to find 0, 8 in the number and delete all remaining digits. We can avoid these checking if we append 0 and 00 before the number for k equal to 4 and 8 respectively. If it is impossible to make the number divisible by k in at most n-1 deletions then answer is -1. Complexity - Overall complexity of the solution is O(n*m) where n is the length of string and m is ceil(1000/8). Tags - Ad-hoc, Simple Math, Brute Force.
- C++ Code :
#include <bits/stdc++.h> #define int long long #define endl "\n" using namespace std; int32_t main() { int t; cin >> t; int ans,id; assert(t >= 1 && t <= 100); while(t--) { int n,k; cin >> n >> k; string s; cin >> s; if(s.size() == 1 && s[0] == '0') { cout << 0 << endl; continue; } assert(s.size() == n); assert(s[0] != '0'); for(int i=0;i<n;i++) assert(s[i] >= '0' && s[i] <= '9'); assert(n >= 1 && n <= 5000); assert(k == 1 || k == 2 || k == 4 || k == 8); if(k == 1) cout << 0 << endl; else if(k == 2) { ans = -1; for(int i=n-1;i>=0;i--) { int temp = s[i] - '0'; if(temp%2 == 0) { ans = i; break; } } if(ans == -1) cout << -1 << endl; else cout << n - ans - 1 << endl; } else if(k == 4) { ans = -1; id = -1; for(int i=96;i>=0;i-=4) { int c1,c2; c1 = i%10; c2 = i/10; for(int j=n-1;j>=0;j--) { int temp = s[j] - '0'; if(temp == c1) { for(int k=j-1;k>=0;k--) { temp = s[k] - '0'; if(temp == c2) { if(ans < k) { ans = k; id = i; } break; } } break; } } } if(ans == -1) { if(s.find('0') != string::npos) cout << n-1 << endl; else if(s.find('4') != string::npos) cout << n-1 << endl; else if(s.find('8') != string::npos) cout << n-1 << endl; else cout << -1 << endl; } else cout << n - ans - 2 << endl; } else if(k == 8) { ans = -1; id = -1; for(int i=992;i>=0;i-=8) { int c1,c2,c3; c1 = i%10; c2 = (i/10)%10; c3 = (i/100)%10; for(int j=n-1;j>=0;j--) { int temp = s[j] - '0'; if(temp == c1) { for(int k=j-1;k>=0;k--) { temp = s[k] - '0'; if(temp == c2) { for(int l=k-1;l>=0;l--) { temp = s[l] - '0'; if(temp == c3) { if(ans < l) { ans = l; id = i; } break; } } break; } } break; } } } if(ans == -1) { for(int i=96;i>=0;i-=8) { int c1,c2; c1 = i%10; c2 = i/10; for(int j=n-1;j>=0;j--) { int temp = s[j] - '0'; if(temp == c1) { for(int k=j-1;k>=0;k--) { temp = s[k] - '0'; if(temp == c2) { cout << n - 2 << endl; ans = 0; break; } } break; } } if(ans == 0) break; } if(ans == -1) { if(s.find('0') != string::npos) cout << n-1 << endl; else if(s.find('8') != string::npos) cout << n-1 << endl; else cout << -1 << endl; } } else cout << n - ans - 3 << endl; } } }- Apple and Ryuk -
- Solution :
If we simply run a brute force then the solution takes O(n^2). The optimize solution uses the fast Fourier transformation. In the given problem, we are required to find all pairs of ones such that the distance between them is d and we have to perform this for every d from 0 to n-1. We have to represent our problem in some polynomial form. The distance between two ones is defined as abs(i-j) where i and j are the respective indices of the ones. We can represent this in polynomial form like - We define two polynomial: A(x) = a_1x^1 + a_2x^2 + ... + a_nx^n, where a_i is 1 if ith position contains an apple and 0 if the box is empty. B(x) = b_1x^-1 + b_2x^-2 + ... + b_nx^-n, where b_i is 1 if ith position contains an apple and 0 if the box is empty If we multiply these two polynomials, the power of x represents the value of d and the respective coefficients represent the number of times the corresponding d occurs. This is because the product of a_ix^i and b_jx^-j accounts for the pair of ones at index i and j. So, after multiplication, we have to just find out the coefficients from 0 to n-1(which is the highest power of polynomial after multiplication). This polynomial multiplication can be achieved in O(nlgn) time by fft. Complexity - O(nlogn) Tags - Fast Fourier Transformation
- C++ Code :
#include <bits/stdc++.h> const double PI = 3.141592653589793238460; using namespace std; typedef std::complex<double> Complex; typedef std::valarray<Complex> CArray; void fft(CArray& x) { const size_t N = x.size(); if (N <= 1) return; CArray even = x[std::slice(0, N/2, 2)]; CArray odd = x[std::slice(1, N/2, 2)]; fft(even); fft(odd); for (size_t k = 0; k < N/2; ++k) { Complex t = std::polar(1.0, -2 * PI * k / N) * odd[k]; x[k ] = even[k] + t; x[k+N/2] = even[k] - t; } } void ifft(CArray& x) { x = x.apply(std::conj); fft( x ); x = x.apply(std::conj); x /= x.size(); } int32_t main() { int N; cin >> N; N++; assert(N >= 2 && N <=100001); string s; cin >> s; for(int i=0;i<N-1;i++) assert(s[i] == '1' || s[i] == '0'); int padded_size = 2 * (1 << int(ceil(log2(N)))); vector<Complex> num1_vec(padded_size - N, 0.0), num2_vec(padded_size - N, 0.0); num1_vec.push_back(0.0); num2_vec.push_back(0.0); for(int i = 1; i < N; i++) { if(s[i-1] == '1') num1_vec.push_back(1.0); else num1_vec.push_back(0.0); } reverse(s.begin(),s.end()); for(int i = 1; i < N; i++) { if(s[i-1] == '1') num2_vec.push_back(1.0); else num2_vec.push_back(0.0); } CArray data1(padded_size); for(int i = 0; i < padded_size; i++) data1[i] = num1_vec[i]; CArray data2(padded_size); for(int i = 0; i < padded_size; i++) data2[i] = num2_vec[i]; fft(data1); fft(data2); CArray data3(padded_size); data3 = data1 * data2; ifft(data3); vector<long long> ans; for (int i = 0; i < padded_size - 1; i++) ans.push_back((long long)(round(data3[i].real()))); for(int i = padded_size - N; i < padded_size - 1; i++) cout << ans[i] << " "; cout << endl; }
- Evil Group -
- Solution :
Let start with some observation. you are given an array of positive integers. Let's define function f(i,j) as the gcd of all the numbers from range from i to j. As if some subarray has f(x,y) equal to 1 then all the subarray which completely contains this subarray also has f(x',y') is equal to 1. Let define another two terms left active point and right active point. For each index i of the array, its right active point j is the index of the last element of smallest subarray starting at i and having f(i, j) = 1. If there is no such subarray, right active point for i is n. Similarly, for each index i of the array, its left active point j is the first index of smallest subarray ending at i and having f(j, i) = 1. If no such subarray exists, the left active point for i is -1. We can precompute this information for every index by using a Segment tree or Fenwick tree. For processing the query, as queries are offline(without updates), we can use standard Mo's algorithm. Let suppose, we know the answer to some range and we want to find out the answer for another range. To convert one range into some another range we require four types of operation. Add to the range from left - if we add an element to the left in the range then there are two possibilities. First, the right active point of the subarray which starts from the point which we want to add into the range is greater than the right point of the range, the answer will be the same. In the second case if it lies within the range then answer will be incremented by (r-x+1) where r is the right end point of range and x is the position of the right active point and also r >= x. Remove to the range from left - if we remove the element to the left from the range then there are two possibilities. First, the right active point of the subarray which starts from the point which we want to remove from the range is greater than the right point of the range, the answer will be the same. In the second case if it lies within the range then answer will be decremented by (r-x+1) where r is the right end point of range and x is the position of the right active point and also r >= x. Add to the range from right - if we add an element to the right in the range then there are two possibilities. First, the left active point of the subarray which ends at the point which we want to add into the range is lesser than the left point of the range, the answer will be the same. In the second case if it lies within the range then answer will be incremented by (x-l+1) where l is left end point of range and x is the position of the left active point and also l <= x. Remove to the range from right - if we remove the element to the right from the range then there are two possibilities. First, the left active point of the subarray which ends at the point which we want to remove from the range is lesser than the left point of the range, the answer will be same. In the second case if it lies within the range then answer will be decremented by (x-l+1) where l is left end point of range and x is the position of the left active point and also l <= x. By using standard Mo's algorithm we can answer all queries in offline mode. Complexity - O(n*sqrt(n)) Tags - Data Structure, Binary Search, Segment Tree, Mo's Algorithm.
- C++ Code :
#include<bits/stdc++.h> #define int long long #define endl "\n" using namespace std; int a[100010]; int tree[400010]; int answers[100010]; int cnt1[100010]; int cnt2[100010]; int BLOCK_SIZE; pair< pair<int, int>, int> queries[100500]; int ans; void build(int node, int start, int end) { if(start == end) tree[node] = a[start]; else { int mid = (start + end) / 2; build(2*node, start, mid); build(2*node+1, mid+1, end); tree[node] = __gcd(tree[2*node],tree[2*node+1]); } } int query(int node, int start, int end, int l, int r) { if(r < start or end < l) return 0; if(l <= start and end <= r) return tree[node]; int mid = (start + end) / 2; int p1 = query(2*node, start, mid, l, r); int p2 = query(2*node+1, mid+1, end, l, r); return __gcd(p1,p2); } inline bool mo_cmp(const pair< pair<int, int>, int> &x, const pair< pair<int, int>, int> &y) { int block_x = x.first.first / BLOCK_SIZE; int block_y = y.first.first / BLOCK_SIZE; if(block_x != block_y) return block_x < block_y; return x.first.second < y.first.second; } int32_t main() { int n; cin >> n; assert(n >= 1 && n <= 100000); BLOCK_SIZE = static_cast<int>(sqrt(n)); for(int i=0;i<n;i++) { cin >> a[i]; assert(a[i] >= 1 && a[i] <= 1e6); } build(1,0,n-1); for(int i=0;i<n;i++) { int l = i; int h = n-1; int ans = n; while(l <= h) { int mid = (l+h)/2; if(query(1,0,n-1,i,mid) == 1) { ans = mid; h = mid - 1; } else l = mid + 1; } cnt1[i] = ans; } for(int i=n-1;i>=0;i--) { int l = 0; int h = i; int ans = -1; while(l <= h) { int mid = (l+h)/2; if(query(1,0,n-1,mid,i) == 1) { ans = mid; l = mid + 1; } else h = mid - 1; } cnt2[i] = ans; } int q; cin >> q; assert(q >= 1 && q <= 50000); for(int i=0;i<q;i++) { cin >> queries[i].first.first >> queries[i].first.second; assert(queries[i].first.first >= 1 && queries[i].first.first <= n); assert(queries[i].first.second >= 1 && queries[i].first.second <= n); queries[i].second = i; } sort(queries, queries + q, mo_cmp); int mo_left = 0, mo_right = -1; ans = 0; for(int i=0;i<q;i++) { int left = queries[i].first.first-1; int right = queries[i].first.second-1; while(mo_right < right) { mo_right++; if(cnt2[mo_right] >= mo_left) ans += (cnt2[mo_right]-mo_left+1); } while(mo_right > right) { if(cnt2[mo_right] >= mo_left) ans -= (cnt2[mo_right]-mo_left+1); mo_right--; } while(mo_left < left) { if(cnt1[mo_left] <= mo_right) ans -= (mo_right-cnt1[mo_left]+1); mo_left++; } while(mo_left > left) { mo_left--; if(cnt1[mo_left] <= mo_right) ans += (mo_right-cnt1[mo_left]+1); } answers[queries[i].second] = ans; } for(int i=0;i<q;i++) cout << answers[i] << "\n"; return 0; }
Asked by: rishup132 on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.