POJ.3709 K-Anonymous Sequence

1.Problem
3709 -- K-Anonymous Sequence (poj.org)

2.Idea
Deque

3.Source

 int n, k;  
 Int a[N];  
 Int dp[N], S[N];  
 int deq[N];  
 Int f(int j, int x)  
 {  
      return -a[j] * x + dp[j] - S[j] + a[j] * j;  
 }  
 bool check(int f1, int f2, int f3)  
 {  
      Int a1 = -a[f1], b1 = dp[f1] - S[f1] + a[f1] * f1;  
      Int a2 = -a[f2], b2 = dp[f2] - S[f2] + a[f2] * f2;  
      Int a3 = -a[f3], b3 = dp[f3] - S[f3] + a[f3] * f3;  
      return (a2 - a1) * (b3 - b2) >= (b2 - b1) * (a3 - a2);  
 }  
 void solve()  
 {  
      int t; cin >> t;  
      while (t--) {  
           scanf("%d%d", &n, &k);  
           for (int i = 0; i < n; i++) {  
                scanf("%d", &a[i]);  
           }  
           for (int i = 0; i < n; i++) {  
                S[i + 1] = S[i] + a[i];  
           }  
           int s = 0, t = 1;  
           deq[0] = 0;  
           dp[0] = 0;  
           for (int i = k; i <= n; i++) {  
                if (i - k >= k) {  
                     while (s + 1 < t && check(deq[t - 2], deq[t - 1], i - k)) t--;  
                     deq[t++] = i - k;  
                }  
                while (s + 1 < t && f(deq[s], i) >= f(deq[s + 1], i)) s++;  
                dp[i] = S[i] + f(deq[s], i);  
           }  
           printf("%lld\n", dp[n]);  
      }  
 }  

LeetCode.472 Concatenated Words

1.Problem
Concatenated Words - LeetCode

2.Idea
Trie + DFS

3.Source

 class TrieNode {  
   public:  
   bool isKey = false;  
   TrieNode* child[26];  
 };  
 class Solution {  
 public:  
   TrieNode* root = new TrieNode();  
   void addWord(string word) {  
     TrieNode* curr = root;  
     for(char c : word) {  
       if(!curr->child[c - 'a'])  
         curr->child[c - 'a'] = new TrieNode();  
       curr = curr->child[c - 'a'];  
     }  
     curr->isKey = true;  
   }  
   bool search(string word, int index, int count) {  
     if(index >= word.size()) return count >= 2;  
     TrieNode* curr = root;  
     for(int i= index; i < word.size(); i++) {  
       char c = word[i];  
       if(!curr->child[c - 'a'])  
         return false;  
       curr = curr->child[c - 'a'];  
       if(curr->isKey) {  
         if(search(word, i+1, count + 1))  
           return true;  
       }  
     }  
     return false;  
   }  
   vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {  
     vector<string> res;  
     if(words.size() == 0) return res;  
     for(string s : words)   
       addWord(s);  
     for(string s : words) {  
       if(search(s, 0, 0))  
         res.push_back(s);  
     }  
     return res;  
   }  
 };  

POJ.2082 Terrible Sets

1.Problem
2082 -- Terrible Sets (poj.org)

2.Idea
Description is terrible but it was just simple max rectangle in histogram problem.

3.Source

 int n;  
 int h[N];  
 int st[N], L[N], R[N], sum[N];  
 int maxRec() {  
      //L   
      int t = 0;  
      for (int i = 0; i < n; i++) {  
           while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
           L[i] = (t == 0 ? 0 : (st[t - 1] + 1));  
           st[t++] = i;  
      }  
      //R   
      t = 0;  
      for (int i = n - 1; i >= 0; i--) {  
           while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
           R[i] = (t == 0 ? n : st[t - 1]);  
           st[t++] = i;  
      }  
      int res = 0;  
      for (int i = 0; i < n; i++) {  
           res = max(res, h[i] * (sum[R[i]] - sum[L[i]]));  
      }  
      return res;  
 }  
 void solve()  
 {  
      while (cin >> n) {  
           if (n < 0) break;  
           for (int i = 0; i < n; i++) {  
                scanf("%d%d", &sum[i + 1], &h[i]);  
           }  
           for (int i = 0; i < n; i++)   
                sum[i + 1] += sum[i];  
           printf("%d\n", maxRec());  
      }  
 }  

POJ.3250 Bad Hair Day

1.Problem
3250 -- Bad Hair Day (poj.org)

2.Idea
Use monoton stack

