Think about the contribution of each bit to the answer.

Does all bit contributes equally?

Each bit of $$$x$$$ contributes equally to the answer. When does a bit contribute?

A bit contributes to the answer if and only if the bit remains set till reaching $$$0$$$ depth, i.e. $$$f(0, x)$$$. If you reset a bit in any depth, it won't contribute to the answer anymore. So for each bit, you have a total $$$k + 1$$$ option, reset the bit in any depth from $$$k - 1$$$ and $$$0$$$, for which it has $$$0$$$ contributions, or keep it set till the end, where it'll contribute.

Let $$$p$$$ be the number of set bits in $$$x$$$, thus each bit contributes in $$$(k + 1) ^ {p - 1}$$$. As each bit has an equal contribution, the answer will be $$$x \cdot (k + 1) ^ {p - 1}$$$.

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

#define ll long long
#define db long double
#define vii vector<ll>
#define pll pair<ll, ll>
#define F first
#define S second


const ll N = (ll) 3e5 + 5;
const ll mod = (ll) 1e9 + 7;
const ll inf = (ll) 1e18;

ll bigmod(ll a, ll b) {
    if(b == 0)
        return 1ll;
    if(b & 1)
        return (a * bigmod(a, b - 1)) % mod;
    ll ret = bigmod(a, b / 2);
    return (ret * ret) % mod;
}

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

    int t = 1;
    cin >> t;
    while(t--) {
        ll a, b, c, i, j, k, m, n, o, x, y, z;
        cin >> k >> x;
        cout << (x * bigmod(k + 1, __builtin_popcountll(x) - 1)) % mod << "\n";
    }
}

• Great problem, enjoyed it a lot.
• Yeah, kinda ok.
• Existence is pain.

Try to find out the number of problems solved on each day.

How can we find the number of problems solved on day $$$i$$$ for $$$i \leq k$$$?

How can we find the number of problems solved on day $$$i$$$ for $$$i > k$$$?

Let's create another array $$$b$$$, where $$$b_i$$$ is the number of problems solved on day $$$i$$$.

For $$$i \leq k$$$, $$$b_i = a_i - a_{i - 1}$$$. (consider $$$a_0 = 0$$$)

For $$$i > k$$$, $$$b_i = a_i - a_{i - 1} + b_{i - k}$$$

after calculating array $$$b$$$, count the maximum number of non-zero elements in a row.

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

#define ll long long
#define db long double
#define vii vector<ll>
#define pll pair<ll, ll>
#define F first
#define S second


const ll N = (ll) 1e5 + 5;
const ll mod = (ll) 1e9 + 7;
const ll inf = (ll) 1e18;

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

    int t = 1;
    cin >> t;
    while(t--) {
        ll a, b, c, i, j, k, m, n, o, x, y, z;
        cin >> n >> k;
        vii v(n + 1, 0), actual(n + 1, 0);
        for(i = 1; i <= n; i++) {
            cin >> v[i];
            actual[i] = v[i] - v[i - 1];
            if(i >= k)
                actual[i] += actual[i - k];
        }
        ll lst = 0, ans = 0;
        for(i = 1; i <= n; i++) {
            if(actual[i] == 0)
                lst = i;
            ans = max(ans, i - lst);
        }
        cout << ans << "\n";
    }
}

• Great problem, enjoyed it a lot.
• Yeah, kinda ok.
• Existence is pain.

Break down the expression that is used to calculate the value of a good partition.

Dynamic programming?

Let's suppose the size of the sets $$$s_1, s_2, \ldots, s_{26}$$$ are $$$a_1, a_2, \ldots, a_k$$$ respectively. By simplifying, we get the value of good partition:

We can further simplify part of the last term:

We can see that for choosing a set, we don't need to know the sizes of the sets we take afterwards, only the sum of previously taken sets' sizes will suffice. Thus, we can use Dynamic Programming (DP) here.

Let $$$\texttt{dp}[i][\texttt{sum}][k]$$$ = maximum value we can make for the sets $$$s_k, s_{k+1}, \ldots, s_{26}$$$ considering the suffix of the string $$$\texttt{S}[i\ldots n-1]$$$, and $$$\texttt{sum}$$$ = sum of sizes of previously taken sets (e.g., $$$s_1, s_2, \ldots, s_{k-1}$$$). Then the answer is surely $$$\texttt{dp}[0][0][1]$$$.

The transition is:

