Codeforces.1359E Modular Stability

1.Problem
https://codeforces.com/contest/1359/problem/E

2.Idea
a1 must be a divisor of a2..aN.

3.Source

 Int fact[N], invfact[N], inv[N];  
 void init()  
 {  
      fact[0] = 1;  
      for (int i = 1; i < N; i++) {  
           fact[i] = fact[i - 1] * i % MOD;  
      }  
      inv[1] = 1;  
      for (int i = 2; i < N; i++) {  
           inv[i] = -inv[MOD%i] * (MOD / i) % MOD;  
           if (inv[i] < 0) inv[i] += MOD;  
      }  
      invfact[0] = 1;  
      for (int i = 1; i < N; i++) {  
           invfact[i] = invfact[i - 1] * inv[i] % MOD;  
      }  
 }  
 Int nCk(Int n, Int k)  
 {  
      return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD;  
 }  
 Int nPk(Int n, Int k)  
 {  
      return fact[n] * invfact[n - k] % MOD;  
 }  
 Int n, k;  
 int main()  
 {  
      cin >> n >> k;  
      init();  
      Int ans = 0;  
      for (int i = 1; i <= n; i++) {  
           int num = (n / i);  
           if (num >= k) {  
                ans = (ans + nCk(num - 1, k - 1)) % MOD;  
           }  
      }  
      cout << ans << endl;  
      return 0;  
 }  

POJ.3214 Heap

1.Problem
http://poj.org/problem?id=3214

2.Idea
Post-Order traversal and LIS.

3.Source

 #include<iostream>  
 #include<cstdio>  
 #include<algorithm>  
 #include<queue>  
 #define maxn 0x7fffffff  
 using namespace std;  
 const int N=2e6;  
 int a[N];  
 int n,x=0;  
 int st[N];  
 vector<int>v;  
 void solve(int k,int& d){  
   if(2*k<=x) solve(k<<1,d);  
   if(2*k+1<=x) solve((k<<1)+1,++d);  
   v.push_back(a[k]-d);  
 }  
 int main()  
 {  
   scanf("%d",&n);  
   while(scanf("%d",&a[++x])!=EOF);  
   int d=0;  
   x--;  
   solve(1,d);  
   st[0]=-maxn;  
   int top=0;  
   for(int i=0,len=v.size();i<len;i++){  
     if(v[i]>=st[top])  
       st[++top]=v[i];  
     else{  
       int k=upper_bound(st,st+top+1,v[i])-st;  
       st[k]=v[i];  
     }  
   }  
   printf("%d\n",x-top);  
   return 0;  
 }  

POJ.1145 Tree Summing

1.Problem
http://poj.org/problem?id=1145

2.Idea
Tree pre-order traversing

3.Source

 int tree_sum(int n)  
 {  
      int ans = 0, m;  
      if (scanf(" (%d", &m)) {  
           ans = tree_sum(n - m) + tree_sum(n - m);  
           if (ans < 2) ans = 0;  
      }  
      else  
           ans = !n;  
      scanf(" )");  
      return ans;  
 }  
 int main()  
 {  
      int n;  
      while (scanf("%d", &n) != EOF) {  
           if (tree_sum(n)) printf("yes\n");  
           else printf("no\n");  
      }  
      return 0;  
 }  

POJ.3321 Apple Tree

1.Problme
http://poj.org/problem?id=3321

2.Idea
A good editorail using BIT.

3.Source

 const int MAX_N = 100009;  
 int table[MAX_N+1];  
 int BIT[MAX_N+1];  
 int tos[MAX_N+1];  
 int idx[MAX_N+1];  
 bool noApple[MAX_N+1];  
 vector<int> G[MAX_N+1];  
 int N, counter;  
 inline int readint(){  
   int ret = 0, x;  
   while(x=getchar(), !('0'<=x&&x<='9'));  
   ret = (x&15);  
   while(x=getchar(), '0'<=x&&x<='9') ret = (ret<<3) + (ret<<1) + (x&15);  
   return ret;  
 }  
 inline int sum(int n){int _R=0;for(;n;n-=n&-n)_R+=BIT[n];return _R;}  
 inline int sum(int from, int to){return sum(to-1)-sum(from-1);}  
 inline void add(int n, int x){for(;n<=N;n+=n&-n)BIT[n]+=x;}  
 inline void dfs(int v){  
      int gv = G[v].size();  
      table[v] = counter++;  
      for(int i=0; i<gv; i++){  
           if(!table[G[v][i]]) dfs(G[v][i]);  
      }  
      tos[table[v]] = counter;  
 }  
 int main(){  
      N = readint();  
      for(int i=0, x, y; i<N-1; i++){  
           x = readint(), y = readint();  
           G[x].push_back(y); G[y].push_back(x);  
      }  
      counter = 1;  
      dfs(1);  
      int M = readint();  
      for(int i=0, x; i<M; i++){  
           char op;  
           scanf(" %c ",&op);  
           x = table[readint()];  
           if(op=='Q'){  
                printf("%d\n", tos[x]-x-sum(x,tos[x]));  
           }  
           else{  
                noApple[x] = !noApple[x];  
                add(x,noApple[x]?1:-1);  
           }  
      }  
      return 0;  
 }  

POJ.1330 Nearest Common Ancestors

1.Problem
http://poj.org/problem?id=1330

2.Idea
while(x!=y) {
     if(depth x < depth y) y = parent of y;
     else  x = parent of x;
}

3.Source

 const int N = 10000;  
 vector<int> a[N]; // multiple linked list, the list of children for node i is a vector  
 int f[N], r[N]; // representations of parents and hierarchy, the parent and hierarchy for node i is f[i] and r[i]  
 void DFS(int u, int dep) // Pre-order Traversal from node u  
 {  
      r[u] = dep; // node u is at hierarchy dep  
      for (vector<int>::iterator it = a[u].begin(); it != a[u].end(); ++it)  
           DFS(*it, dep + 1);// Recursion for every child of u  
 }  
 int main()  
 {  
      int casenum, num, n, i, x, y;  
      scanf("%d", &casenum); // number of test cases  
      for (num = 0; num < casenum; num++)  
      {  
           scanf("%d", &n); // number of nodes  
           for (i = 0; i < n; i++) a[i].clear(); //initialization  
           memset(f, 255, sizeof(f));  
           for (i = 0; i < n - 1; i++)  
           {  
                scanf("%d %d", &x, &y); // edge (x, y)  
                a[x - 1].push_back(y - 1); // push node (y-1) into the list of (x - 1)’s children  
                f[y - 1] = x - 1; //node(y-1)’s parent is (x-1)  
           }  
           for (i = 0; f[i] >= 0; i++); // search the root i  
           DFS(i, 0); // calculate every nodes’ hierarchy from the root  
           scanf("%d %d", &x, &y); // a pair of nodes  
           x--; y--;  
           while (x != y) // to find the Nearest Common Ancestors  
           {  
                if (r[x]>r[y]) x = f[x];  
                else y = f[y];  
           }  
           printf("%d\n", x + 1);// Output  
      }  
      return 0;  
 }  

LeetCode.402 Remove K Digits

1.Problem
https://leetcode.com/problems/remove-k-digits/

2.Idea
Keep deleting first x such is *xy*, x > y.

3.Source

 string removeKdigits(string num, int k) {  
      string ans = "";  
      for (int i = 0; i < num.size(); i++) {  
           while (ans.size() && ans.back() > num[i] && k) {  
                ans.pop_back();  
                k--;  
           }  
           if (ans.length() || num[i] != '0')  
                ans.push_back(num[i]);  
      }  
      while (ans.size() && k) {  
           ans.pop_back();  
           k--;  
      }  
      return ans == "" ? "0" : ans;  
 }  

Codeforces.1349B Orac and Medians

1.Problem
https://codeforces.com/problemset/problem/1349/B

2.Idea
Prime Factorization

