What if the meeting location is fixed?

If the meeting location is fixed, the answer is max(the number of people to the left of that position, the number of people to the right of that position.

This can be solved in $$$O(n^2)$$$ by iterating through all position that has at least one person on it. This problem can also be solved in $$$O(n\log n)$$$ by sorting and setting the meeting position to the median of all positions.

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

	int t = 1;
	cin >> t;
    while(t-->0)
    {
        int n;
        cin >> n;

        vi a(n);
        for(int i=0; i<n; i++) cin >> a[i];

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

        int cnt = 0;
        for(int i=0; i<n; i++) if(a[i] != a[n-1-i]) cnt++;

        cout << cnt / 2 << "\n";
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

If we know the answer to the $$$i$$$-th position, what can we say about the answer to the $$$(i + 1)$$$-th position?

Suppose that we can just move the frosting freely. What is the maximum height the frosting can be while keeping it leveled?

Using the first two hints, we hypothesize that the answer for the first $$$i$$$ position of the cake is min(prefix average). Now, we will show that this is true by induction.

Base Case ($$$i = 1$$$): Since there is only one position, the answer is $$$a_1$$$.

Inductive Step: Suppose that the answer for the $$$i$$$ position is correct, now consider the first $$$i + 1$$$ positions. Since we have $$$\sum_{j=1}^{i+1} a_j$$$ units of frosting, the maximum height is $$$\frac{\sum_{j=1}^{i+1} a_j}{i + 1}$$$. Combining this with hint 1 and the inductive hypothesis, the answer is $$$\min_{k=1}^{i+1} \frac{\sum_{j=1}^{k+1} a_j}{k + 1}$$$.

This problem can be solved in $$$O(n)$$$.

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

	int t = 1;
	cin >> t;
    while(t-->0)
    {
        int n;
        cin >> n;

        vll a(n);
        for(int i=0; i<n; i++) cin >> a[i];

        ll ans = 1e9, sum = 0;

        for(int i=0; i<n; i++)
        {
            sum += a[i];
            ans = min(ans, sum / (i + 1));

            cout << ans << " ";
        }

        cout << "\n";
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

If we fixed the number of ambiverts that behave as introverts, what is the best way to assign who is introverted/extroverted?

It is always better to assign the prefix of ambiverts as introverts and the rest as extroverts, because if the number of introverts is fixed, then it is better to have introverts as early as possible.

For this subtask, it is possible to brute-force the number of ambiverts acting as introverts and find the answer in $$$O(n^2)$$$.

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

ll s, t;

ll eval(string &S, int m)
{
    ll T = 0, ans = 0;

    for(char c: S)
    {
        if(c == 'I')
        {
            if(T < t)
            {
                T++;
                ans++;
            }
        }
        else if(c == 'E')
        {
            if(ans < T * s) ans++;
        }
        else
        {
            if(m-->0)
            {
                if(T < t)
                {
                    T++;
                    ans++;
                }
            }
            else
            {
                if(ans < T * s) ans++;
            }
        }
    }

    return ans;
}

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

	int T = 1;
	cin >> T;
    while(T-->0)
    {
        int n;
        cin >> n >> t >> s;

        string S;
        cin >> S;

        int l = 0, r = 0;
        for(char c: S) if(c == 'A') r++;

        ll ans = 0;
        for(int i=l; i<=r; i++) ans = max(ans, eval(S, i));

        cout << ans << "\n";
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Assigning more ambiverts as introverts has a diminishing return.

Let $$$f(i)$$$ be the maximum number of people seated if the first $$$i$$$ ambiverts act as introverts. If $$$f(i + 1) \lt f(i + 2)$$$, what is the relation ship between $$$f(i)$$$ and $$$f(i + 1)$$$.

Let $$$f(i)$$$ be the maximum number of people seated if the first $$$i$$$ ambiverts act as introverts. We will first prove that if $$$f(i + 1) \lt f(i + 2)$$$, then $$$f(i) \lt f(i + 1)$$$.

Consider the situation where everyone is either an introvert or an extrovert, then we can simply use the greedy algorithm to solve this situation.

Suppose that $$$f(i + 1) \lt f(i + 2)$$$, then there are two possible scenarios:

Case 1: The $$$(i + 2)$$$-th ambivert is not seated when they are extroverted, but is seated when they are introverted.

Thus, when the first $$$i$$$ or $$$i + 1$$$ ambiverts are introverted, only $$$i$$$ or $$$i + 1$$$ tables are all seated, and the rest of the tables are empty. Thus, $$$f(i) \lt f(i + 1)$$$.

Case 2: The $$$(i + 2)$$$-th ambivert is seated when they are extroverted, and is still seated when they are introverted.

Since $$$f(i + 1) \lt f(i + 2)$$$, we know that someone previously unseated has to take the $$$(i+2)$$$-th ambivert's original seat, and since this person is originally unseated, this means the first $$$i + 1$$$ tables have to be fully seated. Therefore, $$$f(i) \lt f(i + 1)$$$.

Next, since we know that $$$f$$$ is strictly increasing before it plateaus/decreases. We can find the peak by finding the least $$$i$$$ that has $$$f(i) \geq f(i + 1)$$$.

Using binary search to find the optimal number of ambiverts acting as introverts reduces the time complexity of this problem down to $$$O(n \log n)$$$.

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

ll s, t;

ll eval(string &S, int m)
{
    ll T = 0, ans = 0;

    for(char c: S)
    {
        if(c == 'I')
        {
            if(T < t)
            {
                T++;
                ans++;
            }
        }
        else if(c == 'E')
        {
            if(ans < T * s) ans++;
        }
        else
        {
            if(m-->0)
            {
                if(T < t)
                {
                    T++;
                    ans++;
                }
            }
            else
            {
                if(ans < T * s) ans++;
            }
        }
    }

    return ans;
}

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

	int T = 1;
	cin >> T;
    while(T-->0)
    {
        int n;
        cin >> n >> t >> s;

        string S;
        cin >> S;

        int l = 0, r = 0;
        for(char c: S) if(c == 'A') r++;

        while(l < r)
        {
            int m = (l + r) / 2;

            int x = eval(S, m), y = eval(S, m + 1);

            if(x < y) l = m + 1;
            else r = m;
        }

        cout << eval(S, l) << "\n";
    }
}

If we fixed the number of ambiverts that behave as introverts, what is the best way to assign who is introverted/extroverted?

If there are no ambiverts, we can solve this problem greedily. How can we use the greedy algorithm here?

We will process each person one by one and keep track of the minimum and maximum number of tables occupied.

Let $$$l$$$, $$$r$$$, and $$$ans$$$ be the minimum, maximum number of tables occupied, and the maximum number of people seated, respectively.

If we encounter an introvert, we want to assign them an empty table. Therefore, if $$$l \lt t$$$, we increase $$$l, r$$$ by $$$1$$$ capping at $$$t$$$ and increase $$$ans$$$ by $$$1$$$.

If we encounter an extrovert, we want to assign them a non-empty table. Therefore, we can increase $$$ans$$$ by $$$1$$$ if there is an empty seat ($$$r * s \gt ans$$$). You also need to make sure that after this person is seated, $$$l$$$ is updated accordingly (increased by $$$1$$$ if $$$l * s \lt ans$$$ now).

If we encounter an ambivert, we have to execute both strategies above.

This solution only takes $$$O(n)$$$.

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

	int T = 1;
	cin >> T;
    while(T-->0)
    {
        ll n, s, t;
        cin >> n >> t >> s;

        string S;
        cin >> S;

        ll l = 0, r = 0, ans = 0;
        for(char c: S)
        {
            if(c == 'A')
            {
                if(t * s == ans) continue;

                ans++;
                if(ans > l * s) l++;
                r = min(t, r + 1);
            }
            else if(c == 'I')
            {
                if(l == t) continue;

                ans++;
                l++;
                r = min(t, r + 1);
            }
            else if(c == 'E')
            {
                if(ans == r * s) continue;

                ans++;
                if(ans > l * s) l++;
            }
        }

        cout << ans << "\n";
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Can you solve the Tower of Hanoi?

If $$$a_i \geq i$$$, then it is impossible because there cannot be at least $$$i$$$ rings on the $$$i$$$-th smallest ring in the first place.

If $$$a_i \lt i$$$ for all $$$i$$$, it is always possible.

If possible, we can move the cake in at most $$$2^n - 1$$$ moves with a recursive algorithm similar to the classic Tower of Hanoi.

Base Case ($$$1$$$ layer): Perform one move to move it from location $$$1$$$ to $$$3$$$.

Inductive step ($$$k$$$ layers): Let $$$f(i)$$$ be the number of moves to solve the first $$$i$$$ layers. By strong induction, $$$f(i) \leq 2 ^ i - 1$$$.

Case 1: $$$a_k = 0$$$

This takes $$$f(k - 1)$$$ moves to move the first $$$k - 1$$$ layers to location $$$2$$$, $$$1$$$ move to move the $$$k$$$-th layer to location $$$3$$$, and another $$$f(k - 1)$$$ moves to move the first $$$k-1$$$ layers to location $$$3$$$.

Total: $$$2 * f(k - 1) + 1 \leq 2 ^ k - 1$$$ moves

Case 2: $$$a_k \geq 1$$$

This takes $$$f(k - 1 - a_k)$$$ moves to move the first $$$k - 1 - a_k$$$ layers to location $$$2$$$, $$$1$$$ move to move the $$$k$$$-th layer to location $$$3$$$, $$$f(k - 1 - a_k)$$$ moves to move the first $$$k - 1 - a_k$$$ layers back to location $$$1$$$, and another $$$f(k - 1)$$$ moves to move the first $$$k - 1$$$ layers to location $$$3$$$.

Total: $$$2 * f(k - 1 - a_k) + f(k - 1) + 1 \leq 2 * f(k - 2) + f(k - 1) + 1 \leq 2 ^ k - 2 \leq 2 ^ k - 1$$$ moves.

Therefore, this problem can be solved in $$$O(2^n)$$$

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int n;
vi a(20);
vvi op;

void moveall(int k, int s, int t)
{
    if(k <= 0) return;
    int u = 6 - s - t;

    if(a[k - 1] == 0)
    {
        moveall(k - 1, s, u);
        op.pb({k, s, t});
        moveall(k - 1, u, t);
    }
    else
    {
        moveall(k - 1 - a[k - 1], s, u);
        op.pb({k, s, t});
        moveall(k - 1 - a[k - 1], u, s);
        moveall(k - 1, s, t);
    }
}

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

	int t;
	cin >> t;

	while(t-->0)
    {
        cin >> n;

        for(int i=0; i<n; i++) cin >> a[i];

        bool ok = true;
        for(int i=0; i<n; i++) if(a[i] > i) ok = false;

        if(!ok)
        {
            cout << "NO\n";
            continue;
        }

        cout << "YES\n";

        moveall(n, 1, 3);

        cout << op.size() << "\n";
        for(vi p: op) cout << p[0] << " " << p[1] << " " << p[2] << "\n";
        op.clear();
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Look at the anti-diagonals (bottom left -> top right).

There is a bijection between the snaking arrangement and the permutation of $$$[1, 2, \dots, n]$$$.

By looking at anti-diagonals of the grid, we can observe that the first anti-diagonal (just the top-left cell) only contains the snake of length $$$n$$$. Then, the next anti-diagonal contains the snake of length $$$n-1$$$ and $$$n$$$, and so on. Therefore, by looking at the $$$i$$$-th and $$$(i+1)$$$-th anti-diagonals, we know the relative position between the $$$(n - i)$$$-th snake and all snakes longer than it.

For example,

3 3 ?
? 3 3
? ? 3

has alternate diagonals 3, ? 3, ? 3 ?.

3 -> ? 3. Know that 2 is to the left of 3. ? 3 -> ? 3 ?. Know that 1 is to the right of 3.

This can now be solved comfortably in $$$O(n^2)$$$ or in $$$O(n)$$$ with more optimization.

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll N = 1000000007;
#define MAX_N 200005

vll fac(MAX_N, 1);

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

	for(int i=2; i<MAX_N; i++) fac[i] = (i * fac[i - 1]) % N;

	int t = 1;
	cin >> t;
    while(t-->0)
    {
        ll n, k;
        cin >> n >> k;

        vvi D; vi d;
        bool ok = true;

        for(int i=0; i<k; i++)
        {
            ll s, r, c;
            cin >> s >> r >> c;

            //Starting Point Check
            if(s / 2 + r + c != n + 1) ok = false;

            vector<pii> V;
            V.pb({r, c});

            if(s != 1)
            {
                string S;
                cin >> S;

                for(char C: S)
                {
                    if(C == 'R')
                    {
                        c++;
                        V.pb({r, c});
                    }
                    else
                    {
                        r++;
                        V.pb({r, c});
                    }
                }

                //Symmetry Check
                for(int i=0; i<s/2; i++) if(V[i].second - V[i].first != V[s - i - 1].second - V[s - i - 1].first) ok = false;
            }

            //Info Handling
            if(!ok) continue;

            if(D.size() < s / 2 + 1)
            {
                D.resize(s / 2 + 1);
                d.resize(s / 2 + 1);
            }

            for(int i=0; i<s/2+1; i++) D[i].pb(V[s/2-i].second);
            d[s / 2] = V[0].second;
        }

        if(!ok)
        {
            cout << "0\n";
            continue;
        }

        int x = D.size();
        for(int i=0; i<x; i++) sort(D[i].begin(), D[i].end());

        D.pb({});

        ll ans = 1;
        for(int i=0; i<x; i++)
        {
            if(!ok)
            {
                ans = 0;
                continue;
            }

            bool dec = false;

            int l = 0, k = 0;

            while(l + k < D[i].size())
            {
                if(D[i][l + k] == d[i])
                {
                    k++;
                    continue;
                }

                if(D[i][l + k] == D[i + 1][l])
                {
                    if(dec)
                    {
                        ok = false;
                        break;
                    }
                }
                else if(D[i][l + k] - 1 == D[i + 1][l])
                {
                    if(!dec)
                    {
                        if(l + k == 0 && d[i] == 0) ans *= D[i][l + k] - 1;
                        else if(l + k != 0 && d[i] == 0) ans *= D[i][l + k] - D[i][l + k - 1] - 1;
                        ans %= N;
                    }

                    dec = true;
                }
                else
                {
                    ok = false;
                    break;
                }

                l++;
            }

            if(!dec)
            {
                if(d[i] == 0) ans *= n - i - D[i][l + k - 1];
                ans %= N;
            }
        }

        ans *= fac[n - x];
        ans %= N;

        cout << ans << "\n";
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Extended Euclidean Algorithm

Formally, we have the system of equations:

$$$a * x_1 = k$$$

$$$a * x_2 + b * x_1 = k$$$

$$$a * x_3 + b * x_2 = k \dots$$$

where $$$x_i$$$ are non-negative integers.

If $$$k$$$ is not divisible by $$$gcd(a, b)$$$, then the answer is $$$0$$$.

Now, let's assume that $$$gcd(a, b) = 1$$$ since you can divide $$$a$$$, $$$b$$$, and $$$k$$$ by $$$gcd(a, b)$$$. If $$$a = b = 1$$$, then the answer is $$$n$$$.

Otherwise, we will compute $$$x_1$$$, $$$x_2$$$, ... until $$$x_i$$$ becomes negative or non-integer. ($$$x_{m+1}$$$ is not a non-negative integer).

So, we know that $$$a * x_{m + 1} + b * x_m$$$ can't be equal to $$$k$$$. Therefore, $$$x_{m + 1}$$$ is independent from $$$x_m$$$.

Next, we want to maximize the number of equations in the following form that you can solve all at the same time. $$$a * x_{m + 2} + b * x_{m + 1} = k$$$

$$$a * x_{m + 3} + b * x_{m + 2} = k$$$

$$$a * x_{m + 4} + b * x_{m + 3} = k \dots$$$

Looking at the first $$$2$$$ equations, if you can solve both of them, then $$$a * x_{m + 3} + b * x_{m + 2} = a * x_{m + 2} + b * x_{m + 1}$$$ or $$$a * (x_{m + 3} - x_{m + 2}) = b * (x_{m + 1} - x_{m + 2})$$$

Therefore, $$$b | x_{m + 3} - x_{m + 2}$$$ and $$$a | x_{m + 2} - x_{m + 1}$$$ Furthermore, $$$b | x_{m + 4} - x_{m + 3}$$$ and $$$a | x_{m + 3} - x_{m + 2}$$$ So, $$$b^2 | x_{m + 4} - x_{m + 3}$$$, $$$ab | x_{m + 3} - x_{m + 2}$$$ and $$$a^2 | x_{m + 2} - x_{m + 1}$$$. This can be extended further using induction.

Suppose $$$a \gt b$$$, consider $$$(a + b) * x_{m + 2} + b * (x_{m + 1} - x_{m + 2}) = (a + b) * x_{m + 2} + b * (a ^ v) * y$$$. If this can be equal to k when both $$$x_{m + 2}$$$ and $$$x_{m + 1} = a^v * y + x_{m + 2}$$$ are non-negative integers, then we can solve $$$v + 1$$$ equations at once.

If $$$k$$$ is divisible by $$$a + b$$$, then $$$v$$$ is infinite. Otherwise, $$$y$$$ is positive, so you can Binary Search for $$$v$$$. (Linear search should be fine too)

The $$$a \lt b$$$ case can be handled similarly.

After you have $$$m$$$ and $$$v$$$, you can use them to maximize your score.

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

// function to find the solution
ll gcd(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x= 1; y = 0;
        return a;
    }
    ll x1, y1;
    ll d = gcd(b, a%b, x1, y1);
    x = y1;
    y = x1 - y1*(a/b);
    return d;
}

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

	int t = 1;
	cin >> t;
    while(t-->0)
    {
        ll n, a, b, k;
        cin >> n >> a >> b >> k;

        ll g = __gcd(a, b);

        if(k % g != 0)
        {
            cout << "0\n";
            continue;
        }

        a /= g; b /= g; k /= g;

        if(a == 1 && b == 1)
        {
            cout << n << "\n";
            continue;
        }

        /// STEP 1
        ll ans = 0;
        if(k % a == 0)
        {
            ans++; n--;
            ll x = k / a;
            while(n > 0)
            {
                if(k - (x * b) < 0 || (k - x * b) % a != 0) break;

                x = (k - x * b) / a;
                ans++;
                n--;
            }
        }

        /// STEP 2
        ll v = 0;
        if(k % (a + b) == 0) v = 1e9;
        else
        {
            if(a < b) swap(a, b);
            /// SOLVE (a + b) x + b * a^v y = k
            ll m = b;
            while(true)
            {
                ll x, y;
                gcd(a + b, m, x, y);

                if(x < 0) {x += m; y -= a + b;}
                x *= k; y *= k;
                ll d = x / m;
                x -= d * m; y += d * (a + b);
                //cout << x << " " << y << "\n";
                //getchar();

                if(m / b * y + x < 0) break;

                /// Secondary Check
                bool ok = true;
                ll x1 = x, x2 = m / b * y + x;
                for(int _=0; _<v; _++)
                {
                    if(a * x1 + b * x2 != k) ok = false;

                    if((k - b * x1) % a)
                    {
                        ok = false;
                        break;
                    }

                    x2 = x1;
                    x1 = (k - b * x1) / a;
                }

                if(!ok) break;

                v++;

                if(a > k / m) break;
                m *= a;
            }
        }

        //cout << "! " << v << "\n";

        cout << ans + (n - (n + v) / (v + 1)) << "\n";
    }
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve