Since there is a difference of 3 coins generated every day, the answer can be calculated using the formula $$$(a−b+2)/3$$$.

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int x,y;
        cin>>x>>y;
        cout<<(y-x+2)/3<<endl;
    }
}

Think about maintaining a running total of the money accumulated each day and compare it with the fee subtracted from this total.

To solve this problem efficiently, iterate through each day while keeping track of the maximum profit that can be obtained by subtracting the fee on that day from the accumulated amount.

Maintain a running total of the money accumulated each day and compare it with the fee subtracted from this total. To solve this problem efficiently, iterate through each day while keeping track of the maximum profit that can be obtained by subtracting the fee on that day from the accumulated amount. Time Complexity: $$$O(n)$$$

#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
void solve()
{
int initial,days;
cin>>initial>>days;
vector<int> stock,tax;
for(int i=0;i<days;i++)
{
int x;cin>>x;
stock.push_back(x);
}
for(int i=0;i<days;i++)
{
int x;cin>>x;
tax.push_back(x);
}
long long int max=initial,curr=initial;
 int pos=-1;
for(int i=0;i<days;i++)
{
curr=curr+stock[i];
if(curr-tax[i]>max)
{
max=curr-tax[i];
pos=i;
}
}
cout<<pos+1<<' '<<max;
cout<<endl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}

We are taking variable curr and max in long long int because maximum value of c, d, a[i] is $$$10^5$$$ so our calculation can go upto stage where all are $$$10^5$$$ in this case our variable curr need to store value of order $$$10^{10}$$$ which is out of range of int.

Answer is $$$-1$$$ only when $$$s[0] = 0$$$ (first character in string is 0), think about it.

Look at the positions of $$$1$$$ in the string and the corresponding position in the permutation. This part of the permutation is always sorted in ascending order.

If $$$s[0] = 0$$$, then no solution exists as first element of p is always maximum of $$$[p_1]$$$.

Else, A valid permutation is:

We iterate over the string in reverse. The last occurrence of $$$1$$$ has the maximum value in the entire array, the second last occurrence has the second highest value… We fill p accordingly.

With those values from $$$1$$$ to $$$n$$$ which are still left with us, we iterate in reverse over all the zeros then, using the same process. This creates a valid permutation always in $$$O(n)$$$ time.

#include<bits/stdc++.h>
using namespace std;
string s;
vector<int> v;
 int main() {
     ios_base::sync_with_stdio(false); 
     cin.tie(NULL);
     cout.tie(NULL);
     int t;
     cin>>t;
     while(t--){
     int n;
     cin>>n;
     cin>>s;
     v.resize(n);
     int c = n;
     if(s[0]=='0')
     cout<<-1<<endl;
     else{
     for(int i=n-1;i>=0;i--){
        if(s[i]=='1'){
            v[i] = c;
            c--;
        }}
     for(int i=n-1;i>=0;i--){
        if(s[i]=='0'){
            v[i] = c;
            c--;
        }}
     for(int i=0;i<n;i++)
     cout<<v[i]<<" ";
     cout<<endl;
        v.clear();
     }}
     return 0;
}

Think about the total no. of gaps available and check how we can distribute them.

Recall the concept of inverse modulo.

Let he atteds 1st class after x1 days, 2nd class after x2 days, 3rd class after x3 days and so on the kth class after xk days Let the days left after kth class be x(k+1)

Here total no. of gaps available are : $$$n-k$$$

so, $$$x1+x2+x3+....+xk+x(k+1) = n-k$$$;

where $$$x1>=0, x2>=1, x3>=1..... xk>=1$$$, $$$x(k+1) >= 1$$$

let $$$y1=x1$$$, $$$y2 = x2-1$$$, $$$y3=x3-1$$$,...... $$$yk = xk-1$$$, $$$y(k+1) = x(k+1)-1$$$

so $$$y1+y2+y3....+y(k+1) = (n-k-(k-1))$$$

solution for this equation is $$$(n-k+1) C k$$$

Now since no. can be too large we have to use the concept of inverse modulo

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

const long long MAXN = 366;
const long long MOD = 1e9 + 7;

long long fac[MAXN + 1];
long long inv[MAXN + 1];

long long power(long long x, long long y, long long p) {
    long long res = 1; 
    x = x % p;
    while (y > 0) {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

void factorial() {
    fac[0] = 1;
    for (long long i = 1; i <= MAXN; i++) { 
        fac[i] = fac[i - 1] * i % MOD; 
    }
    inv[MAXN] = power(fac[MAXN], MOD - 2, MOD);
    for (long long i = MAXN - 1; i >= 0; i--) {
        inv[i] = (inv[i + 1] * (i + 1)) % MOD;
    }
}

long long choose(long long n, long long r) {
    if(r > n) return 0ll;
    return (fac[n] * inv[r] % MOD * inv[n - r] % MOD) % MOD;
}

void solve(){
    int n, k;
    cin >> k >> n;

    if(k > (n + 1) / 2) cout << "0\n";
    else {
        n = (n - k + 1);
        cout << choose(n, k) << endl;
    }
}

signed main() {
    fastio();
    factorial();
    int t; cin >> t;
    while(t--)
        solve();
    
    return 0;
}

What is max OR possible? Take the whole array OR.

Prefix sum of set bits.

First, we find the maximum possible OR of the given array by taking the OR of the whole array in $$$O(n)$$$ time.

Now, we need to find the shortest subarray which will give the OR equal to the max OR found. There are many possible ways to achieve this, some of them are listed below:

1) One possible solution is using two loops to iterate over all subarrays and find the minimum subarray, but the complexity of this approach will be $$$O(n^2)$$$.

2) We can find the minimum subarray in $$$O(32 \cdot n \cdot \log n)$$$ using binary search and prefix sum. First, we store the frequency of set bits in a prefix sum 2D array of size $$$32 \cdot n$$$. Then, we do binary search ($$$\log n$$$) on the answer (from $$$1$$$ to $$$n$$$) to check if it is a possible answer or not. In the predicate function, we can brute force ($$$O(32 \cdot n)$$$) on all possible subarrays of that size. (See solution code for detailed predicate function)