3.Source

 int n;  
 ll a[N];  
 map<ll, vector<int>> mp;  
 void pFac(ll H)  
 {  
      for (ll i = 2; i*i <= H; i++) {  
           int cnt = 0;  
           while (H%i == 0) {  
                cnt++;  
                H /= i;  
           }  
           if (cnt > 0) {  
                mp[i].push_back(cnt);  
           }  
      }  
      if (H > 1) {  
           mp[H].push_back(1);  
      }  
 }  
 ll gcd(const ll a, const ll b)  
 {  
      if (b == 0) return a;  
      return gcd(b, a%b);  
 }  
 int main() {  
      scanf("%d\n", &n);  
      for (int i = 0; i < n; i++) {  
           scanf("%d", &a[i]);  
           pFac(a[i]);  
      }  
      if (n == 2) {  
           cout << a[0] * a[1] / gcd(a[0] , a[1]) << endl;  
           return 0;  
      }  
      ll ans = 1;  
      for (auto itr = mp.begin(); itr != mp.end(); itr++) {  
           int p = itr->first;  
           vector<int> v = itr->second;  
           int k = 0;  
           if (v.size() + 2 <= n) continue;  
           sort(v.begin(), v.end());  
           if (v.size() + 1 == n) {  
                k = v[0];  
           }  
           else {  
                k = v[1];  
           }  
           int t = (int)pow(1.0 * p, 1.0 * k);  
           ans = ans * (ll)t;  
      }  
      printf("%d\n", ans);  
      return 0;  
 }  

POJ.1012 Joseph

1.Problem
http://poj.org/problem?id=1012

2.Idea
https://en.wikipedia.org/wiki/Josephus_problem

3.Source

 int Joseph[15];  
 int k;  
 int main()  
 {  
      while (scanf("%d", &k) && k) {  
           if (Joseph[k]) {  
                printf("%d\n", Joseph[k]);  
                continue;  
           }  
           int n = 2 * k, m = 1;  
           int flag[30] = { 0 };  
           for (int i = 1; i <= k; i++) {  
                flag[i] = (flag[i - 1] + m - 1) % (n - i + 1);  
                if (flag[i] < k) {  
                     i = 0;  
                     m++;  
                }  
           }  
           Joseph[k] = m;  
           printf("%d\n", m);  
      }  
      return 0;  
 }  

LeetCode.1439 Find the Kth Smallest Sum of a Matrix With Sorted Rows

1.Problem
https://leetcode.com/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/

2.Idea
Divide & Conquer. Process by 2 rows from top.

3.Source

 class Solution {  
 public:  
      int kthSmallest(vector<vector<int>>& mat, int k) {  
           vector<int> ans = mat[0];  
           int n = mat.size();  
           int m = mat[0].size();  
           for (int i = 1; i < n; i++) {  
                vector<int> tmp;  
                for (int j = 0; j < ans.size(); j++) {  
                     for (int l = 0; l < m; l++) {  
                          tmp.push_back(ans[j] + mat[i][l]);  
                     }  
                }  
                sort(tmp.begin(), tmp.end());  
                ans.clear();  
                for (int i = 0; i < min(k, (int)tmp.size()); i++) {  
         ans.push_back(tmp[i]);  
       }  
           }  
           return ans[k - 1];  
      }  
 };  

LeetCode.1438 Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

1.Problem
https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

2.Idea
MaxMinQueue + 2 Pointers method

3.Source

 class MaxMinQueue {  
 public:  
      MaxMinQueue() {}  
      bool empty() { return elements.empty(); }  
      int size() { return elements.size(); }  
      void push(int val) {  
           elements.push(val);  
           while (!maxElements.empty() && val > maxElements.back()) maxElements.pop_back();  
           maxElements.push_back(val);  
           while (!minElements.empty() && val < minElements.back()) minElements.pop_back();  
           minElements.push_back(val);  
      }  
      int pop() {  
           int val = elements.front();  
           elements.pop();  
           if (val == maxElements.front()) maxElements.pop_front();  
           if (val == minElements.front()) minElements.pop_front();  
           return val;  
      }  
      int peekMax() {  
           return maxElements.front();  
      }  
      int peekMin() {  
           return minElements.front();  
      }  
 private:  
      queue<int> elements;  
      deque<int> maxElements;  
      deque<int> minElements;  
 };  
 class Solution {  
 public:  
      MaxMinQueue q;  
      int longestSubarray(vector<int>& nums, int limit) {  
           int n = nums.size();  
           int ans = 0;  
           int p1 = 0;  
           while (p1 < n) {  
                q.push(nums[p1]);  
                while(q.size() > 0 && (q.peekMax() - q.peekMin() > limit)) {  
                     q.pop();  
                }  
                ans = max(ans, q.size());  
                p1++;  
           }  
           return ans;  
      }  
 };  
 int main()  
 {  
      Solution obj;  
      vector<int> in = { 8,2,4,7 };  
      obj.longestSubarray(in, 4);  
      return 0;  
 }