mr_dot_convict

1238-Folding-Timus-mr.convict

Sep 26th, 2020
1,218
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include      <bits/stdc++.h>
  2. using namespace std;
  3. #define IOS       ios_base::sync_with_stdio(false); cin.tie (nullptr)
  4. #define PREC      cout.precision (10); cout << fixed
  5. #ifdef CONVICTION
  6. #include "/home/convict/Dropbox/myfiles/sport_coding/cplib/snippets/debug.h"
  7. #else
  8. #define debug(x...)
  9. #endif
  10. //Don’t practice until you get it right. Practice until you can’t get it wrong
  11.  
  12.  
  13. const int Maxn = 200;
  14.  
  15. int rep[Maxn][Maxn]; // reo[pos][len] -> how many occurances of pos->pos+len-1 from pos
  16. pair <int, int> dp[Maxn][Maxn]; // dp[pos][len] -> {}
  17. int N;
  18. string s;
  19.  
  20. void preproc()
  21. {
  22. }
  23.  
  24. void solve()
  25. {
  26.    cin >> s;
  27.    N = (int)s.size();
  28.  
  29.    // calculate rep
  30.    memset(rep, 0, sizeof(rep));
  31.    for (int len = 1; len <= N; ++len) {
  32.       for (int pos = N - 1; pos >= 0; --pos) { // working on prefixes
  33.          // now find rep[pos][len]
  34.          if (pos + len - 1 >= N)
  35.             continue;
  36.          rep[pos][len] = 1;
  37.          if (pos + 2*len - 1 <= N - 1) {
  38.             bool is_same = true;
  39.             for (int k = 0; k < len; ++k) {
  40.                if (s[pos + k] != s[pos + len + k]) {
  41.                   is_same = false;
  42.                   break;
  43.                }
  44.             }
  45.             if (is_same) {
  46.                rep[pos][len] += rep[pos + len][len];
  47.             }
  48.          }
  49.       }
  50.    }
  51.  
  52.    auto dig = [&] (int x) -> int {
  53.       int res = 0;
  54.       while (x) ++res, x /= 10;
  55.       return res;
  56.    };
  57.  
  58.    // calculate dp // dp[pos][len]
  59.    // choose some mid, mid in [pos, pos+len-1], (pos, mid-1), (mid, pos+len-1)
  60.    for (int pos = 0; pos < N; ++pos) {
  61.       dp[pos][1] = make_pair(1, pos);
  62.    }
  63.  
  64.    for (int len = 2; len <= N; ++len) { // increasing length
  65.       for (int pos = 0; pos < N; ++pos) {
  66.          /// calculate the value of dp[pos][len]
  67.          dp[pos][len] = make_pair(INT_MAX, INT_MAX);
  68.          // go for partition
  69.          for (int mid = pos + 1; mid <= pos + len - 1; ++mid) {
  70.             assert(mid - pos != 0 and len - (mid - pos) != 0);
  71.             // parition into [pos, mid-1] and [mid, pos + len - 1]
  72.             auto join = make_pair(dp[pos][mid - pos].first +
  73.                   dp[mid][len - (mid - pos)].first, mid);
  74.             dp[pos][len] = min(dp[pos][len], join);
  75.          }
  76.  
  77.          // take the whole string and go deeper
  78.          for (int k = 1; 2 * k <= len; ++k) {
  79.             // k * min(len / k, rep[pos][k]) == len
  80.             // 2 + dig(min(len / k,rep[pos][k])) + dp[pos][k]
  81.             if (len % k == 0 and
  82.                   k * min(len / k, rep[pos][k]) == len) {  // can be partitioned
  83.                auto comp = make_pair(2 + dig(min(len / k, rep[pos][k]))
  84.                      + dp[pos][k].first, -1 * k);
  85.                dp[pos][len] = min(dp[pos][len], comp);
  86.             }
  87.          }
  88.       }
  89.    }
  90.  
  91.    // preorder traversal
  92.    function <void(int, int)> pre_order = [&] (int pos, int len) -> void {
  93.       if (len == 1) {
  94.          cout << s[pos];
  95.          return;
  96.       }
  97.       auto sol = dp[pos][len];
  98.       if (sol.second < 0) { // repitition string
  99.          int sub_len = -1*sol.second;
  100.          cout << len / sub_len << "(";
  101.          pre_order(pos, sub_len);
  102.          cout << ")";
  103.          return;
  104.       }
  105.       else { // break into two
  106.          int mid = sol.second;
  107.          pre_order(pos, mid - pos);
  108.          pre_order(mid, len - (mid - pos));
  109.          return;
  110.       }
  111.    };
  112.  
  113.    // debug(dp[0][N].first);
  114.    pre_order(0, N);
  115. }
  116.  
  117. signed main()
  118. {
  119.   IOS; PREC;
  120.   preproc();
  121.  
  122.   int tc = 1;
  123.   // cin >> tc;
  124.   for (int Tt = 1; Tt <= tc; ++Tt) {
  125.     // cout << "Case #" << Tt << ": ";
  126.     solve();
  127.   }
  128.   return EXIT_SUCCESS;
  129. }
  130.  
RAW Paste Data