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,penalty;
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;
penalty.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-penalty[i]>max)
{
max=curr-penalty[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;
}

Input Reading:

The function reads the initial investment amount initial and the number of days.

It then reads the amounts added each day into the vector stock and the withdrawal fees into the vector penalty.

Processing Each Day:

The function initializes max to the initial amount and curr to the initial amount as well. pos is set to -1 to indicate no optimal day found yet.

It iterates over each day, updating curr by adding the amount for that day from the stock array.

For each day, it checks if the profit after subtracting the fee (from the penalty array) is greater than the previously recorded maximum profit (max). If so, it updates max and sets pos to the current day index.

Output:

After processing all days, the function outputs the best day to withdraw (pos + 1 because days are 1-indexed) and the maximum profit. If no profitable day is found (pos remains -1), it outputs 0 and the initial amount, indicating Hridyansh should not invest.

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 \gt =0, x2 \gt =1, x3 \gt =1..... xk \gt =1$$$, $$$x(k+1) \gt = 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 \gt 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 :).

For n=4, sequence will be 2,3,3,2.

For n=5, sequence will be 2,3,4,2,3,4.

Think of parities.

It’s very clear that we can’t check rooms randomly.

Approach:

We will always assume that the thief is in an even-numbered room (why not an odd-numbered one?).

So, we will start checking from the 2nd room. If we find him, that's good. Otherwise, if he was in an even-numbered room and we checked the 2nd room, it means now he is in an odd-numbered room, and he can’t go to room 1. Similarly, we will go up to the $$$(n-2)$$$ th room, each time eliminating one room.

When we check the $$$(n-2)$$$ th room and don’t find the thief, we can be assured that he was in room $$$n$$$ ( Why ? ) at that time and must have moved to room $$$n-1$$$. At this point, we will catch him.

However, this approach assumes that the thief was initially in an even-numbered room. If our assumption is wrong, we won’t be able to catch the thief in the $$$(n-1)$$$ th room.

But this process is not a waste. Now we know whether he is in an odd-numbered room or an even-numbered room. (How?) If he is in an even-numbered room, we will repeat the procedure.

If he is in an odd-numbered room, we will start from the last odd-numbered room (but why not from room $$$1$$$? Even the question demanded the lexicographically smallest element).

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

void solve() {
    int n;
    cin>>n;
    if(n==1) {
        cout<<1<<" "<<60<<endl;
        cout<<1;
    }
    else if(n==2) {
        cout<<2<<" "<<135<<endl;
        cout<<1<<" "<<1;
    }
    else {
        cout<<2*(n-2)<<" ";
        int x=2*(n-2);
        int y=x-1;
        cout<<x*60+y*15<<endl;
        if(n%2!=0) {
            for (int i = 2; i < n; i++)
            {
                cout<<i<<" ";
                /* code */
            }
            for (int i = 2; i < n; i++)
            {
                cout<<i<<" ";
                /* code */
            }
        }
        else {
            for (int i = 2; i < n; i++)
            {
                cout<<i<<" ";
                /* code */
            }
            for (int i = n-1; i >= 2; i--)
            {
                cout<<i<<" ";
                /* code */
            }
        }
    }
}




/*----------------------------------------------------------------------------------*/




int32_t main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
        cout << "\n";
    }
    return 0;
}

Notice constraints on elements of array.

You can use ones and zeros to represent if an index has been deleted or not.

You have update a point in a range . Which data structure can be used?

Here, Fenwick Tree(BIT) could be used (alternative can be ordered set or segment trees). Here, constraint on elements of $$$a$$$ is $$$1 \lt =element \lt =n$$$ where max value of can be $$$2\cdot10^5$$$ . So, we can use an array of n+1 length to store frequency of each element but there is a catch we have to work in a range so make this frequency array a BIT . Now, for index use an array of n+1 elements as a BIT , initialize all elements except 0 with value 1 which represent this value is still present in array. In each query, use binary search to find where the index prefix sum is equal to given number x . Now update BIT of index -1 where you find $$$x^{th}$$$ index . Now use update BIT on frequency array to decrease value found at $$$x^{th}$$$ index by 1 . Use binary search again to find median element in frequency BIT .

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

void update(int i,int val,int n,vector<int> &bit){
    while(i<=n){
        bit[i] += val;
        i += (i & (-i));
    }
}

int query(int i,int n,vector<int> &bit){
    int ans=0;
    while(i>0){
        ans += bit[i];
        i -= (i & (-i));
    }
    return ans;
}

int binary_mid(int val,int n,vector<int> &bit){
    int ans = INT_MAX;
    int l = 1 , h = n;
    while(l<=h){
        int mid = l + (h - l)/2;
        if(query(mid,n,bit)>=val){
            ans = min(ans,mid);
            h = mid - 1;
        }
        else {
            l = mid +1;
        }
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    
    int test;cin >> test;
    while(test--){
        int n,q; cin>> n >> q;
        vector<int> v(n+1,0),bit(n+1,0),freq(n+2,0);
        for(int i=1;i<=n;i++){
            cin >> v[i];
            update(i,1,n,bit);
            update(v[i],1,n,freq);
        }
        int size = n;
        while(q--){
            int x; cin >> x;
            int ans = binary_mid(x,n,bit);
            update(v[ans],-1,n,freq);
            update(ans,-1,n,bit);
            size--;
            int pri = binary_mid((size+1)/2,n,freq);
            cout << pri << " ";
        }
        cout << endl;
    }
}