What is minimum number of chocolates Kikazaru and Iwazaru can get?

The minimum amount of chocolates that Kikazaru can get is $$$2$$$. And Iwazaru can get minimum $$$1$$$ chocolates.

Which leaves Mizaru with $$$n-3$$$ chocolates at maximum. Which should be greater than both Kikazaru(2) and Iwazaru(1).

So, $$$n-3>2$$$ which gives $$$n>5$$$ to divide such that all conditions are met.

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

typedef long long ll;

void solve()
{
    ll n;
    cin>>n;
    if(n>=6) cout<<"YES"<<endl;
    else     cout<<"NO"<<endl;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0); 
    int t; cin>>t; 
    while(t--) solve();
}

We can modify the problem by arranging all the rooms in a line (total $$$n \cdot m$$$) rooms. Ramu comes downstairs when he has exhausted all the $$$k$$$ packets. So he has to come back after delivering to every $$$k$$$ rooms. He has to make total $$$\left \lceil{\frac{n \cdot m}{k}}\right \rceil$$$ trips for delivery. Also the final time he comes back should not be counted. So total times he has to come back is $$$\left \lceil{\frac{n \cdot m}{k}}\right \rceil$$$ — $$$1$$$.

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

#define int long long

void solve(int tc)
{
     int n,m,k; cin >> n >> m >> k;
     int x = n*m;
     int y = (x-1)/k + 1;
     cout << y-1 << endl;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t=1; cin>>t;
    for(int i=1; i<=t; i++)
    solve(i);
} 

Consider that the original weights are $$$a_1, a_2, a_3, a_4$$$ and $$$a_5$$$ in increasing order $$$(a_1 \leq a_2 \leq a_3 \leq a_4 \leq a_5)$$$. Next, sort the given 10 weights so that they are also in increasing order. Let’s try to make some observations now.

$$$w_{10}$$$ is the heaviest which means it is the combination of $$$a_4$$$ and $$$a_5$$$ $$$(w_{10} = a_4+a_5)$$$. Similarly $$$w_1 = a_1 + a_2$$$. Next we can see that the summation of all the weights would be $$$4(a_1+a_2+a_3+a_4+a_5)$$$, let's call it $$$s$$$. Thus, we can see that $$$a_3 = s - w_1 - w_{10}$$$.

Lastly, the most important observation to be made is what $$$w_2$$$ can be. If you will just try to do some checks you will realise it can’t be anything else but $$$a_1+a_3$$$. Thus $$$w_2 = a_1+a_3$$$ using which we can get $$$a_1$$$ and hence $$$a_2$$$. Similarly we can see $$$w_9 = a_3+a_5$$$ using which we can also get $$$a_5$$$ and hence $$$a_4$$$.

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

void solve()
{
    vector<int> a(10);
    for(int i=0; i<10; i++)
        cin >> a[i];

    sort(a.begin(),a.end());

    int sum = 0;
    for(int i=0; i<10; i++)
        sum += a[i];

    vector<int> ans(5);
    ans[2] = sum / 4 - a.front() - a.back();

    ans[0] = a[1] - ans[2];
    ans[1] = a[0] - ans[0];

    ans[4] = a[8] - ans[2];
    ans[3] = a[9] - ans[4];

    for(int i=0; i<5; i++)
        cout << a[i] << ' ';
    cout << endl;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0); 
    int t; cin>>t; 
    while(t--) solve();
}

If you are just starting CP the problem might feel a bit tricky, but if you have solved some Dynamic Programming problem you can do it pretty easily.

Consider the given number as a string of length $$$m$$$ $$$(a_1,...,a_m)$$$. We define $$$dp_i$$$ to be the number of possible Passwords (strings) that would convert to the code $$$a_1,...,a_i$$$.

We can clearly see that $$$dp_1=1$$$ and $$$dp_0=1$$$. Next, we define the transition. We can definitely change the $$$i^{th}$$$ number $$$a_i$$$ to a character so $$$dp_i=dp_{i-1}$$$. Additionally, we will see if it's possible to convert the last $$$2$$$ numbers into characters. Thus if $$$w = a_{i-1} \cdot 10 + a_i$$$ and $$$w>9$$$ and $$$w<26$$$, then we add $$$dp_{i-2}$$$ to $$$dp_{i}$$$ as well. Thus our final answer would be $$$dp[n]$$$.

/* AdC_AB2 */

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target("avx2")

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define endl "\n"
#define sz(a) (int)a.size()

const ll mod=998244353;
const ll N=200005;

void solv()
{
    string s;
    cin>>s;
    ll n = s.size();
    vector<ll> a(n+1);
    a[0]=1;
    for(ll i=0; i<n; i++)
    {
        a[i+1] = a[i];
        if(i>0   &&   ((s[i-1]=='1')||(s[i-1]=='2' && s[i]<='5')))
            a[i+1] += a[i-1];
        a[i+1] %= mod;
    }
    cout<<a[n]<<endl;
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll tc=1;
    cin>>tc;
    for(ll cc=1;cc<=tc;cc++)
    {
        solv();
    }
    return 0;
}

First, if the total number of orders summed over all the students is less than or equal to $$$m$$$, then all the orders are completed.

In case the number of orders is greater than $$$m$$$, we can sort the students by the number of orders they wish to place. Starting from the smallest, we iterate over these numbers and find the number of times the queue is completely passed over, say $$$h$$$, and subtract the orders required to do so from $$$m$$$.

Following this, any student with less than or equal to $$$h$$$ orders will definitely not stay in the queue after $$$m$$$ orders. The remaining students can be inserted into a new queue. The remaining orders can be dealt with by iterating over each of these by either sending the students at the front to the back if $$$a_i > h + 1$$$ and removing them from the queue otherwise.

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
void solve()
{
    int n, k;
    cin >> n >> k;
 
    vector<int> a;
    for(int i=0; i<n; i++) {int o; cin>>o; a.emplace_back(o);}
 
    int sum = 0;
    for(int i=0; i<n; i++)
        sum += a[i];
    
    if (sum <= k)
    {
        cout << "Completed" << endl;
        return;
    }
 
    vector<int> b = a;
    sort(b.begin(),b.end());
    int h = 0;
 
    for(int i=0; i<n; i++)
    {
        if (k < (b[i] - h) * (n - i))
        {
            h += k / (n - i);
            k -= k - k % (n - i);
            break;
        }
 
        k -= (b[i] - h) * (n - i);
        h = b[i];
    }
 
    queue<int> q;
 
    for(int i=0; i<n; i++)
        if (a[i] > h)
            q.push(i);
 
    for(int i=0; i<k; i++)
    {
        int tp = q.front();
        q.pop();
 
        if (a[tp] > h + 1)
            q.push(tp);
    }
 
    while (!q.empty())
    {
        int tp = q.front();
        q.pop();
        cout << tp + 1 << ' ';
    }
    cout << endl;
}
 
 
int32_t main()
{
    ios_base::sync_with_stdio(false);  cin.tie(0);  cout.tie(0);
    solve();
}

Do we really have to focus on all subarrays? Can we just focus on some $$$k$$$ elements?

Max element in array can only be till $$$10^6$$$.

We can rearrange elements of the array anyway we like so we just need to find $$$k$$$ elements in the array which give max GCD and then we can put them in one continuous subarray.

We can precompute all factors of all numbers from 1 to $$$10^6$$$. That can be done in $$$\sqrt{x}$$$ for each number $$$x$$$ but it will be $$$O(n\sqrt{n})$$$ which will give TLE. But we can use algorithm similar to sieve of Eratosthenes and for each $$$i$$$ we run second loop and add $$$i$$$ as a factor for all multiples of $$$i$$$. This will have complexity of $$$O(nlog(n))$$$.

Now for $$$i$$$ to be GCD of $$$k$$$ elements, it has to be factor of at least $$$k$$$ elements in the array. So we can make a frequency array, and for each element of array we can increase frequency of all of its factors. Now for each $$$k$$$, we need to find max element with frequency greater than equal to $$$k$$$. This can take $$$O(n*M^{\frac{1}{3}})$$$ where $$$M$$$ is max element in the array.

We can also precompute answer for each $$$k$$$. We can see that if all $$$j>i$$$ have frequency $$$freq[j]<freq[i]$$$ then $$$k=freq[i]$$$ will have answer $$$i$$$.

So we can make a answer array. If all elements greater than $$$i$$$ has less frequency than $$$freq[i]$$$ and $$$j$$$ is largest element with frequency $$$freq[j]>freq[i]$$$ then all $$$k$$$ from $$$freq[i]$$$ to $$$freq[j]-1$$$ will have $$$i$$$ as answer. We can start from $$$10^6$$$ and keep track of max frequency so far and second max frequency then we can fill in values [second_max+1,max] as we find new_max and update second max and max accordingly which can be done in $$$O(n)$$$.

Now we can answer for each $$$k$$$ in $$$O(1)$$$.

/*
Mantra's code :)
*/

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target("avx2")

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

#define pub push_back
#define pob pop_back
#define ya cout<<"Yes\n"
#define na cout<<"No\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007
#define ff first
#define ss second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define precision(a) {cout << setprecision(a) << fixed;}

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x);
#endif

typedef int ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<ld> vld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
typedef set<int> si;
typedef set<ll> sll;
typedef set<pll> spll;
typedef vector<pair<int,int>> vpi;
typedef vector<pair<ll,ll>> vpll;
typedef tuple<ll,ll,ll> tll;
typedef vector<tll> vtll;

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>

using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

const int N=1000001;
vll p[N];