And for $$$i == n$$$ base case, we return $$$0$$$ if $$$k == 27$$$, $$$-\infty$$$ otherwise. Also, one should be careful about maintaining non zero set size for all sets.

We have achieved a very beautiful complexity of $$$O(n^3 \cdot 26)$$$. But this won't pass within the time limit.

Let's redefine our DP. Here, $$$\texttt{dp}[i][\texttt{sum}][k]$$$ means the same as before, but now we bind $$$i$$$ with $$$k$$$. Meaning, for all $$$\texttt{dp}[i][\texttt{sum}][k]$$$, we only consider the ones for which $$$s[i]$$$ = $$$k^{\text{th}}$$$ character of the alphabet. With this change, we now only have $$$|S|$$$ pairs of $$$i,k$$$ from all possible $$$\texttt{dp}[i][j][k]$$$. Thus, our number of states comes down to $$$O(n^2)$$$. We can also remove $$$k$$$ from being a state parameter.

But even then, we have $$$O(n^2)$$$ states, each with $$$O(n)$$$ transitions. We can optimize the transitions further. Instead of iterating from $$$i$$$ to $$$n$$$, we only iterate through the indexes that have the same character as $$$s[i]$$$. We can preprocess an array $$$\texttt{nxt}[i][k]$$$, which means the nearest index of character $$$k$$$ after index $$$i$$$.

So what's the total number of transitions over all states now? We can clearly see that not all states will have $$$O(n)$$$ transitions. But it's not clear how less the total count is. By some math, we can get the maximum value of an upper bound to around $$$10^9$$$. But in practice, it's much less. Figuring it out is trivial and thus left to the readers as an exercise.

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define endl '\n'
#define int long long

using namespace std;
using namespace __gnu_pbds;
using pii = pair<int, int>;

const int inf = 1e18;


int n;
string s;
int nxt[2005], nxtsame[2005];
int dp[2005][2005];

int DP(int i, int taken) {
    if(i == n) return 0;

    if(dp[i][taken] != -1) return dp[i][taken];

    int ret = -inf, cnt = 0;
    for(int j=i; j<=n and j!=-1; j=nxtsame[j]) {
        cnt += (s[j] == s[i]);

        if(nxt[j] == -1 or s[j] != s[i]) continue;
        int now = cnt * cnt * 25 + 2 * cnt * taken + DP(nxt[j], taken + cnt);
        ret = max(ret, now);
    }

    return dp[i][taken] = ret;
}

void solve(int tt) {
    cin >> n >> s;

    int last[26];
    memset(nxt, -1, sizeof(nxt));
    memset(last, -1, sizeof(last));

    for(int i=n-1; i>=0; i--) {
        if(s[i] == 'z') nxt[i] = n;
        else nxt[i] = last[s[i] - 'a' + 1];
        nxtsame[i] = last[s[i] - 'a'];
        last[s[i] - 'a'] = i;
    }

    for(int i=0; i<=n; i++) memset(dp[i], -1, sizeof dp[i]);

    int ans = 0;
    for(int i=0; i<n; i++) if(s[i] == 'a') {
        ans = max(DP(i, 0), ans);
        break;
    }

    cout << ans << endl;
}

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

    int T = 1;

    //cin >> T;
    for(int i=1; i<=T; i++) {
        solve(i);
    }

    return 0;   
}   

• Great problem, enjoyed it a lot.
• Yeah, kinda ok.
• Existence is pain.

The sum of angles in a triangle must be $$$180$$$ degrees.

$$$\sin(x) = \sin(180-x)$$$

We can’t directly find the angle from its Sine value since $$$\sin(x) = \sin(180-x)$$$. To determine, whether the angle value using the “Inverse Sine” function, is the actual value, we can sum the angles’ values and check whether the sum equals $$$180$$$ or not.

Now, what remains is, if the sum is not $$$180$$$, then how to find the angles’ value? In this case, only a single angle $$$x$$$ is actually $$$(180-x)$$$. We can simply replace each angle $$$x$$$ with $$$(180-x)$$$ and see which replacement makes the angles’ sum equal to $$$180$$$. Alternatively, you can see that if $$$A$$$, $$$B$$$, $$$C$$$ are the $$$3$$$ angles’ values and the actual value of $$$A$$$ is $$$(180-A)$$$, then the relation $$$A = B + C$$$ holds.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const long double pi = acos(-1.0);

