[Toph] Easy Peasy Subset Sum

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Easy Peasy Subset Sum
Source            : Toph
Category          : Data Structures
Algorithm         : Implicit Treap
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll              long long int
 
static const int maxn = 1e5 + 5;
static const ll mod = 1e9 + 7;
 
struct Node
{
      ll val, sum;
      int priority, sze;
      Node *lft, *rgt;
      Node(ll val = 0)
      {
            this->val = val;
            this->sum = val;
            this->priority = rand();
            this->sze = 1;
            this->lft = this->rgt = nullptr;
      }
};
 
typedef Node*             pnode;
 
int sz(pnode t)
{
      return (t == nullptr ? 0 : t->sze);
}
 
void updateSize(pnode t)
{
      if (t) t->sze = sz(t->lft) + 1 + sz(t->rgt);
}
 
void combine(pnode t)
{
      t->sum = t->val;
      if (t->lft) t->sum = (t->sum + t->lft->sum) % mod;
      if (t->rgt) t->sum = (t->sum + t->rgt->sum) % mod;
}
 
void Split(pnode t, pnode &l, pnode &r, int pos, int add = 0)
{
      // 'pos' goes to left subtree
      if (t == nullptr) return void(l = r = nullptr);
      int curr = sz(t->lft) + add;
      if (curr <= pos) Split(t->rgt, t->rgt, r, pos, curr + 1), l = t;
      else Split(t->lft, l, t->lft, pos, add), r = t;
      updateSize(t);
      combine(t);
}
 
void Merge(pnode &t, pnode l, pnode r)
{
      if (l == nullptr or r == nullptr) t = l ? l : r;
      else if (l->priority < r->priority) Merge(r->lft, l, r->lft), t = r;
      else Merge(l->rgt, l->rgt, r), t = l;
      updateSize(t);
      combine(t);
}
 
pnode Insert(pnode t, pnode newnode, int pos)
{
      pnode L, R;
      Split(t, L, R, pos - 1);
      Merge(t, L, newnode);
      Merge(t, t, R);
      return t;
}
 
ll query(pnode t, int pos)
{
      if (t == nullptr || pos <= 0) return 0;
      pnode L, R;
      Split(t, L, R, pos-1);
      ll sum = L->sum;
      Merge(t, L, R);
      return sum;
}
 
ll kth(pnode t, int k)
{
      if (t == nullptr) return -1;
      int curr = sz(t->lft) + 1;
      if (curr == k) return t->val;
      if (curr < k) return kth(t->rgt, k - curr);
      else return kth(t->lft, k);
}
 
int binarySearch(pnode t, ll val)
{
      int lo = 1;
      int hi = sz(t);
      int ans = 0;
      while (lo <= hi)
      {
            int mid = lo + hi >> 1;
            ll k = kth(t, mid);
            if (k <= val) ans = mid, lo = mid + 1;
            else hi = mid - 1;
      }
      return ans;
}
 
void display(pnode t)
{
      if (t == nullptr) return;
      display(t->lft);
      cerr << t->val << ' ';
      display(t->rgt);
}
 
ll power_two[maxn];
 
void power_calc()
{
      power_two[0] = 1;
      for (int i = 1; i < maxn; i++)
      {
            power_two[i] = (1LL * 2 * power_two[i-1]) % mod;
      }
}
 
int main()
{
      #ifndef ONLINE_JUDGE
            freopen("in.txt", "r", stdin);
      #endif // ONLINE_JUDGE
 
      power_calc();
 
      int n;
      cin >> n;
      vector <ll> arr(n);
      for (ll &x : arr) cin >> x;
 
      if (n == 1)
      {
            cout << 0 << '\n';
            exit(0);
      }
 
      pnode treap = nullptr;
      ll cumsum = 0;
      ll sum = 0;
      ll mul = power_two[n-2];
 
      for (int i = n-1; i >= 0; i--)
      {
            ll x = arr[i];
 
            ll small_or_equal = binarySearch(treap, x);
            ll greatter = sz(treap) - small_or_equal;
 
            ll small_or_equal_sum = query(treap, small_or_equal);
            ll greatter_sum = cumsum - small_or_equal_sum;
 
            //cerr << i << " -> " << small_or_equal << " : " << greatter << endl;
            //cerr << small_or_equal_sum << " -- " << greatter_sum << endl;
 
 
            ll p = (small_or_equal * mul % mod * x) % mod;
            ll q = (mul * small_or_equal_sum) % mod;
 
            ll add_small_or_equal = (p - q + mod) % mod;
 
            p = (mul * greatter_sum) % mod;
            q = (mul * x % mod * greatter) % mod;
 
            ll add_greatter = (p - q + mod) % mod;
 
            sum = (sum + add_small_or_equal + add_greatter) % mod;
 
            cumsum = (cumsum + x) % mod;
            x %= mod;
            treap = Insert(treap, new Node(x), small_or_equal);
      }
      cout << sum << '\n';
      //display(treap);
}
 