void solve() 
{
    ll n,q;
    cin>>n>>q;
    
    ll a[n];
    for(ll i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
   
    ll freq[N]={0};

    for(ll i=0;i<n;i++)
    {
        for(auto j:p[a[i]])
        {
            freq[j]++;
        }
    }
    freq[1]=n;

    ll ans[n+1];
    ll r=1;
    ll max=0;
    for(ll i=N-1;i>=1;i--)
    {
        if(freq[i]>max)
        {
            for(ll j=r;j<=freq[i];j++)
            {
                ans[j]=i;
            }
            max=freq[i];
            r=freq[i]+1;
        }
    }

    for(ll i=1;i<=q;i++)
    {
        ll x; 
        cin>>x;
        cout<<ans[x]<<"\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    #ifndef ONLINE_JUDGE
        freopen("Error.txt", "w", stderr);
    #endif

    for(ll i=2;i<N;i++)
    {
        for(ll j=i;j<N;j+=i)
        {
            p[j].pub(i);
        }
    }

    ll t=1;
    //cin>>t;

    auto start1 = high_resolution_clock::now();

    while(t--)
    {
        solve();
    }

    auto stop1 = high_resolution_clock::now();
    auto duration = duration_cast<milliseconds>(stop1 - start1);

    #ifndef ONLINE_JUDGE
        cerr << "Time: " << duration . count() << endl;
    #endif
}

Let us say at some round in the tournament, there are $$$N$$$ people in that round, and you have the $$$K^{th}$$$ smallest rank. So there are $$$L = K-1$$$ ranks lesser than you and $$$R = N-K$$$ ranks more than you in this round.

Claim: For an odd round, $$$L = R+1$$$ guarantees that you can win the tournament. For an even round, $$$R = L+1$$$ guarantees that you can win the tournament.

Just before the start of an odd round, let us say there are a total of $$$N$$$ people in that round, out of which $$$L$$$ people have rank less than you and $$$R$$$ people have rank more than you. In this round, player with greater rank wins. Note that for you to progress to the next round, $$$R > 0$$$. Else you can't clear this round.

1. The minimum value of L after this round will be $$$\lceil\frac{L}{2}\rceil$$$.

2. The maximum value of R after this round will be $$$\lfloor\frac{R}{2}\rfloor$$$.

This will occur when the people more than $$$K$$$ play among each other.

1. The maximum value of L after this round will be $$$min(\frac{N}{2} - 1, L)$$$.

2. The minimum value of R after this round will be $$$max(0, \frac{N}{2} - 1 - L)$$$.

This will occur when the people less than $$$K$$$ play with people greater than $$$K$$$ and defeat them. There are to be a total of $$$\frac{N}{2} - 1$$$ winners (excluding you) and any person in $$$L$$$ can beat a person in $$$R$$$.

A symmetric analysis can be done for the even rounds.

We will follow a greedy approach to solve this problem. Let us assume initially $$$L < R$$$.

In each round, we will greedily go for the moves that minimize $$$R$$$. If after some odd round we get $$$L > R+1$$$ ,then it is possible to get $$$L = R+1$$$ after this round. Hence from Lemma, we can win.

[Initially we were at $$$L < R$$$, we played left optimally and managed to get $$$L > R+1$$$. So we can modify our moves and get $$$L = R+1$$$ after this round.]

Similarly if we get $$$L+1 > R$$$ after an even round, then it is possible to get $$$L = R+1$$$ after this round. Hence from Lemma, we can win.

If we can never attain $$$L+1 > R$$$, then greedily going for the moves that minimize $$$R$$$ will give us the maximum rounds you can play in the tournament [since we are always trying to reduce the value of $$$R$$$ in the above method].

We can apply a similar logic for the other cases as well.

Time Complexity: $$$O(log N)$$$ per test case.

/* AdC_AB2 */

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target("avx2")

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define endl "\n"
#define sz(a) (int)a.size()

const ll mod=1000000007;
const ll N=200005;

ll max(ll a, ll b)
{
    if(a>b)
        return a;
    else
        return b;
}

ll min(ll a, ll b)
{
    if(a<b)
        return a;
    else
        return b;
}

void solv()
{
    ll n,k;
    cin>>n>>k;
    ll ppl = 1LL<<n;
    ll l = k-1, r = ppl-k;

    ll ans=0, rnd=1;
    if(l>r)                 //Left side more, so max right part
    {
        while(ans<n)
        {
            if(rnd%2==1)
            {
                if(!r)  break;      //r needed to kill
                l = (l+1)/2;        //min l
                r = (r-1)/2;        //max r
                ppl /= 2;
                ans++;

                if(r>=l-1) ans=n;   //r >= l-1 ==> we can attain X 1 X-1 scene => win
            }
            else
            {
                l = max(0,ppl/2 - (r+1)); //min out l
                r = min(ppl/2-1,r);     //max out r
                ppl /= 2;
                ans++;

                if(r>l) ans=n;      //r exceeds l ==> we can attain X-1 1 X scene => win
            }
            rnd++;
        }
        cout<<ans<<endl;
    }
    else                            //r > l
    {
        while(ans<n)
        {
            if(rnd%2==1)
            {
                r = max(0,ppl/2 - (l+1));     //min out R
                l = min(ppl/2-1, l);        //max out L's win
                ppl /= 2;
                ans++;

                if(l>r) ans=n;              //L exceeds R => we can attain X 1 X-1 => win
            }
            else
            {
                if(!l)  break;          //L needed to kill
                r = (r+1)/2;            //min out R
                l = (l-1)/2;            //max out L
                ppl /= 2;
                ans++;

                if(l-1>=r) ans=n;          //l-1 >= r ==> we can attain X-1 1 X scene => win
            }
            rnd++;
        }
        cout<<ans<<endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll tc=1;
    cin>>tc;
    for(ll cc=1;cc<=tc;cc++)
    {
        solv();
    }
    return 0;
}

Let $$$f(n)$$$ $$$=$$$ $$$\sum_{k=1}^{n} F(n,k), \quad g(n)$$$ $$$=$$$ $$$\sum_{k=1}^{n} G(n,k)$$$.

$$$f(n)$$$ denotes the number of ways of partitioning the students into multiple non-empty floors (following the warden rules that higher roll no. person goes to higher floor) and assigning a representative to each floor.

Let us say we know $$$f(i)$$$ from $$$i=1$$$ to $$$n-1$$$. Let us say our hostel has $$$n-1$$$ people right now, and we are looking to add the $$$n^{th}$$$ person. Either of these 2 things can happen:

1. $$$n$$$ is part of the last floor, but is not the representative of this floor. Number of cases = $$$1 \cdot f(n-1)$$$.

2. $$$n$$$ is the leader of the floor he is in. In this case, let us say that $$$n$$$'s floor has $$$x$$$ members (including $$$n$$$). This means the first $$$n-x$$$ members are free to do as they please.

Number of ways here = $$$1 + \sum_{x=1}^{n-1} f(n-x)$$$

[we are adding $$$1$$$ to include the case where all members are in the same floor as $$$n$$$, and $$$n$$$ is the floor rep of this floor].

Hence,

From (1),

From (2) & (3),

We want your crush (hereafter called $$$m$$$) to be the representative of her floor. Let us say we include $$$x$$$ people to the left of $$$m$$$ [i.e. $$$m-1, m-2, ..., m-x$$$] to the same floor as $$$m$$$. For the rest of the $$$m-x-1$$$ people, number of ways of arranging them in the below floors = $$$f(m-x-1)$$$. [if $$$m-x=1$$$ then number of ways = $$$1$$$ ]

Let us include $$$y$$$ people to the right of $$$m$$$ [i.e. $$$m+1, m+2, ..., m+y$$$] to the same floor as $$$m$$$. Note that the choices of $$$x$$$ and $$$y$$$ are independent, and varying $$$x$$$ and $$$y$$$ over all possible values will give us $$$g(n)$$$.

For the rest of the $$$n-(m+y)$$$ people, number of ways of arranging them in the above floors = $$$f(n-(m+y))$$$. [if $$$m+y=n$$$ then number of ways = $$$1$$$ ]

From (3) & (4),

We use Binary Exponentiation to compute $$$f(n)$$$ using the recursion. GFG page on Matrix Exponentiation

Fun Note: This is the same recursive relation for alternating terms of the Fibonacci series:

Hence, $$$f(n) = Fib(2n)$$$ for $$$n > 0$$$. $$$\quad \quad$$$ [Fib(1) = 1, Fib(2) = 1, Fib(3) = 2,...]

In this case, $$$g(n) = Fib(2m-1) \cdot Fib(2(n-m)+1)$$$.

/* AdC_AB2 */

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target("avx2")

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define endl "\n"
#define sz(a) (int)a.size()

const ll mod=1000000007;
const ll N=200005;

void mat_mul(ll a[2][2], ll b[2][2])
{
    ll c[2][2];
    c[0][0] = a[0][0]*b[0][0] + a[0][1]*b[1][0];
    c[0][1] = a[0][0]*b[0][1] + a[0][1]*b[1][1];
    c[1][0] = a[1][0]*b[0][0] + a[1][1]*b[1][0];
    c[1][1] = a[1][0]*b[0][1] + a[1][1]*b[1][1];

    a[0][0] = c[0][0]%mod;
    a[0][1] = c[0][1]%mod;
    a[1][0] = c[1][0]%mod;
    a[1][1] = c[1][1]%mod;
}

ll Fib(ll nnn)
{
    if(nnn==0)      return 0;

    ll result[2][2] = {{1,0},{0,1}};
    ll aaa[2][2] = {{0,1},{1,1}};
    while(nnn)
    {
        if(nnn%2==1)    mat_mul(result,aaa);
        mat_mul(aaa,aaa);
        nnn/=2;
    }

    return result[1][0]%mod;
}

/**Takes a&b as input and Returns : The power (a,b), (a^b)%mod **/
ll Power(ll aaa,ll bbb)
{
ll result=1; aaa%=mod;
while(bbb) { if(bbb%2==1) result*=aaa; aaa*=aaa; aaa%=mod; result%=mod; bbb/=2; }
return result;
}

/** It give the modulo inverse of a, (1/a)%mod **/
ll Mod_Inv(ll aaa)
{
aaa%=mod; aaa=Power(aaa,mod-2); return aaa;
}

void solv()
{
    ll n,k;
    cin>>n>>k;
    ll denom = Fib(2*n);                        //Total cases
    ll l = k-1, r = n-k;
    ll num = (Fib(2*l+1)*Fib(2*r+1))%mod;       //Where crush is captain
    ll ans = num*Mod_Inv(denom);
    ans %= mod;
    cout<<ans<<endl;
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll tc=1;
    cin>>tc;
    for(ll cc=1;cc<=tc;cc++)
    {
        solv();
    }
    return 0;
}