void solve() {
    long double a,b,c;
    cin >> a >> b >> c;
    long double _a = asin(a)*180/pi, _b = asin(b)*180/pi, _c = asin(c)*180/pi;
    int A = round(_a), B = round(_b), C = round(_c);
    if(A+B+C == 180) cout << max({A,B,C}) << '\n';
    else if(A+B == C) cout << max({A,B,180-C}) << '\n';
    else if(A+C == B) cout << max({A,180-B,C}) << '\n';
    else if(B+C == A) cout << max({180-A,B,C}) << '\n';
    return;
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int tc = 1;
    cin >> tc;
    for(int kase = 1; kase <= tc; kase++) {
        //cout << "Case " << kase << ": ";
        solve();
    }
    return 0;
}

• Great problem, enjoyed it a lot.
• Yeah, kinda ok.
• Existence is pain.

You need to apply the operation at most once.

$$$n$$$ is $$$odd$$$

Notice that you need to apply the operation at most once. Let’s say, you applied two operations with $$$x1$$$ and $$$x2$$$. Then you can achieve the same result using one single operation with $$$x1 \oplus x2$$$.

Suppose, you applied the operation once with $$$x$$$. Then the array becomes like this: $$$a_1 \oplus x$$$, $$$a_2 \oplus x$$$, $$$…$$$, $$$a_n \oplus x$$$. Let’s denote $$$S$$$ as $$$xor$$$ of all these elements. Then $$$S = a_1 \oplus x \oplus a_2 \oplus x \oplus … \oplus a_n \oplus x = (a_1 \oplus a_2 \oplus …. \oplus a_n) \oplus x$$$ since $$$x$$$ occurs an odd number of times.

Let’s denote $$$P$$$ as $$$xor$$$ of $$$1$$$ to $$$n$$$. Now if the array is a permutation of length $$$n$$$, then $$$S = P$$$, that means $$$(a_1 \oplus a_2 \oplus …. \oplus a_n) \oplus x = (1 \oplus 2 \oplus …. \oplus n). So, x = (a_1 \oplus a_2 \oplus …. \oplus a_n) \oplus (1 \oplus 2 \oplus …. \oplus n)$$$. In this way, we can find the $$$x$$$, then we have to check whether doing an operation with this $$$x$$$ results in a permutation or not.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6+2;
 
int a[N];
 
void solve() {
    int n;
    cin >> n;
    int x = 0;
    for(int i = 1; i <= n; i++)
        x ^= i;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        x ^= a[i];
    }
    for(int i = 0; i < n; i++){
        a[i] ^= x;
    }
    sort(a,a+n);
    for(int i = 0; i < n; i++){
        if(a[i] != i+1){
            cout << "NO\n";return;
        }
    }
    cout << "YES\n";
    return;
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int tc = 1;
    // cin >> tc;
    for(int kase = 1; kase <= tc; kase++) {
        //cout << "Case " << kase << ": ";
        solve();
    }
    return 0;
}

• Great problem, enjoyed it a lot.
• Yeah, kinda ok.
• Existence is pain.

First you need to minimize the number of digits.

The final number will have some digit 8 padded at the last. Why?

This problem can be solved by dynamic programming as well as by finding pattern. We will discuss the later.

First, we need to minimize the number of digits. for $$$n \geq 2$$$, we can always create a number of $$$\lceil \frac{n}{7} \rceil$$$ digits, which is the minimum.

For small values of $$$n$$$, there is no optimal way of picking digits. But, we can write a bruteforce solution or use dynamic programming for small values of $$$n$$$ to ensure that there is always a solution of $$$\lceil \frac{n}{7} \rceil$$$ digits. When $$$n$$$ becomes large, it is always optimal to use digit 8 as much as possible while minimizing the number of digits as well.

In particular, for $$$n \leq 17$$$, you can find the answer by bruteforce. After that, for $$$n \gt 17$$$, it is always optimal to pad digit 8 at the last as long as $$$n \gt 17$$$ and use precalculated value when $$$n$$$ becomes less or equal to $$$17$$$.

This problem can also be solve using bfs.

Note that, for $$$n$$$ = $$$6$$$, the answer is $$$0$$$.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int ans[18];
void pre(){
    vector<int> v = {6,2,5,5,4,5,6,3,7,6};
    for(int i = 2; i <= 17; i++) ans[i] = 1000000000;
    for(int i = 0; i <= 200; i++){
        string s = to_string(i);
        int cur = 0;
        for(auto x:s)
            cur += v[x-'0'];
        ans[cur] = min(ans[cur],i);
    }
}

