HackerEarth A binary palindrome problem solution

In this HackerEarth A binary palindrome problem solution You are given a number N. In one operation, you can either increase the value of N by 1 or decrease the value of N by 1. Determine the minimum number of operations required (possibly zero) to convert number N to a number P such that binary representation of P is a palindrome.

HackerEarth A binary palindrome problem solution.

#include <bits/stdc++.h>
#define lli long long

using namespace std;

vector <lli> palindromes;

lli cal(string p)
{
    string p1 = p;
    reverse(p1.begin(), p1.end());
    p += p1;
    lli ans = 0;
    for ( int i = p.size() - 1; i >= 0; i-- ) {
        if ( p[i] == '1' ) ans += (1LL << ((int)p.size() - 1 - i));
    }
    return ans;
}

lli cal1(string p)
{
    string p1 = p;
    reverse(p1.begin(), p1.end());
    p1.erase(p1.begin());
    p += p1;
    int ans = 0;
    for ( int i = p.size() - 1; i >= 0; i-- ) {
        if ( p[i] == '1' ) ans += (1LL << ((int)p.size() - 1 - i));
    }
    return ans;
}

void f(int idx, string p, int flag)
{
    if ( idx == 16 ) {
        palindromes.push_back(cal(p));
        if ( !p.empty() ) palindromes.push_back(cal1(p));
        return;
    }
    if ( flag == 0 ) {
        f(idx + 1, p, 0);
        f(idx + 1, p + "1", 1);
    }
    else {
        f(idx + 1, p + "0", 1);
        f(idx + 1, p + "1", 1);
    }
}

int main()
{
    int t;
    lli idx, ans, n;
    cin >> t;
    assert(t >= 1 && t <= 100000);

    f(0, "", 0);
    sort(palindromes.begin(), palindromes.end());
    
    while ( t-- ) {
        cin >> n;
        assert(n >= 0 && n <= 2000000000);
        idx = lower_bound(palindromes.begin(), palindromes.end(), n) - palindromes.begin();
        ans = palindromes[idx] - n;
        if ( idx > 0 ) ans = min(ans, n - palindromes[idx - 1]);
        cout << ans << endl;
    }
    
    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 10, maxl = 1e5, lg = 20;
int n, occ[maxn][maxl];
//set<string> bag;
string s;
string p[maxn];
int l[maxn], r[maxn];
int rnk[lg][maxl], whenUni[maxl], per[maxl], L;
int lcp(int i, int j){
    int ans = 0;
    for(int k = L - 1; k >= 0 && i < s.size() && j < s.size(); k--)
        if(rnk[k][i] == rnk[k][j])
            i += 1 << k, j += 1 << k, ans += 1 << k;
    return ans;
}
void buildSA(string &s){
    int n = s.size();
    int l = 0;
    auto cmp = [&l, &n](int i, int j){
        if(rnk[l][i] != rnk[l][j])
            return rnk[l][i] < rnk[l][j];
        i += 1 << l, j += 1 << l;
        return i < n && j < n ? rnk[l][i] < rnk[l][j] : i > j;
    };
    for(int i = 0; i < n; i++)
        rnk[0][i] = s[i];
    iota(per, per + n, 0);
    while(1 << l <= n){
        sort(per, per + n, cmp);
        int c = 0;
        for(int i = 0; i < n; i++){
            rnk[l + 1][ per[i] ] = c;
            c += cmp(per[i], per[i + 1]);
        }
        l++;
    }
    L = l;
    {
        stack<int> s;
        for(int i = 0; i < n; i++){
            while(s.size() && s.top() > per[i])
                s.pop();
            if(s.size())
                whenUni[ per[i] ] = max(whenUni[ per[i] ], lcp(per[i], s.top()));
            s.push(per[i]);
        }
        s = stack<int> ();
        for(int i = n - 1; i >= 0; i--){
            while(s.size() && s.top() > per[i])
                s.pop();
            if(s.size())
                whenUni[ per[i] ] = max(whenUni[ per[i] ], lcp(per[i], s.top()));
            s.push(per[i]);
        }
    }
}
bool okl(const string &s){
    for(int i = 0; i < n; i++)
        if(count(p[i], s) < l[i])
            return 0;
    return 1;
}
bool okr(const string &s){
    for(int i = 0; i < n; i++)
        if(count(p[i], s) > r[i])
            return 0;
    return 1;
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> s >> n;
    buildSA(s);
    for(int i = 0; i < n; i++){
        cin >> p[i] >> l[i] >> r[i];
        int f[p.size() + 1] = {};
        int k = 0;
        for(int i = 1; i < p.size(); i++){
            while(k && p[k] != p[i])  k = f[k];
            if(p[k] == p[i])  k++;
            f[i + 1] = k;
        }
        k = 0;
        int ans = 0;
        for(int i = 0; i < s.size(); i++){
            while(k && p[k] != s[i])  k = f[k];
            if(p[k] == s[i])  k++;
            if(k == p.size()){
                ans++;
                k = f[k];
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < s.size(); i++)
        if(okl(s.substr(i, 1))){
            whenUni[i] += i;
            int lo = i, hi = s.size();
            while(hi - lo > 1){
                int mid = (lo + hi) / 2;
                (okr(s.substr(i, mid - i)) ? hi : lo) = mid;
            }
            if(!okr(s.substr(i, hi - i)))
                hi++;
            int f = max(whenUni[i] + 1, hi);
            lo = i + 1, hi = s.size() + 1;
            while(hi - lo > 1){
                int mid = (lo + hi) / 2;
                (okl(s.substr(i, mid - i)) ? lo : hi) = mid;
            }
            ans += max(0, lo - f + 1);

        }
    cout << ans << 'n';
}

coding problems