3) We can further reduce the time complexity to $$$O(32 \cdot n)$$$ using the two-pointer method. (See code for this implementation)

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define endl "\n"
#define vl vector<ll>

bool good(vector<vl> &pf,ll m,ll maxx,ll n){
    for(ll i=m;i<=n;i++){
        ll sum = 0;
        for(ll j=0;j<32;j++){
            if((pf[j][i]-pf[j][i-m])>0){
                sum += (1ll<<j);
            }
        }
        if(sum==maxx)
            return true;
    }
    return false;
}

void solve()
{
    ll n;
    cin>>n;
    vl a(n);
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    
    ll maxx = 0;
    for(ll i=0;i<n;i++){
       maxx |= a[i];
    }

    vector<bitset<32>> v;
    for(ll i=0;i<n;i++){
        bitset<32> num(a[i]);
        v.pb(num);
    }
 
    vector<vl> pf(32,vl (n+1));
    for(ll i=0;i<32;i++){
        pf[i][0] = 0;
        for(ll j=0;j<n;j++){
            if(v[j][i]){
                pf[i][j+1] = pf[i][j] + 1;
            }
            else{
                pf[i][j+1] = pf[i][j];
            }
        }
    }

    ll l=1,r=n;
    while(r-l>1){
        ll m = l + (r-l)/2;
        if(good(pf,m,maxx,n)){
            r = m;
        }
        else{
            l = m + 1;
        }
    }

    if(good(pf,l,maxx,n)){
        cout<<l<<endl;
    }
    else{
        cout<<r<<endl;
    }
}


int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)
        solve();

    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define endl "\n"
#define vl vector<ll>

void solve()
{
    ll n;
    cin>>n;
    vl a(n);
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    
    ll maxx = 0;
    for(ll i=0;i<n;i++){
       maxx |= a[i];
    }

    vector<bitset<32>> v;
    for(ll i=0;i<n;i++){
        bitset<32> num(a[i]);
        v.pb(num);
    }
 
    vector<vl> pf(32,vl (n+1));
    for(ll i=0;i<32;i++){
        pf[i][0] = 0;
        for(ll j=0;j<n;j++){
            if(v[j][i]){
                pf[i][j+1] = pf[i][j] + 1;
            }
            else{
                pf[i][j+1] = pf[i][j];
            }
        }
    }

    ll l=0,r=0;
    ll orr = 0;
    ll ans = 1e18;
    while(l<n && r<n){
        orr |= a[r];
        while(orr==maxx && l<=r){
            ans = min((r-l+1),ans);
            if(l==r)break;
            l++;
            for(ll i=0;i<32;i++){
                if(v[l-1][i])
                if((pf[i][r+1] - pf[i][l]) == 0){
                    orr -= (1ll<<i);
                }
            }
        }
        r++;
    }
    cout<<ans<<endl;
}


int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)
        solve();

    return 0;
}

Can we think of finding the longest palindrome first and then removing $$$k$$$ characters greedily?

Does the constraints allow us to run a loop of $$$n^2$$$ .

Lets just reverse the problem and length of longest palindromic subsequence that could have been made from original $$$n$$$ letters be L ? now if $$$k$$$ <= $$$n-L$$$ then we can directly say that answer would be as for removing $$$k$$$ letters we will choose them from $$$n-L$$$ pile .

Now what if $$$k>n-L$$$ . How to remove from this subsequence ? We start with removing the middle and answer is always $$$n-k$$$ .

For finding the length of longest palindromic subsequence we can use dynamic programming.

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
int longestPalindromeSubseq(string s) {
        int n = s.size();
        string b(s.rbegin(), s.rend());
        int dp[n+1][n+1];
        memset(dp,0,sizeof(dp));
        for(int i =1; i<=n;++i){
            for(int j =1; j<=n;++j){
                if(s[i-1]==b[j-1]){
                    dp[i][j]=1+dp[i-1][j-1];
                }
                else{
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[n][n];
}
signed main() {
   int t ; cin >> t;
   while(t--){
     int n;
    cin >> n;
    int k;
    cin >> k;
    
    string s;
    cin >> s;
 
 
   
    int lpsLength = longestPalindromeSubseq(s);
    
 
    
   
    int remainingDeletions = k - (n - lpsLength);
    if(k<=n-lpsLength){
       cout << lpsLength << '\n';
    }
    else{
       int rem = lpsLength -(k - (n - lpsLength));
       cout << rem << '\n';
        
        
 
    }
   }
    return 0;
}

The original question was to also print the subsequence but latter it was discarded to maintain level of contest . Can you do so :).