void solve() {
    int n;
    cin >> n;
    if(n <= 17){
        cout << ans[n] << '\n';return;
    }
    int m = n-17;
    m = (m+6)/7;
    n = n-7*m;
    cout << ans[n];
    for(int i = 0; i < m; i++)
        cout << 8;
    cout << '\n';
    return;
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    pre();
    int tc = 1;
    cin >> tc;
    for(int kase = 1; kase <= tc; kase++) {
        //cout << "Case " << kase << ": ";
        solve();
    }
    return 0;
}

• Great problem, enjoyed it a lot.
• Yeah, kinda ok.
• Existence is pain.

Can you find the answer when $$$n$$$ is even?

Can you reorder so that it works for odd $$$n$$$?

Does your solution work for $$$n = 3$$$?

Let’s try to fill one row like this $$$1, 1, 1, … , x$$$ where $$$x$$$ is the minimum possible number such that the sum of this row is a power of $$$2$$$. Now we will shuffle this row in such a way that the other conditions are satisfied.

When $$$n$$$ is even, the following matrix satisfies all the conditions:

The sum of each row is $$$(1 + 1 + …. + x)$$$ which is a power of $$$2$$$. Similarly, each column sum is $$$(1 + 1 + … + x)$$$. Now the primary diagonal contains all $$$1$$$ except at $$$n/2_{th}$$$ row where there is $$$x$$$. The secondary diagonal contains all $$$1$$$ except at $$$1_{st}$$$ row where there is $$$x$$$. So, all the conditions are satisfied.

When n is odd, the following matrix satisfies all the conditions:

The sum of each row is $$$(1 + 1 + … + x)$$$ which is a power of $$$2$$$. Similarly, each column sum is $$$(1 + 1 + … + x)$$$. Now the primary diagonal contains all $$$1$$$ except at $$$1_{st}$$$ row where there is $$$x$$$. The secondary diagonal contains all $$$1$$$ except at $$$2_{nd}$$$ row where there is $$$x$$$. So, all the conditions are satisfied.

Applying the technique mentioned above can be done for $$$n \ge 4$$$. For $$$n \leq 3$$$, there will be collision, i.e. $$$x$$$ will occur multiple times in the same row or column or diagonal. This won't create a problem for $$$n = 1$$$ and $$$n = 2$$$, as the value of $$$x$$$ itself is $$$1$$$ in these cases. The only special case is when $$$n = 3$$$, where the above matrix doesn’t satisfy the diagonal condition. You have to brute force for a solution in this case, or calculate one manually. One of the valid $$$3 \times 3$$$ matrices is as follows:

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

ll ar[1005][1005], row[1005], col[1005], d1 = 0, d2 = 0;

bool check(ll n) {
    memset(row, 0, sizeof(row));
    memset(col, 0, sizeof(col));
    d1 = d2 = 0;
    for(ll i = 1; i <= n; i++) {
        for(ll j = 1; j <= n; j++) {
            row[i] += ar[i][j];
            col[j] += ar[i][j];
            if(i == j)
                d1 += ar[i][j];
            if(i + j == n + 1)
                d2 += ar[i][j];
        }
    }
    bool ok = true;
    for(ll i = 1; i <= n; i++) {
        ok &= (__builtin_popcountll(row[i]) == 1);
        ok &= (__builtin_popcountll(col[i]) == 1);
    }
    ok &= (__builtin_popcountll(d1) == 1);
    ok &= (__builtin_popcountll(d2) == 1);
    return ok;
}

bool build(ll i, ll j, ll n) {
    if(i > n) {
        return check(n);
    }
    ll nxt_i = i, nxt_j = j;
    if(j == n)
        nxt_j = 1, nxt_i += 1;
    else
        nxt_j += 1;
    for(ll k = 1; k <= 1ll << (1 + (31 - __builtin_clz(n - 1))); k++) {
        ar[i][j] = k;
        if(build(nxt_i, nxt_j, n))
            return true;
    }
    return false;
}

void solve() {
    int n;
    cin >> n;
    if(n == 1){
        cout << 1 << '\n';return;
    }
    int x = n-1;
    int nxt = 1;
    while(nxt <= x){
        nxt *= 2;
    }
    x = nxt-x;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            ar[i][j] = 1;
        }
    }
    if(n <= 3){

        build(1, 1, n);
    } else if(n & 1) {

        ar[1][1] = x;
        ar[2][n-1] = x;
        ar[n][n-2] = x;
        ar[n-1][n] = x;
        for(int i = 3; i < n-1; i++) {
            ar[i][i-1] = x;
        }
    } else {

        ar[1][n] = x;
        for(int i = 2; i < n; i++){
            ar[i][n-i] = x;
        }
        ar[n][n-1] = x;
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cout << ar[i][j] << " \n"[j == n];
        }
    }
    return;
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int tc = 1;
    // cin >> tc;
    for(int kase = 1; kase <= tc; kase++) {
        //cout << "Case " << kase << ": ";
        solve();
    }
    return 0;
}

• Great problem, enjoyed it a lot.
• Yeah, kinda ok.
• Existence is pain.

Think greedily.

A player wins if his score is atleast $$$n/2+1$$$. (floored division, we’ll consider this throughout the proof/solution).

Let’s solve for odd $$$n$$$. We can observe that, everytime a ball is taken, the next person to move is guaranteed to find a ball that has atleast $$$2$$$ points. So let both player try taking the ball with $$$\geq 2$$$ points everytime it exists.

Case — 1: $$$n \mod 4$$$ == $$$1$$$:

Total moves = $$$n / 2 + 1 = m$$$ (m is odd)

Alice’s moves = $$$m/2 + 1$$$

Bob’s moves = $$$m/2$$$

As Alice has more moves than Bob, she can easily guarantee $$$n/2+1$$$ score for herself. Thus Alice wins.

Case — 2: $$$n \mod 4$$$ == $$$3$$$:

Total moves = $$$n / 2 + 1 = m$$$ (m is even)

Alice’s moves = $$$m / 2$$$

Bob’s moves = $$$m / 2$$$

Now, Bob can take balls of 2 points everytime, whereas Alice is forced to take ball of single point in her first move. So, Bob can always take balls of 2 points and guarantee $$$n/2+1$$$ score for him. Thus Bob wins.

Case — 3: $$$n \mod 2$$$ == $$$0$$$:

In this case, always the person with the current move can achieve score atmost 1 greater than the other. But the last move will have only a single ball left, taking that will make both player's score equal. So, the result is draw.

include<bits/stdc++.h>

using namespace std;

define ll long long

void solve() { int n; cin >> n; if(n%2 == 0) cout << "No words\n"; else if(n%4 == 1) cout << "Beautiful game\n"; else cout << "Never playing this again\n"; return; }

int32_t main() { ios_base::sync_with_stdio(false);cin.tie(NULL); int tc = 1; cin >> tc; for(int kase = 1; kase <= tc; kase++) { //cout << "Case " << kase << ": "; solve(); } return 0; }

• Great problem, enjoyed it a lot.
• Yeah, kinda ok.
• Existence is pain.

There are 2 cases:
$$$case - 1:$$$ There is no ancestor-descendent relation between the starting nodes.
$$$case - 2:$$$ A starting node is the ancestor of the other.

For $$$case - 1$$$, the answer is simply their subtree maximum.

For $$$case - 2$$$, the answer for the descendent node is still its subtree maximum, but for the ancestor node, the answer is the maximum value of all the nodes which are in its subtree but not in the subtree of the descendent. To quickly answer the query, we have to do a Euler tour on the tree and precalculate the in-time and out-time of each node. Then for the ancestor node, the range of nodes it can visit is actually $$$2$$$ disjoint subarray (possibly one empty) in the euler tour array. Then it remains to find the maximum value in these segments which can be done using sparse table or any other range query data structures.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5+2;
vector<int> g[N],euler;
int st[N],en[N],in[N],out[N],T,sub[N],a[N],table[N][20];

void dfs(int u,int p=0){
    in[u] = T++;
    st[u] = euler.size();
    euler.push_back(u);
    sub[u] = a[u];
    for(auto x: g[u]){
        if(x^p){
            dfs(x,u);
            sub[u] = max(sub[u],sub[x]);
        }
    }
    en[u] = euler.size()-1;
    out[u] = T++;
}

bool is_ancestor(int u,int v){
    return in[u] < in[v] and out[u] > out[v];
}

void build(int n){
    for(int i = 0; i < n; i++)
        table[i][0] = a[euler[i]];
    for(int k = 1; k < 20; k++){
        for(int i = 0; i+(1<<k)-1 < n; i++){
            table[i][k] = max(table[i][k-1],table[i+(1<<(k-1))][k-1]);
        }
    }
}

int get_max(int l,int r){
    int k = 31 - __builtin_clz(r-l+1);
    return max(table[l][k],table[r-(1<<k)+1][k]);
}

void solve() {
    int n,q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        g[i].clear();
        sub[i] = 0;
    }
    euler.clear();
    T = 0;

    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i < n; i++){
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1);
    build(n);
    while(q--){
        int x,y;
        cin >> x >> y;
        if(!is_ancestor(x,y) and !is_ancestor(y,x)){
            cout << sub[x] << ' ' << sub[y] << '\n';
        }
        else if(is_ancestor(x,y)){
            int l1 = st[x], r1 = st[y]-1, l2 = en[y]+1, r2 = en[x];
            int ans = get_max(l1,r1);
            if(l2 <= r2) ans = max(ans,get_max(l2,r2));
            cout << ans << ' ' << sub[y] << '\n';
        }
        else{
            int l1 = st[y], r1 = st[x]-1, l2 = en[x]+1, r2 = en[y];
            int ans = get_max(l1,r1);
            if(l2 <= r2) ans = max(ans,get_max(l2,r2));
            cout << sub[x] << ' ' << ans << '\n';
        }
    }
    return;
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int tc = 1;
    // cin >> tc;
    for(int kase = 1; kase <= tc; kase++) {
        //cout << "Case " << kase << ": ";
        solve();
    }
    return 0;
}

• Great problem, enjoyed it a lot.
• Yeah, kinda ok.
• Existence is pain.

Notice the color of the square the knight is currently in and the squares it can move to.

What is the relation of $$$(x, y)$$$ with the color of the square?

The knight changes the color of the square with every move. So if the knight has to jump to a square that has a different color than its current square, it'll take an odd number of moves. Otherwise, an even number of moves are required.

Let the current position of the knight be $$$(x, y)$$$. Notice that the color of its square depends on the parity of $$$(x + y)$$$. So just a simple parity checking is enough to determine who will win — $$$Monke$$$ or $$$Potato$$$.

/**
 * author  : UshanGhosh
 * created : 2021-01-15 09:01:28
**/ 

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

#define    ll      long long
#define    pii     pair<int,int>
#define    vii     vector<int>
#define    vcc     vector<char>
#define    pll     pair<long long, long long>
#define    mem     memset
#define    sof     sizeof
#define    co1     __builtin_popcountll
#define    PB      push_back
#define    UB      upper_bound
#define    LB      lower_bound
#define    MP      make_pair
#define    TS      to_string
#define    F       first
#define    S       second
#define    pi      acos(-1)
#define    mod     (long long)1000000007
#define    inf     (long long)1e18
#define    endl    '\n'

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        long long a,b,c,d,e,f,i,j,k,m,n,o,x,y;
        cin>>a>>b>>c>>d;
        if((a+b)%2!=(c+d)%2) cout<<"Monke\n";
        else cout<<"Potato\n";
    }
}

• Great problem, enjoyed it a lot.
• Yeah, kinda ok.
• Existence is pain.

What happens if $$$x + y > g$$$?

Is it easier to find the number of arrangements for which Monke can not be the center of attraction?

Obviously there is no solution when $$$x + y > g$$$.

Let's call an arrangement $$$bad$$$ if Monke can't fulfill his wish. Then by subtracting the number of bad arrangements from the total arrangements, we'll find the answer.

There are total $$$\binom{b + g}{b}$$$ arrangements. Let's consider when an arrangement is bad.

In a bad arrangement there are no positions for boys among the $$$x$$$'th girl from the left and $$$y$$$'th girl from the right. To count, we can consider all the girls between the $$$x$$$'th girl from the left and the $$$y$$$'th girl from the right as a single girl, as in a bad arrangement, there will be all girls between them.

The number of such arrangements are $$$\binom{b + g - (g + 1 - x - y)}{b}$$$ $$$=$$$ $$$\binom{b + x + y - 1}{b}$$$

So, the total number of good arrangements are $$$\binom{b + g}{b} - \binom{b + x + y - 1}{b}$$$

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

#define ll long long
#define db long double
#define vii vector<ll>
#define pll pair<ll, ll>
#define F first
#define S second