[Codeforces] C. k-Tree

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : C. k-Tree
Source            : Codeforces
Category          : Dynamic Programing
Algorithm         : Basic Dynamic Programing
Verdict           : Accepted

#include <bits/stdc++.h>  
  
using namespace std;  
  
static const int maxn = 100 + 5;  
static const int mod = (int)1e9+7;  
  
int add(int a, int b)  
{  
      a += b;  
      if (a >= mod) a -= mod;  
      return a;  
}  
  
int dp[maxn][2];  
bool memoize[maxn][2];  
int n, k, d;  
  
int solve(int sum = 0, bool flag = 0)  
{  
      if (sum == n) return flag;  
      if (sum > n) return 0;  
      int &ret = dp[sum][flag];  
      bool &mem = memoize[sum][flag];  
      if (mem) return ret;  
      mem = 1;  
      ret = 0;  
      for (int weight = 1; weight <= k; weight++)  
      {  
            ret = add(ret, solve(sum + weight, flag | weight >= d));  
      }  
      return ret;  
}  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(NULL);  
      cout << fixed << setprecision(15);  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      cin >> n >> k >> d;  
      cout << solve(0, 0) << '\n';  
}  

[Codeforces] D. Random Task

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : D. Random Task
Source            : Codeforces
Category          : Dynamic Programing, Search
Algorithm         : Digit DP, Binary Search
Verdict           : Accepted

#include <bits/stdc++.h>  
  
using namespace std;  
  
#define ll            long long int  
  
ll dp[70][70];  
bool memoize[70][70];  
int a[70];  
  
ll m, k;  
  
ll solve(int pos, int one = 0, bool flag = 1, bool take = 0)  
{  
      if (pos < 0) return one == k;  
      ll &ret = dp[pos][one];  
      bool &mem = memoize[pos][one];  
      if (!flag && take && mem) return ret;  
      int loop = 1;  
      if (flag) loop = a[pos];  
      ll sum = 0;  
      for (int i = 0; i <= loop; i++)  
      {  
            if (!take && i == 0) sum += solve(pos-1, 0, 0, 0);  
            else sum += solve(pos-1, one + i, flag & i == a[pos], 1);  
      }  
      if (!flag && take) mem = 1, ret = sum;  
      return sum;  
}  
  
ll digit_dp(ll num)  
{  
      int len = 0;  
      while (num) a[len++] = num % 2, num /= 2;  
      return solve(len-1);  
}  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(NULL);  
      cout << fixed << setprecision(15);  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      cin >> m >> k;  
      ll lo = 1;  
      ll hi = 1e18;  
      ll ans = -1;  
      while (lo <= hi)  
      {  
            ll mid = lo + (hi - lo) / 2;  
            ll cnt = digit_dp(mid*2) - digit_dp(mid);  
            if (cnt == m)  
            {  
                  ans = mid;  
                  hi = mid - 1;  
            }  
            else if (cnt < m) lo = mid + 1;  
            else hi = mid - 1;  
      }  
      assert(ans != -1);  
      cout << ans;  
}  

[Toph] An Obvious Interactive Problem

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : An Obvious Interactive Problem
Source            : Toph
Category          : Interactive Problems
Algorithm         : Interactive Problems, Binary Search
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout << fixed << setprecision(2);  
  
      int lo = 0;  
      int hi = 1000000;  
      while (lo <= hi)  
      {  
            int mid = lo + hi >> 1;  
            cout << mid << endl;  
            fflush(stdout);  
            string s;  
            cin >> s;  
            if (s == "Bigger") lo = mid + 1;  
            else if (s == "Smaller") hi = mid - 1;  
            else break;  
      }  
}