Showing posts with label Binary Search. Show all posts
Showing posts with label Binary Search. Show all posts

Saturday, January 27, 2024

[Hackerearth] RebelReach

 

Problem Link    : RebelReach
Category        : Graph, Binary Search
Contest         : January Circuits '24

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
using pii = pair<int, int>;
 
int n;
int q;
vector<vector<int>> graph;
vector<int> guards;
vector<vector<pii>> queries;
vector<int> arr;
vector<int> cumsum;
vector<int> ans;
 
void dfs(int u, int p) {
    arr.push_back(u);
    cumsum.push_back(guards[u] + (cumsum.size() ? cumsum.back() : 0));
    for (pii it : queries[u]) {
        int x = it.first;
        int lo = 0;
        int hi = arr.size() - 1;
        int id = arr.size() - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            int sum = cumsum.back() - (mid - 1 >= 0 ? cumsum[mid - 1] : 0);
            if (sum <= x) {
                id = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        int sum = cumsum.back() - (id - 1 >= 0 ? cumsum[id - 1] : 0);
        ans[it.second] = arr[id];
        if (sum < x and id - 1 >= 0) {
            ans[it.second] = arr[id - 1];
        }
    }
    for (int v : graph[u]) {
        if (v == p) {
            continue;
        }
        dfs(v, u);
    }
    arr.pop_back();
    cumsum.pop_back();
}
 
void solve() {
    cin >> n;
    graph.clear(); graph.resize(n + 1);
    for (int e = 1; e < n; e++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    guards.clear(); guards.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> guards[i];
    }
    cin >> q;
    queries.clear(); queries.resize(n + 1);
    for (int i = 0; i < q; i++) {
        int u, x;
        cin >> u >> x;
        queries[u].push_back(pii(x, i));
    }
    arr.clear();
    cumsum.clear();
    ans.clear(); ans.resize(q);
    dfs(1, 0);
    for (int i = 0; i < q; i++) {
        cout << ans[i] << endl;
    }
}
 
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++) {
        solve();
    }
}

[Hackerearth] OrOasis

 

Problem Link    : OrOasis 
Category        : Binary Search, Xor
Contest         : January Circuits '24

#include "bits/stdc++.h"
using namespace std;
// #define int     long long int
#define endl    '\n'
 
const int BITS = 31;
 
void solve() {
    int n;
    cin >> n;
    vector<int> nums(n);
    int total = 0;
    vector<vector<int>> cumBits(n, vector<int>(BITS));
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        total |= nums[i];
        for (int b = BITS - 1; b >= 0; b--) {
            bool val = (nums[i] >> b & 1);
            cumBits[i][b] = val;
            if (i - 1 >= 0) {
                cumBits[i][b] += cumBits[i - 1][b];
            }
        }
    }
    function<int(int, int)> GetOr = [&](int l, int r) {
        if (r >= n or l > r) {
            return 0;
        }
        int orsum = 0;
        for (int b = BITS - 1; b >= 0; b--) {
            int cnt = cumBits[r][b];
            if (l - 1 >= 0) {
                cnt -= cumBits[l - 1][b];
            }
            if (cnt) {
                orsum |= (1LL << b);
            }
        }
        return orsum;
    };
    int minlen = INT_MAX;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int lo = i;
        int hi = n - 1;
        int id = -1;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            int x = GetOr(i, mid);
            if (x == total) {
                id = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        if (id != -1) {
            int x = GetOr(i, id);
            int y = GetOr(0, i - 1) | GetOr(id + 1, n - 1);
            if (x ^ y) {
                continue;
            }
            int len = id - i + 1;
            if (len < minlen) {
                minlen = len;
                ans = 1;
            } else if (minlen == len) {
                ans++;
            }
        }
    }
    if (minlen >= n) {
        cout << -1 << endl;
    } else {
        cout << minlen << " " << ans << endl;
    }
}
 
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++) {
        solve();
    }
}

Monday, April 8, 2019

[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

  1. #include <bits/stdc++.h>  
  2.   
  3. using namespace std;  
  4.   
  5. #define ll            long long int  
  6.   
  7. ll dp[70][70];  
  8. bool memoize[70][70];  
  9. int a[70];  
  10.   
  11. ll m, k;  
  12.   
  13. ll solve(int pos, int one = 0, bool flag = 1, bool take = 0)  
  14. {  
  15.       if (pos < 0) return one == k;  
  16.       ll &ret = dp[pos][one];  
  17.       bool &mem = memoize[pos][one];  
  18.       if (!flag && take && mem) return ret;  
  19.       int loop = 1;  
  20.       if (flag) loop = a[pos];  
  21.       ll sum = 0;  
  22.       for (int i = 0; i <= loop; i++)  
  23.       {  
  24.             if (!take && i == 0) sum += solve(pos-1, 0, 0, 0);  
  25.             else sum += solve(pos-1, one + i, flag & i == a[pos], 1);  
  26.       }  
  27.       if (!flag && take) mem = 1, ret = sum;  
  28.       return sum;  
  29. }  
  30.   
  31. ll digit_dp(ll num)  
  32. {  
  33.       int len = 0;  
  34.       while (num) a[len++] = num % 2, num /= 2;  
  35.       return solve(len-1);  
  36. }  
  37.   
  38. int main()  
  39. {  
  40.       ios_base::sync_with_stdio(false);  
  41.       cin.tie(NULL);  
  42.       cout << fixed << setprecision(15);  
  43.       #ifndef ONLINE_JUDGE  
  44.             freopen("in.txt", "r", stdin);  
  45.       #endif // ONLINE_JUDGE  
  46.   
  47.       cin >> m >> k;  
  48.       ll lo = 1;  
  49.       ll hi = 1e18;  
  50.       ll ans = -1;  
  51.       while (lo <= hi)  
  52.       {  
  53.             ll mid = lo + (hi - lo) / 2;  
  54.             ll cnt = digit_dp(mid*2) - digit_dp(mid);  
  55.             if (cnt == m)  
  56.             {  
  57.                   ans = mid;  
  58.                   hi = mid - 1;  
  59.             }  
  60.             else if (cnt < m) lo = mid + 1;  
  61.             else hi = mid - 1;  
  62.       }  
  63.       assert(ans != -1);  
  64.       cout << ans;  
  65. }