const ll N = (ll) 3e6 + 5;
const ll mod = (ll) 1e9 + 7;
const ll inf = (ll) 1e18;

ll bigmod(ll a, ll b) {
    if(b == 0)
        return 1ll;
    if(b & 1)
        return (1ll * a * bigmod(a, b - 1)) % mod;
    ll ret = bigmod(a, b / 2);
    return (1ll * ret * ret) % mod;
}

ll fact[N], i_fact[N];

void factorial() {
    fact[0] = 1;
    for(int i = 1; i < N; i++)
        fact[i] = (1ll * fact[i - 1] * i) % mod;

    i_fact[N - 1] = bigmod(fact[N - 1], mod - 2);
    for(int i = N - 2; i >= 0; i--)
        i_fact[i] = (1ll * i_fact[i + 1] * (i + 1)) % mod;
}

ll ncr(ll n, ll r) {
    if(r > n)
        return 0ll;
    return (1ll * fact[n] * (1ll * i_fact[r] * i_fact[n - r] % mod)) % mod;
}

ll npr(ll n, ll r) {
    return (1ll * fact[n] * i_fact[n - r]) % mod;
}

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

    int t = 1;
    cin >> t;
    factorial();

    while(t--) {
        ll a, b, c, g, i, j, k, m, n, o, x, y, z;
        cin >> b >> g >> x >> y;

        if(x + y > g)
            cout << 0 << "\n";
        else
            cout << (ncr(b + g, g) - ncr(b + x + y - 1, b) + mod) % mod << "\n";
    }
}

• Great problem, enjoyed it a lot.
• Yeah, kinda ok.
• Existence is pain.

Think of the bracket sequence as an array of $$$+1$$$ and $$$-1$$$

What are the things you see on the array that indicates if a sequence is RBS or not?

Multiply with $$$-1$$$ to flip a range.

Consider the bracket sequence as an array. Replace '(' with $$$+1$$$ and ')' with $$$-1$$$

In an RBS, the number of '(' must be equal to ')'. Also the number of '(' must be greater or equal to the number of ')' in any prefix. What does that translate to in the array we've created?

In the array, if the sum of all elements is $$$0$$$, and the minimum prefix-sum among all prefixes is $$$0$$$, then it's an RBS.

To flip a segment, multiply with $$$-1$$$ in the array using a segment tree with lazy propagation. Maintain a range sum, minimum prefix sum, and maximum prefix sum to calculate the result after a flip.

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

#define ll long long
#define db long double
#define vii vector<ll>
#define pll pair<ll, ll>
#define F first
#define S second


const ll N = (ll) 2e5 + 5;
const ll mod = (ll) 1e9 + 7;
const ll inf = (ll) 1e18;

#define lc (u << 1)
#define rc (u << 1 | 1)

struct vrtx{
    int sum, lazy, p_mn, p_mx;
    vrtx(){ sum = 0, lazy = 1, p_mn = mod, p_mx = -mod;}
};
struct seg_lazy{
    // must change this
    
 
    vrtx tre[4 * N], default_return;
 
 
    //changes required here
    void pull(int u){
        tre[u].sum = tre[lc].sum + tre[rc].sum;
        tre[u].p_mn = min(tre[lc].p_mn, tre[lc].sum + tre[rc].p_mn);
        tre[u].p_mx = max(tre[lc].p_mx, tre[lc].sum + tre[rc].p_mx);
    }
 
    //changes required here
    void propagate(int u, int l,int r){
        if(tre[u].lazy == 1)
            return;
        tre[u].sum = tre[u].lazy * tre[u].sum;
        tre[u].p_mn *= tre[u].lazy;
        tre[u].p_mx *= tre[u].lazy;
        swap(tre[u].p_mn, tre[u].p_mx);
        if(l != r) tre[lc].lazy *= tre[u].lazy, tre[rc].lazy *= tre[u].lazy;
        tre[u].lazy = 1;
    }
 
 
 