3.Source

 int n;  
 Int h[80200];  
 void solve()  
 {       
      int n; cin >> n;  
      for (int i = 0; i < n; i++) {  
           scanf("%d", &h[i]);  
      }  
      h[n] = MOD;  
      Int ans = 0;  
      stack<int> st;//monoton stack  
      for (int i = 0; i <= n; i++) {  
           if (st.empty() || h[st.top()] > h[i])  
                st.push(i);  
           else {  
                while (!st.empty() && h[st.top()] <= h[i]) {  
                     int tmp = st.top(); st.pop();  
                     ans += (Int)(i - tmp - 1);  
                }  
                st.push(i);  
           }  
      }  
      printf("%lld\n", ans);  
 }  

POJ.3494 Largest Submatrix of All 1’s

1.Problem
3494 -- Largest Submatrix of All 1’s (poj.org)

2.Idea
Apply the max rectangle in histogram problem.

3.Source

 int m, n;  
 int h[2200];  
 int st[2200], L[2200], R[2200];  
 int maxRec() {  
      //L  
      int t = 0;  
      for (int i = 0; i < n; i++) {  
           while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
           L[i] = (t == 0 ? 0 : (st[t - 1] + 1));  
           st[t++] = i;  
      }  
      //R  
      t = 0;  
      for (int i = n - 1; i >= 0; i--) {  
           while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
           R[i] = (t == 0 ? n : st[t - 1]);  
           st[t++] = i;  
      }  
      int res = 0;  
      for (int i = 0; i < n; i++) {  
           res = max(res, h[i] * (R[i] - L[i]));  
      }  
      return res;  
 }  
 void solve()  
 {       
      while (cin >> m >> n) {  
           memset(h, 0, sizeof h);  
           int ans = 0;  
           for (int i = 0; i < n; i++) {  
                for (int j = 0; j < m; j++) {  
                     int t; scanf("%d", &t);  
                     h[j] = t ? h[j] + 1 : 0;  
                }  
                ans = max(ans, maxRec());  
           }  
           printf("%d\n", ans);  
      }  
 }  

POJ.2559 Largest Rectangle in a Histogram

1.Problem
2559 -- Largest Rectangle in a Histogram (poj.org)

2.Idea
Using stack

3.Source

 int n;  
 int h[N];  
 int L[N], R[N], st[N];  
 void solve()  
 {       
      while (scanf("%d", &n), n) {  
           REP(i, n) scanf("%d", &h[i]);  
           //L  
           int t = 0;  
           for (int i = 0; i < n; i++) {  
                while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
                L[i] = (t == 0 ? 0 : (st[t - 1] + 1));  
                st[t++] = i;  
           }  
           //R  
           t = 0;  
           for (int i = n - 1; i >= 0; i--) {  
                while (t > 0 && h[st[t - 1]] >= h[i]) t--;  
                R[i] = (t == 0 ? n : st[t - 1]);  
                st[t++] = i;  
           }  
           long long res = 0;  
           for (int i = 0; i < n; i++) {  
                res = max(res, (long long)h[i] * (R[i] - L[i]));  
           }  
           printf("%lld\n", res);  
      }  
 }  

POJ.3729 Facer’s string

1.Problem
3729 -- Facer’s string (poj.org)

2.Idea
Suffix Array
Longest Common Prefix Array

3.Source Code

 const int MAXN = 50010;  
 int n, N, M, k, K;  
 int Rank[MAXN * 2];  
 int tmp[MAXN * 2];  
 int sa[MAXN * 2];  
 int lcp[MAXN * 2];  
 int s[MAXN * 2];  
 bool compare_sa(const int& i, const int& j) {  
      if (Rank[i] != Rank[j])return Rank[i] < Rank[j];  
      else {  
           int ri = i + k <= n ? Rank[i + k] : -1;  
           int rj = j + k <= n ? Rank[j + k] : -1;  
           return ri < rj;  
      }  
 }  
 void construct_sa(const int *S, int *sa) {  
      for (int i = 0; i <= n; i++) {  
           sa[i] = i;  
           Rank[i] = i < n ? S[i] : -1;  
      }  
      for (k = 1; k <= n; k *= 2) {  
           sort(sa, sa + n + 1, compare_sa);  
           tmp[sa[0]] = 0;  
           for (int i = 1; i <= n; i++) {  
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
           }  
           for (int i = 0; i <= n; i++) {  
                Rank[i] = tmp[i];  
           }  
      }  
 }  
 void construct_lcp(const int *S, int *sa, int *lcp) {  
      memset(lcp, 0, sizeof(lcp));  
      for (int i = 0; i <= n; i++)Rank[sa[i]] = i;  
      int h = 0;  
      lcp[0] = 0;  
      for (int i = 0; i < n; i++) {  
           int j = sa[Rank[i] - 1];  
           if (h > 0)h--;  
           for (; j + h < n&&i + h < n; h++) {  
                if (S[j + h] != S[i + h])break;  
           }  
           lcp[Rank[i] - 1] = h;  
      }  
 }  
 long long calc(int K) {  
      int A = 0, B = 0;  
      long long res = 0;  
      for (int i = 0; i < n; i++) {  
           if (lcp[i] < K) {  
                if (B > 0)res += A;  
                A = 0; B = 0;  
           }  
           if (sa[i + 1] < N)A++;  
           if (sa[i + 1] > N) B++;  
      }  
      return res;  
 }  
 void solve()  
 {       
      while (scanf("%d%d%d\n", &N, &M, &K) != EOF) {  
           for (int i = 0; i < N; i++) {  
                scanf("%d", &s[i]);  
                s[i]++;  
           }  
           s[N] = '$';  
           for (int i = N + 1; i < N + M + 1; i++) {  
                scanf("%d", &s[i]);  
                s[i]++;  
           }  
           n = N + M + 1;  
           s[n] = 0;  
           construct_sa(s, sa);  
           construct_lcp(s, sa, lcp);  
           printf("%lld\n", calc(K) - calc(K+1));  
      }  
 }  

POJ.3415 Common Substrings

1.Problem
3415 -- Common Substrings (poj.org)

2.Idea
Suffix Array
Monotonic Stack

3.Source

 const int MAX_L = 100000 + 1;  
 const int MAX_N = 2 * MAX_L + 1;  
 std::string S;  
 int n, k;  
 int sa[MAX_N + 1], lcp[MAX_N + 1];   
 int Rank[MAX_N + 1], tmp[MAX_N + 1];  
 bool compare_sa(const int i, const int j)  
 {  
      if (Rank[i] != Rank[j])  
      {  
           return Rank[i] < Rank[j];  
      }  
      return (i + k <= n ? Rank[i + k] : -1) < (j + k <= n ? Rank[j + k] : -1);  
 }  
 void construct_sa()  
 {  
      for (int i = 0; i <= n; i++)  
      {  
           sa[i] = i;  
           Rank[i] = i < n ? S[i] : -1;  
      }  
      for (k = 1; k <= n; k <<= 1)  
      {  
           std::sort(sa, sa + n + 1, compare_sa);  
           tmp[sa[0]] = 0;  
           for (int i = 1; i <= n; i++)  
           {  
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
           }  
           for (int i = 0; i <= n; i++)  
           {  
                Rank[i] = tmp[i];  
           }  
      }  
 }  
 void construct_lcp()  
 {  
      memset(lcp, 0, sizeof(lcp));  
      for (int i = 0; i <= n; i++)  
      {  
           Rank[sa[i]] = i;  
      }  
      int h = 0;  
      lcp[0] = 0;  
      for (int i = 0; i < n; i++)  
      {  
           int j = sa[Rank[i] - 1];  
           if (h > 0)  
           {  
                h--;  
           }  
           for (; i + h < n && j + h < n && S[i + h] == S[j + h]; h++);  
           lcp[Rank[i] - 1] = h;  
      }  
 }  
 int Stack[MAX_N][2];  
 long long contribution, top;  
 using namespace std;  
 long long calc(int K, int l1, bool is_s1)  
 {  
      long long ans = 0;  
      for (int i = 0; i < n; i++) {  
           if (lcp[i] < K) {  
                top = contribution = 0;  
           }  
           else {  
                int size = 0;  
                if ((is_s1 && sa[i] < l1) || (!is_s1 && sa[i] > l1)) {  
                     ++size;  
                     contribution += lcp[i] - K + 1;  
                }  
                while (top > 0 && lcp[i] <= Stack[top - 1][0]) {  
                     --top;  
                     contribution -= Stack[top][1] * (Stack[top][0] - lcp[i]);  
                     size += Stack[top][1];  
                }  
                if (size) {  
                     Stack[top][0] = lcp[i];  
                     Stack[top][1] = size;  
                     ++top;  
                }  
                if ((is_s1 && sa[i + 1] > l1) || (!is_s1 && sa[i + 1] < l1)) {  
                     ans += contribution;  
                }  
           }  
      }  
      return ans;  
 }  
 void solve()  
 {  
      int k;  
      while (scanf("%d", &k), k) {  
           string s1, s2;  
           cin >> s1 >> s2;  
           int l1 = s1.length();  
           int l2 = s2.length();  
           S = s1 + "$" + s2;  
           n = l1 + l2 + 1;  
           construct_sa();  
           construct_lcp();  
           printf("%lld\n", calc(k, l1, true) + calc(k, l1, false));  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.1509 Glass Beads

1.Problem
1509 -- Glass Beads (poj.org)

2.Idea
Suffix Array

3.Source Code

 const int MAXN = 20010;  
 int Rank[MAXN], tmp[MAXN];  
 int n, k;  
 int sa[MAXN];  
 bool compare_sa(int i, int j) {  
      if (Rank[i] != Rank[j]) return Rank[i] < Rank[j];  
      int ri = (i + k <= n) ? Rank[i + k] : -1;  
      int rj = (j + k <= n) ? Rank[j + k] : -1;  
      return ri < rj;  
 }  
 void createSA(const string& s, int* sa) {  
      n = s.size();  
      for (int i = 0; i <= n; i++) {  
           sa[i] = i;  
           Rank[i] = i < n ? s[i] : -1;  
      }  
      for (k = 1; k <= n; k *= 2) {  
           sort(sa, sa + n + 1, compare_sa);  
           tmp[sa[0]] = 0;  
           for (int i = 1; i <= n; i++) {  
                tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
           }  
           for (int i = 0; i <= n; i++) Rank[i] = tmp[i];  
      }  
 }  
 char str[MAXN];  
 void getInput(string& s) {  
      fgets(str, MAXN, stdin);  
      strtok(str, "\n\0");  
      s = str;  
 }  
 void solve()  
 {  
      int t;  
      scanf("%d\n", &t);  
      while (t--) {  
           string S;  
           getInput(S);  
           createSA(S + S + (char)('z' + 1), sa);  
           int ans = -1;  
           for (int i = 0; i <= n; i++) {  
                if (sa[i] < S.length()) {  
                     ans = sa[i] + 1;  
                     break;  
                }  
           }  
           printf("%d\n", ans);  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.2217 Secretary

1.Problem
2217 -- Secretary (poj.org)

2.Idea
Suffix Array
Longest Common Prefix Array

3. Source Code

 const int MAXN = 20010;  
 namespace SA {  
      int rank[MAXN], tmp[MAXN];  
      int n, k;  
      bool compare_sa(int i, int j) {  
           if (rank[i] != rank[j]) return rank[i] < rank[j];  
           int ri = (i + k <= n) ? rank[i + k] : -1;  
           int rj = (j + k <= n) ? rank[j + k] : -1;  
           return ri < rj;  
      }  
      void createSA(const string& s, int* sa) {  
           n = s.size();  
           for (int i = 0; i <= n; i++) {  
                sa[i] = i;  
                rank[i] = i < n ? s[i] : -1;  
           }  
           for (k = 1; k <= n; k *= 2) {  
                sort(sa, sa + n + 1, compare_sa);  
                tmp[sa[0]] = 0;  
                for (int i = 1; i <= n; i++) {  
                     tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
                }  
                for (int i = 0; i <= n; i++) rank[i] = tmp[i];  
           }  
      }  
      namespace LCP {  
           int rank[MAXN];  
           void createLCP(const string& s, const int* sa, int* lcp) {  
                int n = s.size();  
                for (int i = 0; i <= n; i++) rank[sa[i]] = i;  
                int h = 0;  
                lcp[0] = 0;  
                for (int i = 0; i < n; i++) {  
                     int j = sa[rank[i] - 1];  
                     h = max(0, h - 1);  
                     for (; j + h < n && i + h < n; h++) {  
                          if (s[j + h] != s[i + h]) break;  
                     }  
                     lcp[rank[i] - 1] = h;  
                }  
           }  
      } // namespace LCP  
 } // namespace SA  
 char str[MAXN];  
 void getInput(string& s) {  
      fgets(str, MAXN, stdin);  
      strtok(str, "\n\0");  
      s = str;  
 }  
 int sa[MAXN], lcp[MAXN];  
 void solve()  
 {  
      int t;  
      scanf("%d\n", &t);  
      while (t--) {  
           string S, T;  
           getInput(S); getInput(T);  
           int n = S.size(), m = T.size();  
           S += '\n';  
           S += T;  
           SA::createSA(S, sa);  
           SA::LCP::createLCP(S, sa, lcp);  
           int nm = S.size(), ans = 0;  
           for (int i = 0; i < nm; i++) {  
                if (sa[i] < n && sa[i + 1] < n) continue;  
                if (sa[i] > n && sa[i + 1] > n) continue;  
                ans = max(ans, lcp[i]);  
           }  
           printf("Nejdelsi spolecny retezec ma delku %d.\n", ans);  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.3581 Sequence

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

2.Idea
Suffix Array

3.Source

 const int MAXN = 20010;  
 namespace SA {  
      int rank[2 * MAXN], tmp[2 * MAXN];  
      int n, k;  
      bool compare_sa(int i, int j) {  
           if (rank[i] != rank[j]) return rank[i] < rank[j];  
           int ri = (i + k <= n) ? rank[i + k] : -1;  
           int rj = (j + k <= n) ? rank[j + k] : -1;  
           return ri < rj;  
      }  
      void createSA(const int* s, int N, int* sa) {  
           n = N;  
           for (int i = 0; i <= n; i++) {  
                sa[i] = i;  
                rank[i] = i < n ? s[i] : -1;  
           }  
           for (k = 1; k <= n; k *= 2) {  
                sort(sa, sa + n + 1, compare_sa);  
                tmp[sa[0]] = 0;  
                for (int i = 1; i <= n; i++) {  
                     tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
                }  
                for (int i = 0; i <= n; i++) rank[i] = tmp[i];  
           }  
      }  
 }  
 int N, A[MAXN], rev[2 * MAXN], sa[2 * MAXN];  
 void solve()  
 {  
      cin >> N;  
      for (int i = 0; i < N; i++) scanf("%d", A + i);  
      reverse_copy(A, A + N, rev);  
      SA::createSA(rev, N, sa);  
      int p1, p2;  
      for (int i = 0; i <= N; i++) {  
           p1 = N - sa[i];  
           if (p1 > 0 && N - p1 >= 2) break;  
      }  
      int m = N - p1;  
      reverse_copy(A + p1, A + N, rev);  
      reverse_copy(A + p1, A + N, rev + m);  
      SA::createSA(rev, 2 * m, sa);  
      for (int i = 0; i <= 2 * m; i++) {  
           p2 = m - sa[i];  
           if (p2 > 0 && m - p2 >= 1) break;  
      }  
      for (int i = p1 - 1; i >= 0; i--) printf("%d\n", A[i]);  
      for (int i = p1 + p2 - 1; i >= p1; i--) printf("%d\n", A[i]);  
      for (int i = N - 1; i >= p1 + p2; i--) printf("%d\n", A[i]);  
 }  
 int main() {  
      //ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }  

POJ.3690 Constellations

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

2.Idea
Rolling Hash D2

3.Source Code

 typedef unsigned long long ull;  
 int N, M, T, P, Q;  
 char field[1100][1100];  
 char patterns[110][1100][1100];  
 ull Hash[1100][1100], tmp[1100][1100];  
 void compute_hash(char a[1100][1100], int n, int m)  
 {  
      const ull B1 = 9973;  
      const ull B2 = 1000000007;  
      ull t1 = 1;  
      for (int j = 0; j < Q; j++) t1 *= B1;  
      for (int i = 0; i < n; i++) {  
           ull e = 0;  
           for (int j = 0; j < Q; j++) {  
                e = e * B1 + a[i][j];  
           }  
           for (int j = 0; j + Q <= m; j++) {  
                tmp[i][j] = e;  
                if (j + Q < m) e = e * B1 - t1 * a[i][j] + a[i][j + Q];  
           }  
      }  
      ull t2 = 1;  
      for (int i = 0; i < P; i++) t2 *= B2;  
      for (int j = 0; j + Q <= m; j++) {  
           ull e = 0;  
           for (int i = 0; i < P; i++) {  
                e = e * B2 + tmp[i][j];  
           }  
           for (int i = 0; i + P <= n; i++) {  
                Hash[i][j] = e;  
                if (i + P < n) e = e * B2 - t2 * tmp[i][j] + tmp[i + P][j];  
           }  
      }  
 }  
 void solve()  
 {  
      int cnt = 0;  
      while (true) {  
           scanf("%d%d%d%d%d", &N, &M, &T, &P, &Q);  
           if (N + M + T + P + Q == 0) break;  
           cnt++;  
           for (int i = 0; i < N; ++i) {  
                scanf("%s", field[i]);  
           }  
           for (int t = 0; t < T; ++t) {  
                for (int i = 0; i < P; ++i) {  
                     scanf("%s", patterns[t][i]);  
                }  
           }  
           multiset<ull> unseen;  
           for (int k = 0; k < T; k++) {  
                compute_hash(patterns[k], P, Q);  
                unseen.insert(Hash[0][0]);  
           }  
           compute_hash(field, N, M);  
           for (int i = 0; i + P <= N; i++) {  
                for (int j = 0; j + Q <= M; j++) {  
                     unseen.erase(Hash[i][j]);  
                }  
           }  
           printf("Case %d: %d\n", cnt, T - unseen.size());  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }