Be careful of precision errors!

For rajat to pass it should answer should be max(marks to get 4CG, marks to pass C3). which is max(marks to score 4CG,12). Let marks required to pass C3 is $$$c$$$ so following conditions should be satisfied

which can be re-written as

The above inequality can be modified to the following form to remove fractional values:

We will use the following property to avoid dealing with float values as they are prone to precision errors:

So the final answer should be

Alternatively, we can iterate from 12 to 40 while checking if the current value satisfies the passing criteria.

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

#define int long long

void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << max(12LL, (2 * c + 4) / 5 - a - b) << endl;
}

signed main() {
    
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();       
    }
    return 0;
}

Think of three case when last letter of given string is S , M and L

To solve this problem we will take three cases when input string last character is S Then we need to output in descending order. And if it is M then it should be placed after all small sized merch. And if it is L then need to simply arrange in ascending and output. For Implementation of this, in solution we used a comparator function in which we assigned a value to each string, k-XS represent (-k), M represents 0 and k-XL represents +k so simply we can sort in ascending order of assigned value which will give us required array.

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

int get(string &a) {
    int A = 0;
    if(a.size() == 1) A = 0;
    else {
        if(a.back() == 'S') A -= (a[0] - '0');
        else A += (a[0] - '0');
    }
    return A;
}

bool cmp(string &a, string &b) {
    if(get(a) < get(b)) return true;
    return false;
}

void solve(){
    int n; cin >> n;
    vector<string> s(n);
    for(auto &x: s) 
        cin >> x;
    sort(s.begin(), s.end(), cmp);
    for(auto &x: s) cout << x << " ";
    cout << "\n";
}   
 
int main() {
    int t; cin >> t;
    while(t--) solve();
}

find pattern

In the defined Fibonacci sequence $$$s$$$, initially established with $$$s_0$$$ = ‘0’ and $$$s_1$$$ = ‘1’, concatenating the last string with the second-to-last string yields alternating parity. Consequently, for $$$s_i$$$ , if $$$i$$$ is even, the parity of $$$s_i$$$ is even, and if $$$i$$$ is odd, the parity of $$$s_i$$$ is odd.

Upon observation, it's evident that the function $$$f(s)$$$ generates the Fibonacci sequence starting from $$$f(s_2)$$$ . Given the established fact that every third Fibonacci number is even, we can conclude that $$$f(s)$$$ is even for $$$s$$$ = $$$s_{2+3i}$$$ and odd otherwise .

Now we got parity for nth element of both $$$s$$$ and $$$f(s)$$$ , compare parity of both and answer .

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

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

#define int long long
#define pb push_back
#define ppb pop_back
#define MOD 1000000007;

const int N=1e5;


void solve(){
    int n;
    cin >> n;
    bool s = ((n%2)==0);
    bool fs = ((n%3)==2);

    if(s == fs){
       cout << "YES";
    }else cout << "NO";

    cout << endl;
}

signed main() {
    fastio();

    int t = 1;
    cin >> t;
    while(t--){
        solve();       
       }
    return 0;
}

prefix and suffix

For each delete query in this problem, deleting a substring from a string results in a new string consisting of a prefix and a suffix. To check whether $$$str$$$ occurs when prefix and suffix are combined we used array pre and suff. pre denotes elements of the string present until a specific prefix point of string $$$str$$$ and suff denotes elements in reverse present until a particular suffix point after deleting the substring Prefix array keep track of will which point of $$$str$$$ is subsequence of string till specific prefix point . suffix array does the same in reverse, noting the elements present in the reversed order

During each query, the code efficiently checks if the suffix point occurs before the prefix point in the precomputed arrays , this determines if $$$str$$$ is subsequence of remaining string or not

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

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

#define int long long
#define pb push_back
#define ppb pop_back
#define MOD 1000000007;

const int N=1e5;

void solve(){
    int m, n;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    int index = 0;
    s.insert(0, "0"); t.insert(0, "0");
    vector<int> pre(n + 1), suff(n + 2);
    for(int i = 1; i <= n; i++) {
        if(s[i] == t[index + 1] and index<m)
            index++;
        pre[i] = index;
    }
    suff.back() = index = t.size();
    for(int i = n; i > 0; i--) {
        if(s[i] == t[index - 1] and index>1) 
            index--;
        suff[i] = index;
    }
    int q;
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        if(suff[r + 1] - pre[l - 1] < 2)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}

signed main() {
    fastio();

    int t = 1;
    while(t--){
        solve();       
       }
    return 0;
}

Think of humans always moving in one direction say left or right.

Think of Applying Binary Search

Since we are asked for non-zero probability then we just need to show one single configuration of movement such that all spots get destroyed. we can think of all humans moving together to either left or right as if it is possible to destroy all spots by splitting then it will surely be possible to destroy by all humans moving in a specific direction.

Now Let's take this whole problem as $$$n$$$ sub-problem where answer to $$$ith$$$ problem is number humans to be deployed on $$$ith$$$ spot.

Now if we are able to destroy all spots by deploying $$$k$$$ number of humans then we will surely be able to do it by deploying $$$k+1$$$ people. Hence to solve this sub problem we will apply binary search on number of humans to be deployed, And to check for any value we will maintain one variable $$$buff$$$ denoting number of humans which can move to either of sites, use two pointers one pointing at left side of destroyed site and other at right side And if it is possible to destroy any site by placing $$$buff$$$ on it simply destroy it and in this way if we can destroy them all then $$$k$$$ value returns true and if both both sites i.e. left and right cannot be destroyed then function returns false.

#include<bits/stdc++.h>
using namespace std;
#define int long long int 
vector<int> a,b;
int n;
bool check(int key,int ind)
{
	int s=ind-1,e=ind+1;
	int buff=key+a[ind]; // extra people which can go to any site once their site is broken
	while(s!=-1 || e!=n)
	{
         int flag=0 ;// to check buff changes 
         if(s!=-1)
         {
         	if(a[s]+buff>=b[s]) 
         	{
         		buff+= a[s];
         		s--;
         		flag=1;
         	}
         }
         if(e!=n)
         {
         	if(a[e]+buff>=b[e])
         	{
         		buff+= a[e];
         		e++;
         		flag=1;
         	}
         }
         if(!flag) return 0;
	}
	return 1;
}

signed main()
{
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n;
		a.clear();b.clear();
		a.resize(n);b.resize(n);
		for(int i=0;i<n;i++) cin >> a[i];
		for(int i=0;i<n;i++) cin >> b[i];
		vector<int> ans(n);	
		for(int i=0;i<n;i++)
		{
			int lo=(b[i]-a[i]),hi=1e12;
			while(hi-lo>1)
			{
				int mid=(hi+lo)/2;
				if(check(mid,i))
				{
					hi=mid;
				}
				else
				{
					lo=mid+1;
				}
				if(check(lo,i)) ans[i]=lo;
				else ans[i]=hi;
			}
		}
		for(int i=0;i<n;i++)
		{
			cout << ans[i] << ' ';
		}
		cout << endl;
	}
}

Try to use DP to solve this problem.

Let $$$dp[i][p][q][turn]$$$ denote the probability of Rajat winning the game, where:

• $$$i$$$ denotes the number of turns left,
• $$$p$$$ denotes the parity of Rajat’s score,
• $$$q$$$ denotes the parity of Dr. S’s score, and
• $$$turn$$$ is 0 if it is Rajat’s turn and 1 if it is Dr. S’s turn.

Let $$$p_{\text{even}}$$$ and $$$p_{\text{odd}}$$$ denote the probabilities of landing \text{even} and \text{odd} elements, respectively, among the first $$$n - 1$$$ elements of $$$a$$$. We will consider the scenario where $$$a_n$$$ is rolled on the die separately.

The transitions will be as follows:

If it is Rajat’s turn, then there are 2 additional cases:

Case 1: When $$$a_n$$$ is odd,

$$$dp[i][p][q][turn] = p_{\text{even}} \cdot dp[i - 1][p][q][turn \oplus 1] + p_{\text{odd}} \cdot dp[i - 1][p \oplus 1][q][turn \oplus 1] + p_n \cdot dp[i - 1][p \oplus 1][q]$$$
$$$[turn]$$$

Case 2: When $$$a_n$$$ is even,

$$$dp[i][p][q][turn] = p_{\text{even}} \cdot dp[i - 1][p][q][turn \oplus 1] + p_{\text{odd}} \cdot dp[i - 1][p][q \oplus 1][turn \oplus 1] + p_n \cdot dp[i - 1][p][q][turn]$$$

Similarly, for Dr. S’s turn:

Case 1: When $$$a_n$$$ is odd,

$$$dp[i][p][q][turn] = p_{\text{even}} \cdot dp[i - 1][p][q][turn \oplus 1] + p_{\text{odd}} \cdot dp[i - 1][p][q \oplus 1][turn \oplus 1] + p_n \cdot dp[i - 1][p \oplus 1][q]$$$ $$$[turn]$$$

Case 2: When $$$a_n$$$ is even,

$$$dp[i][p][q][turn] = p_{\text{even}} \cdot dp[i - 1][p][q][turn \oplus 1] + p_{\text{odd}} \cdot dp[i - 1][p][q \oplus 1][turn \oplus 1] + p_n \cdot dp[i - 1][p][q][turn]$$$

where $$$p_n$$$ is the probability of rolling $$$n$$$.

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

#define MOD 1000000007
#define int long long

int binExp(int a, int b, int M){
    int ans = 1;
    while(b){
        if(b & 1)
            ans = (ans * 1LL * a) % M;
        a = (a * 1LL * a) % M;
        b >>= 1;
    }
    return ans;
}


void solve(){
    int n, k, even, odd = 0;
    cin >> n >> k;
    vector<int> v(n);
    for(int i = 0; i < n; i++) {
        cin >> v[i];
        if(v[i] & 1)
            odd++;
    }

    even = n - odd;
    int inv = binExp(n, MOD - 2, MOD);
    if(v.back() & 1)
        odd--;
    else
        even--;
    even *= inv; even %= MOD;
    odd *= inv; odd %= MOD;

    int dp[k + 1][2][2][2];
    memset(dp, 0, sizeof(dp));

    for(int p = 0; p < 2; p++) {
        for(int q = 0; q < 2; q++) {
            for(int turn = 0; turn < 2; turn++) {
                if(p * q == 0)
                    dp[0][p][q][turn] = 1;
            }
        }
    }

    for(int i = 1; i <= k; i++) {
        for(int p = 0; p < 2; p++) {
            for(int q = 0; q < 2; q++) {
                for(int turn = 0; turn < 2; turn++) {
                    dp[i][p][q][turn] += (even * dp[i - 1][p][q][turn ^ 1]) % MOD;

                    if(turn)
                        dp[i][p][q][turn] += (odd * dp[i - 1][p][q ^ 1][turn ^ 1]) % MOD;
                    else
                        dp[i][p][q][turn] += (odd * dp[i - 1][p ^ 1][q][turn ^ 1]) % MOD;

                    if(v.back() & 1) {
                        if(turn)
                            dp[i][p][q][turn] += (inv * dp[i - 1][p][q ^ 1][turn]) % MOD;
                        else
                            dp[i][p][q][turn] += (inv * dp[i - 1][p ^ 1][q][turn]) % MOD;
                    }
                    else 
                        dp[i][p][q][turn] += (inv * dp[i - 1][p][q][turn]) % MOD;

                    dp[i][p][q][turn] %= MOD;
                }
            }
        }
    }

    cout << dp[k][0][0][0] << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int tt = 1;
    cin >> tt;
    while(tt--){
        solve();
    }
    return 0;
}

Try to first solve if Rathi played optimally to increase the score, and Somani played optimally to decrease the score.

Try to use the above answer to calculate the expected score.

First let's see how the optimal choices will be made by Rathi and Somani. If Rathi trying to increase the score of the game and Somani is trying to decrease it.

Make a function $$$f$$$, which takes the parent of a subtree and return the score of that subtree if both played min-max game.

Store the optimal choices made by Rathi in an array — $$$next$$$, using the function $$$f$$$.

Now to calculate the expected score of a subtree rooted at $$$v$$$, we can define a function $$$g_v$$$.

Now, the answer will stored in $$$g_1$$$

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

#define int long long

const int mod = 1e9 + 7;
const int N = 2e5 + 10;

vector<int> adj[N];
int a[N];
int dp[N][2];
int dp1[N];
int vis[N];

const int MAXN = 2e5;
int SUMN = 0;

int pow_(int a, int p){
    if(p == 0) return 1;
    if(p&1){
        int k = a * pow_(a, p-1);
        k %= mod;
        return k;
    }
    int k = pow_(a, p/2);
    k *= k;
    k %= mod;
    return k;
}


int dfs(int v, int chance, int p){
    if(dp[v][chance] != -1) return dp[v][chance];
    if(chance&1){
        int ans = 1e18;
        for(auto &x: adj[v]){
            if(x == p) continue;
            ans = min(ans, a[x - 1] + dfs(x, chance^1, v));
        }
        if(ans == 1e18) ans = 0;
        return dp[v][chance] = ans;
    }
    int ans = 0;
    int next = -1;
    for(auto &x: adj[v]){
        if(x == p) continue;
        if(dfs(x, chance^1, v) + a[x - 1] > ans){
            next = x;
            ans = a[x - 1] + dfs(x, chance^1, v);
        }
        if(dfs(x, chance^1, v) + a[x - 1] == ans){
            if(x < next) {
                next = x;
            }
        }
    }
    dp1[v] = next;
    return dp[v][chance] = ans;
}

int solve(int v, int chance, int p){
    if(dp[v][chance] != -1) return dp[v][chance]; 
    if(chance&1){
        int ans = 0;
        int nodes = 0;
        for(auto &x: adj[v]){
            if(x == p) continue;
            ans += (a[x - 1] + solve(x, chance ^ 1, v)) % mod;
            ans %= mod;
            nodes++;
        }
        if(nodes == 0) return 0;
        int inv = pow_(nodes, mod - 2);
        ans *= inv;
        ans %= mod;
        return dp[v][chance] = ans;
    }
    if(dp1[v] == -1) return 0;
    return dp[v][chance] = ((a[dp1[v] - 1] +  solve(dp1[v], chance ^ 1, v)) % mod);
}

void clear(int n) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < 2; j++) dp[i][j] = -1;
        dp1[i] = -1;
        adj[i].clear();
    }
}

void chk(int v, int p) {
    assert(vis[v] == 0);
    vis[v] = 1;
    for(auto &x: adj[v]) {
        if(x == p) continue;
        chk(x, v);
    }
}

void solve() {
    int n; cin>>n;
    SUMN += n;
    clear(n + 5);
    for(int i = 0; i < n; i++) cin>>a[i], assert(a[i] <= 1e9 && a[i] >= 1);
    for(int i = 0; i < n - 1; i++){
        int a, b; cin>>a>>b;
        assert(a != b);
        assert(1 <= a && a <= n);
        assert(1 <= b && b <= n);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i = 1; i <= n; i++) vis[i] = 0;
    chk(1, -1);
    for(int i = 1; i <= n; i++) assert(vis[i] == 1);
    dfs(1, 0, -1);
    for(int i = 0; i <= n; i++) for(int j = 0; j < 2; j++) dp[i][j] = -1;
    cout<<(a[0] + solve(1, 0, -1))%mod<<"\n";
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); 
    int t; cin>>t;
    assert(t <= 1000);
    while(t--) solve();
    assert(SUMN <= MAXN);
}