    void init(int u,int l,int r){
 
        // changes required here
        tre[u].lazy = 1;
        if(l == r){
            tre[u].sum = 0;
            return ;
        }
        int mid = l + r >> 1;
        init(lc, l, mid);
        init(rc, mid + 1, r);
        pull(u);
    }
    void entry(int u,int l,int r,int i,int val){
        if(i > r || i < l) return;
        if(i <= l && i >= r){
            tre[u].sum = val;
            tre[u].p_mn = val;
            tre[u].p_mx = val;
            return;
        }
        int mid = l + r >> 1;
        entry(lc, l, mid, i, val);
        entry(rc, mid + 1, r, i, val);
        pull(u);
    }
    void update(int u,int l,int r,int i,int j,int val){
        propagate(u, l, r);
        if(i > r || j < l) return;
        if(i <= l && j >= r){
            tre[u].lazy *= val;
            propagate(u, l, r);
            return;
        }
        int mid = l + r >> 1;
        update(lc, l, mid, i, j, val);
        update(rc, mid + 1, r, i, j, val);
        pull(u);
    }
    vrtx combine(vrtx x, vrtx y){
        vrtx ret;
        ret.sum = x.sum + y.sum;
        ret.p_mn = min(x.p_mn, x.sum + y.p_mn);
        ret.p_mx = max(x.p_mx, x.sum + y.p_mx);
        return ret;
    }
    vrtx query(int u,int l,int r,int i,int j){
        propagate(u, l, r);
        if(i <= l && j >= r) return tre[u];
        if(i > r || j < l) return default_return;
        int mid = (l + r) / 2;
        return combine(query(lc, l, mid, i, j), query(rc, mid + 1, r, i, j));
    }
 
 
};



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

    int t = 1;
    //cin >> t;
    while(t--) {
        ll a, b, c, i, j, k, m, n, o, x, y, z;
        ll q;
        cin >> n >> q;
        seg_lazy st;
        st.init(1, 1, n);
        string s;
        cin >> s;
        s = "#" + s;
        for(i = 1; i <= n; i++) {
            st.entry(1, 1, n, i, (s[i] == '(' ? 1 : -1));
        }
        while(q--) {
            cin >> a >> b >> c;
            if(a == 1) {
                st.update(1, 1, n, b, c, -1);
            } else {
                vrtx ans =  st.query(1, 1, n, b, c);
                cout << (ans.sum == 0 && ans.p_mn == 0 ? "YES" : "NO") << "\n";
            }
        }
    }
}

• Great problem, enjoyed it a lot.
• Yeah, kinda ok.
• Existence is pain.

Try to move greedily.

Suppose $$$dx = |s_x - t_x|$$$ and $$$dy = |s_y - t_y|$$$. For simplicity, let’s assume you need to cover a smaller distance in the Y-axis and a greater distance on the X-axis. In other words, $$$dx \geq dy$$$. The other case can be solved similarly.

Suppose we move like this, $$$1$$$ unit in the Y-axis and $$$k$$$ unit in the X-axis. In this way, we can move $$$(dy+1) \cdot k$$$ unit in the X-axis for moving $$$dy$$$ unit in the Y-axis. Hence if $$$dx \leq (dy+1) \cdot k$$$, then we can reach the destination in Manhattan distance.

If $$$dx > (dy+1) \cdot k$$$, we need some extra moves. After moving in the way mentioned above, we will reach the destination on the Y-axis but will need to go some more steps on the X-axis. The optimal way to move in this case is to go $$$1$$$ unit in the Y-axis, then $$$k$$$ unit in the X-axis, then $$$1$$$ unit in the reverse direction in the Y-axis to again come back to the destination Y-axis, then $$$k$$$ unit in X-axis and so on. You need to carefully handle the last move, if you are $$$1$$$ unit away from the destination Y-axis, then you will need $$$1$$$ more move to come back to the destination Y-axis. You can simply think of it like this, each extra $$$2 \cdot k$$$ distance in the X-axis requires $$$2$$$ extra moves in the Y-axis. This way, the implementation is easier.

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


void solve() {
    ll sx,sy,tx,ty,k;
    cin >> sx >> sy >> tx >> ty >> k;
    ll dx = abs(sx-tx), dy = abs(sy-ty);

    if(dx < dy) swap(dx,dy);

    if(dx <= (dy+1)*k) cout << dx+dy << '\n';
    else{
        ll ex = 2*((dx-(dy+1)*k+2*k-1)/(2*k));
        cout << dx+dy+ex << '\n';
    }
    return;
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int tc = 1;
    cin >> tc;
    for(int kase = 1; kase <= tc; kase++) {
        //cout << "Case " << kase << ": ";
        solve();
    }
    return 0;
}

• Great problem, enjoyed it a lot.
• Yeah, kinda ok.
• Existence is pain.