Showing posts with label DP Optimization. Show all posts
Showing posts with label DP Optimization. Show all posts

Saturday, January 27, 2024

[Hackerearth] Odd Bit Array

 

Problem Link    : Odd Bit Array
Category        : Xor, DP, DP Optimization
Contest         : January Circuits '24


#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
template <const int32_t MOD> struct modint {
    int32_t value;
    modint() = default;
    modint(int32_t value_) : value(value_) {}
    inline modint<MOD> operator + (modint<MOD> other) const { int32_t c = this->value + other.value; return modint<MOD>(c >= MOD ? c - MOD : c); }
    inline modint<MOD> operator - (modint<MOD> other) const { int32_t c = this->value - other.value; return modint<MOD>(c <    0 ? c + MOD : c); }
    inline modint<MOD> operator * (modint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return modint<MOD>(c < 0 ? c + MOD : c); }
    inline modint<MOD> & operator += (modint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline modint<MOD> & operator -= (modint<MOD> other) { this->value -= other.value; if (this->value < 0) this->value += MOD; return *this; }
    inline modint<MOD> & operator *= (modint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
    inline modint<MOD> operator - () const { return modint<MOD>(this->value ? MOD - this->value : 0); }
    modint<MOD> pow(uint64_t k) const { modint<MOD> x = *this, y = 1; for (; k; k >>= 1) { if (k & 1) y *= x; x *= x; } return y; }
    modint<MOD> inv() const { return pow(MOD - 2); }  // MOD must be a prime
    inline modint<MOD> operator /  (modint<MOD> other) const { return *this *  other.inv(); }
    inline modint<MOD> operator /= (modint<MOD> other)       { return *this *= other.inv(); }
    inline bool operator == (modint<MOD> other) const { return value == other.value; }
    inline bool operator != (modint<MOD> other) const { return value != other.value; }
    inline bool operator < (modint<MOD> other) const { return value < other.value; }
    inline bool operator > (modint<MOD> other) const { return value > other.value; }
};
template <int32_t MOD> modint<MOD> operator * (int64_t value, modint<MOD> n) { return modint<MOD>(value) * n; }
template <int32_t MOD> modint<MOD> operator * (int32_t value, modint<MOD> n) { return modint<MOD>(value % MOD) * n; }
template <int32_t MOD> istream & operator >> (istream & in, modint<MOD> &n) { return in >> n.value; }
template <int32_t MOD> ostream & operator << (ostream & out, modint<MOD> n) { return out << n.value; }
 
const int mod = 1e9 + 7;
using mint = modint<mod>;
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = true; string FILE = "in.txt";
    if (FILEIO and fopen(FILE.c_str(), "r")) {
        freopen(FILE.c_str(), "r", stdin);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        int n;
        cin >> n;
        vector<int> arr(n);
        vector<int> parity(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
            parity[i] = __builtin_popcount(arr[i]) & 1;
        }
        vector<int> paritysum(n);
        for (int i = n - 1; i >= 0; i--) {
            paritysum[i] = parity[i] + (i + 1 < n ? paritysum[i + 1] : 0);
        }
        vector<mint> dp(n);
        vector<mint> results(2);
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            int lookup = paritysum[i] & 1;
            if (parity[i] == 0) {
                lookup ^= 1;
            }
            cnt += parity[i];
            dp[i] = results[lookup];
            if (cnt & 1) {
                dp[i] += 1;
            }
            if (i + 1 < n) {
                results[ paritysum[i + 1] & 1 ] += dp[i];
            }
        }
        cout << dp.back() << endl;
    }
 
}

Sunday, January 13, 2019

[UVa] 12836 - Gain Battle Power

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 12836 - Gain Battle Power
Source            : CodeChef
Category          : Dynamic Programing Optimization
Algorithm         : Knuth Optimization
Verdict           : Accepted

  1. #include <bits/stdc++.h>  
  2.   
  3. using namespace std;  
  4.   
  5. #define ll         long long int  
  6.   
  7. static const int maxn = 1000 + 5;  
  8.   
  9. int n;  
  10. int strength[maxn];  
  11. ll power[maxn], sumPower[maxn];  
  12. int Right[maxn], Left[maxn];  
  13.   
  14. inline int goRight(int u)   // LDS in right part  
  15. {  
  16.       if (Right[u] != -1) return Right[u];  
  17.       int maxi = 0;  
  18.       for (int v = u+1; v <= n; v++)  
  19.       {  
  20.             if (strength[v] < strength[u])  
  21.             {  
  22.                   if (goRight(v) > maxi)  
  23.                   {  
  24.                         maxi = goRight(v);  
  25.                   }  
  26.             }  
  27.       }  
  28.       Right[u] = 1 + maxi;  
  29.       return Right[u];  
  30. }  
  31.   
  32. inline int goLeft(int u) // LDS in left part  
  33. {  
  34.       if (Left[u] != -1) return Left[u];  
  35.       int maxi = 0;  
  36.       for (int v = u-1; v >= 1; v--)  
  37.       {  
  38.             if (strength[v] < strength[u])  
  39.             {  
  40.                   if (goLeft(v) > maxi)  
  41.                   {  
  42.                         maxi = goLeft(v);  
  43.                   }  
  44.             }  
  45.       }  
  46.       Left[u] = 1 + maxi;  
  47.       return Left[u];  
  48. }  
  49.   
  50. inline void Power()  
  51. {  
  52.       for (int i = 1; i <= n; i++)  
  53.       {  
  54.             power[i] = Right[i] + Left[i] - 1;  
  55.             sumPower[i] = sumPower[i-1] + power[i];  
  56.       }  
  57. }  
  58.   
  59. inline ll getPower(int l, int r)  
  60. {  
  61.     return sumPower[r] - sumPower[l];  
  62. }  
  63.   
  64. ll dp[maxn][maxn];  
  65. bool vis[maxn][maxn];  
  66. int mid[maxn][maxn];  
  67.   
  68. /**           TLE 
  69. ll solve(int left, int right) 
  70. { 
  71.       if (left == right) return 0; 
  72.       ll &ret = dp[left][right]; 
  73.       bool &v = vis[left][right]; 
  74.       if (v == 1) return ret; 
  75.       v = 1; 
  76.       ll mini = 1e17 + 7; 
  77.       for (int i = left; i < right; i++) 
  78.       {  
  79.           ll temp = solve(left, i) + solve(i+1, right) + getPower(left, right); 
  80.           if (temp < mini) mini = temp; 
  81.       } 
  82.       return ret = mini; 
  83. } 
  84. **/  
  85.   
  86. inline ll knuth_optimization()  
  87. {  
  88.       memset(dp, 0, sizeof dp);  
  89.       memset(mid, 0, sizeof mid);  
  90.       for (int s = 0; s <= n; s++)  
  91.       {  
  92.           for (int l = 0; l+s <= n; l++)  
  93.           {  
  94.               int r = l+s;  
  95.               if (s < 2)  
  96.               {  
  97.                   dp[l][r] = 0;  
  98.                   mid[l][r] = l;  
  99.                   continue;  
  100.               }  
  101.               int mleft = mid[l][r-1];  
  102.               int mright = mid[l+1][r];  
  103.               dp[l][r] = 1e17 + 7;  
  104.               for (int mm = mleft; mm <= mright; mm++)  
  105.               {  
  106.                   ll tmp = dp[l][mm] + dp[mm][r] + getPower(l, r);  
  107.                   if (tmp < dp[l][r])  
  108.                   {  
  109.                       dp[l][r] = tmp;  
  110.                       mid[l][r] = mm;  
  111.                   }  
  112.               }  
  113.           }  
  114.       }  
  115.       return dp[0][n];  
  116. }  
  117.   
  118. inline void init()  
  119. {  
  120.       memset(strength, 0, sizeof strength);  
  121.       memset(vis, 0, sizeof vis);  
  122.       memset(Right, -1, sizeof Right);  
  123.       memset(Left, -1, sizeof Left);  
  124. }  
  125.   
  126. int main()  
  127. {  
  128.       int tc;  
  129.       scanf("%d", &tc);  
  130.       for (int tcase = 1; tcase <= tc; tcase++)  
  131.       {  
  132.             init();  
  133.             scanf("%d", &n);  
  134.             for (int i = 1; i <= n; i++) scanf("%d", strength+i);  
  135.             for (int i = 1; i <= n; i++) goRight(i);  
  136.             for (int i = n; i >= 1; i--) goLeft(i);  
  137.             Power();  
  138.             //ll ans = solve(1, n);  
  139.             ll ans = knuth_optimization();  
  140.             printf("Case %d: %lld\n", tcase, ans);  
  141.       }  
  142. }