The smallest length for such a string is $$$n\cdot k$$$.

The smallest length possible for such a string is $$$n\cdot k$$$.

In fact, it is always possible to construct a string of length $$$n\cdot k$$$ that satisfies this property. One such string is $$$(a_1a_2a_3\ldots a_k)(a_1a_2a_3\ldots a_k)(a_1a_2a_3\ldots a_k)\ldots n$$$ times where $$$a_i$$$ is the $$$i^{th}$$$ letter of English alphabet. For example, the answer for $$$n=3,k=4$$$ can be $$$\texttt{abcdabcdabcd}$$$. It is not hard to see that the first letter of the subsequence can be from the first group of $$$k$$$ letters, second letter from the second group and so on.

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

int main()
{
    int tc;
    cin >> tc;
    while(tc--)
    {
        int n,k;
        cin >> n >> k;
        for(int i=0;i<n;i++)
            for(char c='a';c<'a'+k;c++)
                cout << c;
        cout << '\n';
    }
}

• Good problem:
• Ok problem:
• Bad problem:
• Did not attempt:

$$$GCD(a_1,a_2,a_3,\ldots,a_n) = GCD(a_1,a_1+a_2,a_1+a_2+a_3,\ldots,a_1+a_2+a_3+\ldots+a_n)$$$

The maximum GCD that can be achieved is always a divisor of $$$x$$$.

Let the difficulties of the $$$n$$$ sub-problems be $$$a_1,a_2,a_3,\ldots,a_n$$$. By properties of GCD, $$$GCD(a_1,a_2,a_3,\ldots,a_n)$$$ $$$= GCD(a_1,a_1+a_2,a_1+a_2+a_3,\ldots,a_1+a_2+a_3+\ldots+a_n)$$$ $$$= GCD(a_1,a_1+a_2,a_1+a_2+a_3,\ldots,x)$$$. So, the final answer will always be a divisor of $$$x$$$.

Now, consider a divisor $$$d$$$ of $$$x$$$. If $$$n\cdot d\leq x$$$, you can choose the difficulties of the sub-problems to be $$$d,d,d,\ldots,x-(n-1)d$$$ each of which is a multiple of $$$d$$$ and hence, the balance of this problemset will be $$$d$$$. Otherwise you cannot choose the difficulties of $$$n$$$ sub-problems such that each of them is a multiple of $$$d$$$.

Find the maximum $$$d$$$ for which this condition holds. This can be done in $$$\mathcal{O}(\sqrt{x})$$$ using trivial factorization.

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

int main()
{
    int tc;
    cin >> tc;
    while(tc--)
    {
        int x,n;
        cin >> x >> n;
        int ans = 1;
        for(int i=1;i*i<=x;i++)
        {
            if(x%i==0)
            {
                if(n<=x/i)
                    ans=max(ans,i);
                if(n<=i)
                    ans=max(ans,x/i);
            }
        }
        cout << ans << '\n';
    }
}

• Good problem:
• Ok problem:
• Bad problem:
• Did not attempt:

Try to build the counter-case greedily.

While building the counter-case, it is always optimal to choose the first character as the one whose first index of occurrence in the given string is the highest.

We will try to construct a counter-case. If we can't the answer is YES otherwise NO.

We will greedily construct the counter-case. It is always optimal to choose the first character of our counter-case as the character (among the first $$$k$$$ English alphabets) whose first index of occurrence in $$$s$$$ is the highest. Add this character to our counter-case, remove the prefix up to this character from $$$s$$$ and repeat until the length of the counter-case reaches $$$n$$$ or we reach the end of $$$s$$$.

If the length of the counter-case is less than $$$n$$$, find a character which does not appear in the last remaining suffix of $$$s$$$. Keep adding this character to the counter-case until its length becomes $$$n$$$. This is a valid string which does not occur as a subsequence of $$$s$$$.

Otherwise, all possible strings of length $$$n$$$ formed using the first $$$k$$$ English alphabets occur as a subsequence of $$$s$$$.

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

int main()
{
    std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        int n, k, m;
        cin>>n>>k>>m;
        string s;
        cin>>s;
        string res="";
        bool found[k];
        memset(found, false, sizeof(found));
        int count=0;
        for(char c:s)
        {
            if(res.size()==n)
                break;
            count+=(!found[c-'a']);
            found[c-'a']=true;
            if(count==k)
            {
                memset(found, false, sizeof(found));
                count=0;
                res+=c;
            }
        }
        if(res.size()==n)
            cout<<"YES\n";
        else
        {
            cout<<"NO\n";
            for(int i=0;i<k;i++)
            {
                if(!found[i])
                {
                    while(res.size()<n)
                        res+=(char)('a'+i);
                }
            }
            cout<<res<<"\n";
        }
    }
}

This problem is essentially "Implement the checker for Div. 2A". It was not among the problems that were initially proposed for the round. While preparing problem 2A, I realized that writing the checker in itself might be a more interesting problem compared to 2A.

• Good problem:
• Ok problem:
• Bad problem:
• Did not attempt:

Since expected value is linear, we can consider the contribution of initial friendship values and the contribution of increase in friendship values by repeated excursions independently.

Contribution of the initial friendship values will be $$$\dfrac{k\times \sum_{i=1}^{n}f_i}{\binom{n}{2}}$$$.

Now we can assume that there are $$$m$$$ pair of friends out of a total of $$$\binom{n}{2}$$$ pairs of students whose initial friendship value is $$$0$$$.

Since expected value is linear, we can consider the contribution of initial friendship values and the contribution of increase in friendship values by repeated excursions independently.

Let $$$d=\binom{n}{2}$$$ denote the total number of pairs of students that can be formed.

Contribution of the initial friendship values will be $$$s=\dfrac{k\cdot \sum_{i=1}^{n}f_i}{d}$$$.

Now, to calculate the contribution to the answer by the increase in friendship values due to excursions, for each pair of friends, it will be $$$\sum_{x=0}^{k}\dfrac{x(x-1)}{2}\cdot P(x)$$$ where $$$P(x)$$$ is the probability of a pair of friends to be selected for exactly $$$x$$$ out of the $$$k$$$ excursions which is given by $$$P(x)=\binom{k}{x}\cdot \bigg(\dfrac{1}{d}\bigg)^{x}\cdot \bigg(\dfrac{d-1}{d}\bigg)^{k-x}$$$.

Since the increase is uniform for all pair of friends, we just have to multiply this value by $$$m$$$ and add it to the answer.

The time complexity is $$$\mathcal{O}(m+k\log k)$$$ per test case.

#include <bits/stdc++.h>                
#define int long long   
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007ll
using namespace std;
const long long N=200005, INF=2000000000000000000;

int power(int a, int b, int p)
{
    if(b==0)
    return 1;
    if(a==0)
    return 0;
    int res=1;
    a%=p;
    while(b>0)
    {
        if(b&1)
        res=(1ll*res*a)%p;
        b>>=1;
        a=(1ll*a*a)%p;
    }
    return res;
}
int fact[N],inv[N];
void pre()
{
    fact[0]=1;
    inv[0]=1;
    for(int i=1;i<N;i++)
    fact[i]=(i*fact[i-1])%mod;
    for(int i=1;i<N;i++)
    inv[i]=power(fact[i], mod-2, mod);
}
int nCr(int n, int r, int p) 
{ 
    if(r>n || r<0)
    return 0;
    if(n==r)
    return 1;
    if (r==0) 
    return 1; 
    return (((fact[n]*inv[r]) % p )*inv[n-r])%p;
} 
int32_t main()
{
    IOS;
    pre();
    int t;
    cin>>t;
    while(t--)
    {
        int n, m, k;
        cin>>n>>m>>k;
        int sum=0;
        for(int i=0;i<m;i++)
        {
            int a, b, f;
            cin>>a>>b>>f;
            sum=(sum + f)%mod;
        }
        int den=((n*(n-1))/2ll)%mod;
        int den_inv=power(den, mod-2, mod);
        int base=(((sum*k)%mod)*den_inv)%mod;
        int avg_inc=0;
        for(int i=1;i<=k;i++)
        {
            // Extra sum added to ans if a particular pair of friends is picked i times. 
            int sum=((i*(i-1))/2ll)%mod; 
            int prob = (nCr(k, i, mod)*power(den_inv, i, mod))%mod;
            // Probablity that a particular pair in unpicked for a given excursion.
            int unpicked_prob = ((den-1)*den_inv)%mod;
            // Probability that a particular pair is picked exactly i times.
            prob=(prob * power(unpicked_prob, k-i, mod))%mod;
            avg_inc = (avg_inc + (sum*prob)%mod)%mod;
        }
        int ans = (base + (m*avg_inc)%mod)%mod;
        cout<<ans<<'\n';
    }
}

• Good problem:
• Ok problem:
• Bad problem:
• Did not attempt:

Segment Tree with Lazy Propogation

We can maintain a segment tree of size $$$n$$$ which initially stores the cost of all the ships.

Now there are 2 types of updates when we add an harbour:

• The ships to the left of the new harbour have their cost decreased by a fixed amount.
• The ships to the right of the harbour have their cost changed by the value equivalent to product of distance from the harbour on their right (which remains unchanged) and the difference in values of the previous and new harbour to their left.

There are multiple ways to handle both the updates simultaneously, a simple way would be to use a struct simulating an arithmetic progression. It can contain two values

• Base: Simply a value which has to be added to all values belonging to the segment.
• Difference: For each node of the segment, $$$dif \times dist$$$ will be added to the node, where $$$dist$$$ is the distance of node from the end of the segment.

Using summation of arithmetic progression we can make sure that the updates on Difference can be applied to an entire segment lazily. You can see the code for more details.

#include <bits/stdc++.h>                 
#define int long long    
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
using namespace std;
const long long N=300005;

struct ap {
    int base, dif;
};

ap add(ap a, ap b)
{
    ap res;
    res.base = a.base + b.base;
    res.dif = a.dif + b.dif;
    return res;
}

int convert(ap a, int n)
{
    int res = (n*a.base);
    res += ((n*(n-1))/2ll)*a.dif;
    return res;
}

int st[4*N], cost[N];
ap lazy[4*N];
ap zero = {0, 0};

void propogate(int node, int l, int r)
{
    st[node] += convert(lazy[node], r-l+1);
    if(l!=r)
    {
        lazy[node*2+1] = add(lazy[node*2+1], lazy[node]);
        int mid = (l+r)/2;
        int rig = (r-mid);
        lazy[node].base += (rig*lazy[node].dif);
        lazy[node*2] = add(lazy[node*2], lazy[node]);
    }
    lazy[node] = zero;
}
void build(int node, int l, int r)
{
    if(l==r)
    {
        st[node] = cost[l];
        lazy[node] = zero;
        return;
    }
    int mid=(l+r)/2;
    build(node*2, l, mid);
    build(node*2+1, mid+1, r);
    st[node] = (st[node*2] + st[node*2+1]);
    lazy[node] = zero; 
    return;
}
void update(int node, int l, int r, int x, int y, ap val)
{
    if(lazy[node].base != 0 || lazy[node].dif != 0)
    propogate(node, l, r);
    if(y<x||x>r||y<l)
    return;
    if(l>=x&&r<=y)
    {
        st[node] += convert(val, r-l+1);
        if(l!=r)
        {
            lazy[node*2+1] = add(lazy[node*2+1], val);
            int mid = (l+r)/2;
            int rig = (r-mid);
            val.base += (rig*val.dif);
            lazy[node*2] = add(lazy[node*2], val);
        }
        return;
    }
    int mid=(l+r)/2;
    update(node*2+1, mid+1, r, x, y, val);
    if(y>mid)
    {
        int rig = (min(y, r)-mid);
        val.base += (rig*val.dif);
    }
    update(node*2, l, mid, x, y, val);
    st[node] = st[node*2] + st[node*2+1];
    return;
}
int query(int node, int l, int r, int x, int y)
{
    if(lazy[node].base != 0 || lazy[node].dif != 0)
    propogate(node, l, r);
    if(y<x||y<l||x>r)
    return 0;
    if(l>=x&&r<=y)
    return st[node];
    int mid=(l+r)/2;
    return query(node*2, l, mid, x, y) + query(node*2+1, mid+1, r, x, y);
}

int32_t main()
{
    IOS;
    int n, m, q;
    cin>>n>>m>>q;
    set <int> harbours;
    int X[m], V[n+1];
    for(int i=0;i<m;i++)
    {
        cin>>X[i];
        harbours.insert(X[i]);
    }
    for(int i=0;i<m;i++)
    {
        int v;
        cin>>v;
        cost[X[i]] = v;
        V[X[i]] = v;
    }
    for(int i=1;i<=n;i++)
    {
        if(cost[i] == 0)
        cost[i] = cost[i-1];
    }
    int dist=0;
    for(int i=n;i>0;i--)
    {
        if(harbours.find(i) != harbours.end())
        dist=0;
        else
        dist++;
        cost[i] *= dist;
    }
    build(1, 1, n);
    while(q--)
    {
        int typ;
        cin>>typ;
        if(typ == 1)
        {
            int x, v;
            cin>>x>>v;
            V[x] = v;
            auto it = harbours.lower_bound(x);
            int nxt = (*it);
            it--;
            int prev = (*it);
            ap lef = {(V[prev]*(x-nxt)), 0};
            ap rig = {0, V[x]-V[prev]};
            update(1, 1, n, prev+1, x, lef);
            update(1, 1, n, x+1, nxt, rig);
            harbours.insert(x);
        }
        else
        {
            int l, r;
            cin>>l>>r;
            cout<<query(1, 1, n, l, r)<<'\n';
        }
    }
}

• Good problem:
• Ok problem:
• Bad problem:
• Did not attempt:

You need more math and less paper :)

The length of mountain crease lines and valley crease lines created in each operation is the same, except for the first operation.

Let there be an upside of the paper and a downside of the paper, initially the upside of the paper is facing up. With a little imagination, we can see that the mountain crease lines on the upside of the paper will be valley crease lines on the downside of the paper, and vice versa.

Grey is the upside and orange is the downside

After the first operation, what once was a single layer of square paper turns into a square with two overlapping layers of paper. The layer at the bottom has its upside facing up, and the layer at the top has its downside facing up.

After this first operation, whatever crease lines are formed on the upside of the bottom layer will be the same as the ones formed on the bottom layer of the top layer, which means when the paper is unfolded and the upside of the entire paper is facing up, the mountain crease lines and the valley crease lines created after the first operation will be equal.

Let $$$M$$$ be the length of mountain crease lines and $$$V$$$ be the length of valley crease lines after $$$N$$$ moves, and the side of the square paper is $$$1$$$.

Let $$$diff = V - M = $$$ Length of valley crease lines created in the first operation $$$ = 2\sqrt{2}$$$.

It is easy to calculate the total crease lines that are created (mountain and valley) in $$$N$$$ operations. It is the sum of a GP.

Let $$$sum = V + M = {\displaystyle\sum_{i = 1}^{N}}2^{i - 1}\cdot2\sqrt{2}\cdot{(\dfrac{1}{\sqrt{2}})}^{i - 1} = {\displaystyle\sum_{i = 1}^{N}}(\sqrt{2})^{i + 2}$$$

Now to find $$$\dfrac{M}{V}$$$, we use the age-old componendo and dividendo.

$$$\dfrac{M}{V} = \dfrac{sum - diff}{sum + diff}$$$

And then rationalize it to find the coefficient of $$$\sqrt{2}$$$.

The reason for the uncommon modulo in the problem is that the irrational part of $$$\dfrac{M}{V}$$$ is of the form $$$\dfrac{a\sqrt{2}}{b^2 - 2}$$$, where $$$a$$$ and $$$b$$$ are some integers. If there exists any $$$b$$$ such that $$$b^2 \equiv 2 \pmod m$$$, then the denominator becomes $$$0$$$.

To avoid this situation, such a prime modulo $$$m$$$ was taken for which $$$2$$$ is not a quadratic residue modulo $$$m$$$. It can be seen that $$$999999893\bmod 8 = 5$$$ and so, the Legendre symbol $$$\bigg(\dfrac{2}{999999893}\bigg) = -1$$$ meaning that $$$2$$$ is a quadratic non-residue modulo $$$999999893$$$.

// library link: https://github.com/manan-grover/My-CP-Library/blob/main/library.cpp
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define asc(i,a,n) for(I i=a;i<n;i++)
#define dsc(i,a,n) for(I i=n-1;i>=a;i--)
#define forw(it,x) for(A it=(x).begin();it!=(x).end();it++)
#define bacw(it,x) for(A it=(x).rbegin();it!=(x).rend();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)
#define fbo(x) find_by_order(x)
#define ook(x) order_of_key(x)
#define all(x) (x).begin(),(x).end()
#define sz(x) (I)((x).size())
#define clr(x) (x).clear()
#define U unsigned
#define I long long int
#define S string
#define C char
#define D long double
#define A auto
#define B bool
#define CM(x) complex<x>
#define V(x) vector<x>
#define P(x,y) pair<x,y>
#define OS(x) set<x>
#define US(x) unordered_set<x>
#define OMS(x) multiset<x>
#define UMS(x) unordered_multiset<x>
#define OM(x,y) map<x,y>
#define UM(x,y) unordered_map<x,y>
#define OMM(x,y) multimap<x,y>
#define UMM(x,y) unordered_multimap<x,y>
#define BS(x) bitset<x>
#define L(x) list<x>
#define Q(x) queue<x>
#define PBS(x) tree<x,null_type,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define PBM(x,y) tree<x,y,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define pi (D)acos(-1)
#define md 999999893
#define rnd randGen(rng)
I modex(I a,I b,I m){
  a=a%m;
  if(b==0){
    return 1;
  }
  I temp=modex(a,b/2,m);
  temp=(temp*temp)%m;
  if(b%2){
    temp=(temp*a)%m;
  }
  return temp;
}
I mod(I a,I b,I m){
  a=a%m;
  b=b%m;
  I c=__gcd(a,b);
  a=a/c;
  b=b/c;
  c=modex(b,m-2,m);
  return (a*c)%m;
}
int main(){
  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  uniform_int_distribution<I> randGen;
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  #ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("out04.txt", "w", stdout);
  #endif
  I temp=md;
  I t;
  cin>>t;
  while(t--){
    I n;
    cin>>n;
    I b=modex(2,n/2,md)-1;
    I a;
    if(n%2){
      a=modex(2,n/2+1,md)-1;
    }else{
      a=modex(2,n/2,md)-1;
    }
    I temp=(a+1)*(a+1);
    temp%=md;
    temp-=2*b*b;
    temp%=md;
    I ans=mod(2*b,temp,md);
    ans+=md;
    ans%=md;
    cout<<ans<<"\n";
  }
  return 0;
}

• Good problem:
• Ok problem:
• Bad problem:
• Did not attempt:

Consider a function $$$f(n, m, k)$$$ which returns the number of permutations such that length of longest regular bracket subsequence is at most $$$2 \cdot k$$$ where $$$n$$$ is the number of '(' and $$$m$$$ is the number of ')'.

Answer to the problem is $$$f(n, m, k) - f(n, m, k-1)$$$

Now to compute $$$f(n, m, k)$$$, we can consider the following cases:

• Case 1: $$$k \ge min(n, m)\rightarrow$$$ Here, the answer is $$${n+m} \choose {m}$$$, since none of the strings can have a subsequence of length greater than $$$k$$$.

• Case 2: $$$k < min(n, m)\rightarrow$$$ Here we can write $$$f(n, m, k) = f(n-1, m, k-1) + f(n, m-1, k)$$$ since all strings will either start with:
  a) ')' $$$\rightarrow$$$ Here, count is equal to $$$f(n, m-1, k)$$$.
  b) '(' $$$\rightarrow$$$ Here, count is equal to $$$f(n-1, m, k-1)$$$, the first opening bracket will always add $$$1$$$ to the optimal subsequence length because all strings where each of the $$$m$$$ ')' is paired to some '(' don't contribute to the count since $$$k<m$$$.

After this recurrence relation we have 2 base cases:

• $$$k=0\rightarrow$$$ Here, count is $$$1$$$ which can also be written as $$${n+m} \choose {k}$$$.
• $$$k=min(n, m)\rightarrow$$$ Here, count is $$${n+m} \choose {m}$$$ (as proved in Case 1) which can also be written as $$${n+m} \choose {k}$$$.

Now using induction we can prove that the value of $$$f(n, m, k)$$$ for Case 2 is $$${n+m} \choose {k}$$$.

#include <bits/stdc++.h>                   
#define int long long      
using namespace std;
const long long N=4005, mod=1000000007;

int power(int a, int b, int p)
{
    if(a==0)
    return 0;
    int res=1;
    a%=p;
    while(b>0)
    {
        if(b&1)
        res=(1ll*res*a)%p;
        b>>=1;
        a=(1ll*a*a)%p;
    }
    return res;
}

int fact[N], inv[N];
void pre()
{
    fact[0]=inv[0]=1;
    for(int i=1;i<N;i++)
    fact[i]=(fact[i-1]*i)%mod;
    for(int i=1;i<N;i++)
    inv[i]=power(fact[i], mod-2, mod);
}
int nCr(int n, int r)
{
    if(min(n, r)<0 || r>n)
    return 0;
    if(n==r)
    return 1;
    return (((fact[n]*inv[r])%mod)*inv[n-r])%mod;
}
int f(int n, int m, int k)
{
    if(k>=min(n, m))
        return nCr(n+m, m);
    return nCr(n+m, k);
}
int32_t main()
{
    pre();
    int t;
    cin>>t;
    while(t--)
    {
        int n, m, k;
        cin>>n>>m>>k;
        cout<<(f(n, m, k) - f(n, m, k-1) + mod)%mod<<"\n";
    }
}

• Good problem:
• Ok problem:
• Bad problem:
• Did not attempt:

Can you solve it for $$$k=2$$$?

Using linearity of expectation, we can say that expected number of cuts is same as sum of probability of each line being cut and for $$$k=2$$$, we need to cut the paper until we achieve a $$$1 \times 1$$$ piece of paper.

Probability of each horizontal line being cut is $$$\dfrac {1}{count \thinspace of \thinspace lines \thinspace above \thinspace it + 1}$$$ Probability of each vertical line being cut is $$$\dfrac {1}{count \thinspace of \thinspace lines \thinspace left \thinspace to \thinspace it + 1}$$$

Now for $$$k=2$$$ we just have to calculate the sum of all these probabilities.

For the given problem we can solve it by dividing it into 4 cases:

1. Only Vertical Cuts:
   Let the largest integer $$$y$$$ for which $$$n\cdot y<k$$$ be $$$reqv$$$.
   
   The probability of achieving the goal using only vertical cuts is $$$\frac{reqv}{reqv+n-1}$$$ since one of the $$$reqv$$$ lines needs to be cut before all the horizontal lines. Now we will multiply this with the sum of conditional probabilities for each of the vertical line.
   
   Sum of conditional probabilities of being cut for all lines from $$$1$$$ to $$$reqv$$$ is exactly $$$1$$$, since for area to be smaller than $$$k$$$, one of them needs to be cut and as soon as one is cut, the area becomes less than $$$k$$$ so no further cuts are required. Now for the lines from $$$reqv+1$$$ to $$$m-1$$$, their conditional probabilities will form the following harmonic progression:
   
   $$$\frac{1}{n+reqv} + \frac{1}{n+reqv+1} + .... + \frac{1}{n+m-2}$$$
   This is due to the fact that for a line to be cut it needs to occur before all horizontal lines and all vertical lines smaller than it.
   
   

2. Case with only horizontal cuts can be handled similarly.
   
   

3. Case when the overall last cut is a horizontal one and there is at least one vertical cut:
   
   For this, we iterate over the last cut among all the vertical cuts.
   
   Let the last vertical cut be $$$x$$$. We now find the largest $$$y$$$ such that $$$(y\cdot x)<k$$$. Let this value be $$$reqh$$$.
   
   The objective can be achieved using this case if the vertical line $$$x$$$ occurs before all the horizontal lines from $$$1$$$ to $$$reqh$$$ and all the vertical lines from $$$1$$$ to $$$x-1$$$, and after that any one of the horizontal line from $$$1$$$ to $$$reqh$$$ occur before all the vertical lines from $$$1$$$ to $$$x-1$$$.
   
   The probability of this happening is $$$\frac{1}{x+reqh}\times\frac{reqh}{reqh+x-1}$$$.
   
   Now we just add the the conditional probabilities of being cut for every line and multiply this with the above probability to find the contribution of this case to the final answer.
   
   a. Firstly the conditional probability of the vertical line $$$x$$$ being cut is $$$1$$$.
   
   b. The sum of conditional probabilities for horizontal lines $$$1$$$ to $$$reqh$$$ is also $$$1$$$.
   
   The order of the first $$$x$$$ vertical cuts and the first $$$reqh$$$ horizontal cuts for the given case would look like:
   $$$x_v$$$, $$$y1_h$$$, ($$$(x-1)$$$ vertical lines and $$$(reqh-1)$$$ horizontal lines in any relative ordering) [Total $$$x+reqh$$$ elements in the sequence].
   
   $$$x_v$$$ denotes the $$$x^{th}$$$ vertical cut.
   $$$y1_h$$$ denotes the horizontal cut which occurs first among all the first $$$reqh$$$ horizontal cuts.
   
   c. Vertical cuts from $$$x+1$$$ to $$$m-1$$$:
   
   For the $$$(x+1)^{th}$$$ cut, we can look at this like it needs to occur before the $$$x^{th}$$$ vertical cut (or it has one gap in the sequence to choose from a total of $$$(x+reqh+1)$$$ gaps).
   
   So the probability is $$$\frac{1}{x+reqh+1}$$$.
   
   For the $$$(x+2)^{th}$$$ cut, we can first place the $$$(x+2)^{th}$$$ cut with probability $$$\frac{1}{x+reqh+1}$$$ now we need to place the $$$(x+1)^{th}$$$ cut after of this which will happen with the probability of $$$\frac{x+reqh+1}{x+reqh+2}$$$.
   
   So the overall probability is the product i.e., $$$\frac{1}{x+reqh+2}$$$.
   
   Similarly, the probability for $$$(x+i)^{th}$$$ cut is $$$\frac{1}{x+reqh+i}$$$.
   
   The sum of this Harmonic Progression can be computed in $$$\mathcal{O}(1)$$$ using pre computation.
   
   d. Horizontal cuts from $$$reqh+1$$$ to $$$n-1$$$ (Trickiest Case imo)
   
   Let us see the case for the $$$(reqh+1)^{th}$$$ cut $$$\rightarrow$$$ It has $$$2$$$ optimal gaps (before $$$x_v$$$ and the gap between $$$x_v$$$ and $$$y1_h$$$) so the probability is $$$\frac{2}{x+reqh+1}$$$.
   
   Now for finding the probability for $$$(reqh+i)^{th}$$$ cut, we first place this cut into one of the $$$2$$$ gaps and handle both cases separately.
   
   Gap before $$$x_v$$$: this case is similar to case 3c and the answer is just $$$\frac{1}{x+reqh+i}$$$.
   
   Gap between $$$x_v$$$ and $$$y1_h$$$. Here we again have to ensure that all lines from $$$reqh+1$$$ to $$$reqh+i-1$$$ occur after $$$reqh+i$$$.
   
   So we multiply $$$\frac{reqh+x}{reqh+x+2}\times\frac{reqs+x+1}{reqh+x+3}$$$ since after we place the $$$(reqh+i)^{th}$$$ cut, we have $$$(reqh+x)$$$ good gaps among a total of $$$(reqh+x+2)$$$ and so on for all the other lines we place (Their relative ordering does not matter since we are only concerned with $$$(reqh+i)^{th}$$$ cut).
   
   The final term for $$$(reqh+i)^{th}$$$ cut occurs out to be: $$$\frac{x+reqh}{(x+reqh+i)\cdot(x+reqh+i-1)}$$$.
   
   
   This forms a quadratic Harmonic Progression, the sum of which can be computed in $$$\mathcal{O}(1)$$$ using precomputation.
   
   

4. Case when the overall last cut is a vertical one and there is at least one horizontal cut:
   This case can be handled in a similar way as the previous case.

#include <bits/stdc++.h>                    
#define int long long    
using namespace std;
const long long N=2000005, mod=1000000007;

int power(int a, int b, int p)
{
    if(a==0)
    return 0;
    int res=1;
    a%=p;
    while(b>0)
    {
        if(b&1)
        res=(1ll*res*a)%p;
        b>>=1;
        a=(1ll*a*a)%p;
    }
    return res;
}

int pref[N], inv[N], pref2[N], hp2[N];

// Returns (1/l + 1/(l+1) + ... + 1/r)
int cal(int l, int r)
{
    if(l>r)
        return 0;
    return (pref[r]-pref[l-1]+mod)%mod;
}

// Returns (1/(l*(l+1)) + ... + 1/(r(r+1)))
int cal2(int l, int r)
{
    if(l>r)
        return 0;
    return (pref2[r]-pref2[l-1]+mod)%mod;
}
void pre()
{
    pref[0]=0;
    pref2[0]=0;
    for(int i=1;i<N;i++)
    {
        inv[i]=power(i, mod-2, mod);
        pref[i]=(pref[i-1]+inv[i])%mod;
        int mul2=(i*(i+1))%mod;
        pref2[i]=(pref2[i-1] + power(mul2, mod-2, mod))%mod;
        hp2[i]=((i*(i-1))%mod)%mod;
    }
}
int solve2(int n, int m, int k)
{
    if((n*m)<k)
        return 0;
    int ans=0;
    int reqv=(k-1)/n;
    if(reqv<m)
    {
        int prob=(reqv*inv[reqv+n-1])%mod;
        int exp=(prob*(1ll + cal(n+reqv, m+n-2)))%mod;
        ans=(ans + exp)%mod;
    }
    int reqh=(k-1)/m;
    if(reqh<n)
    {
        int prob=(reqh*inv[reqh+m-1])%mod;
        int exp=(prob*(1ll + cal(m+reqh, m+n-2)))%mod;
        ans=(ans + exp)%mod;
    }
    for(int i=1;i<min(n, k);i++)
    {
        reqv=(k-1)/i;
        if(reqv>=m)
            continue;
        int prob=(inv[i+reqv]*reqv)%mod;
        prob=(prob*inv[i-1+reqv])%mod;
        int num1=(hp2[i+reqv+1]*cal2(i+reqv, i+m-2))%mod;
        int num2=((i+reqv+1)*cal(i+reqv+1, i+m-1))%mod;
        int num=((num1+num2)*inv[i+reqv+1])%mod;
        int exp=(prob*(2ll + cal(i+reqv+1, reqv+(n-1))+num))%mod;
        ans=(ans + exp)%mod;
    }
    for(int i=1;i<min(m, k);i++)
    {
        reqh=(k-1)/i;
        if(reqh>=n)
            continue;
        int prob=(inv[i+reqh]*reqh)%mod;
        prob=(prob*inv[i-1+reqh])%mod;
        // Sum for cases when the (reqh+i)th horizontal line occurs in the gap b/w x_v and y1_h
        int num1=(hp2[i+reqh+1]*cal2(i+reqh, i+n-2))%mod;
        // Sum for cases when the (reqh+i)th horizontal line occurs in the gap to the left of x_v
        int num2=((i+reqh+1)*cal(i+reqh+1, i+n-1))%mod;
        int num=((num1+num2)*inv[i+reqh+1])%mod;
        int exp=(prob*(2ll + cal(i+reqh+1, reqh+(m-1))+num))%mod;
        ans=(ans + exp)%mod;
    }
    return ans;
}
int32_t main()
{
    pre();
    int t;
    cin>>t;
    while(t--)
    {
        int n, m, k;
        cin>>n>>m>>k;
        cout<<solve2(n, m, k)<<"\n";
    }
}

• Good problem:
• Ok problem:
• Bad problem:
• Did not attempt:

$$$\sqrt[4]{1.5}=1.1069$$$

Try to do a $$$3\rightarrow 2$$$ reduction in $$$4$$$ queries.

Try to do a $$$3\rightarrow 2$$$ reduction in such a way that if the middle part is eliminated $$$3$$$ queries are used otherwise $$$4$$$ queries are used.

Instead of dividing the search space into $$$3$$$ equal parts, divide it into parts having size $$$36\%$$$, $$$28\%$$$ and $$$36\%$$$.

There might be multiple strategies to solve this problem. I will describe one of them.

First, let's try to solve a slightly easier version where something like $$$\lceil \log_{1.1} n\rceil$$$ queries are allowed and subset queries are allowed instead of range queries.

The main idea is to maintain a search space of size $$$S$$$ and reduce it to a search space of size $$$\big\lceil \frac{2S}{3}\big\rceil$$$ using atmost $$$4$$$ queries. At the end, there will be exactly $$$2$$$ elements remaining in the search space which can be guessed. The number of queries required to reduce a search space of size $$$n$$$ to a search space of size $$$2$$$ using the above strategy will be equal to $$$4\cdot\log_{\frac{3}{2}}\frac{n}{2}$$$ $$$= \frac{\ln\frac{n}{2}}{0.25\ln 1.5}$$$ $$$= \frac{\ln n - \ln 2}{\ln 1.1067}$$$ $$$< \frac{\ln n - \ln 2}{\ln 1.1}$$$ $$$= \log_{1.1} n - 9.01$$$ $$$< \lceil\log_{1.1} n\rceil$$$.

Given below is one of the strategies how this can be achieved. Let the current search space be $$$T$$$. Divide $$$T$$$ into $$$3$$$ disjoint exhaustive subsets $$$T_1$$$, $$$T_2$$$ and $$$T_3$$$ of nearly equal size. Then follow the decision tree given below to discard one of the three subsets using at most $$$4$$$ queries.

It can seen that all the leaf nodes discard at least one-third of the search space based on the previous three queries.

Now, coming back to the problem where only ranges are allowed to be queried. This can be easily solved by choosing $$$T_1$$$, $$$T_2$$$ and $$$T_3$$$ in such a way that all elements of $$$T_1$$$ are less than all elements of $$$T_2$$$ and all elements of $$$T_2$$$ are less than all elements of $$$T_3$$$. Then all queries used in the above decision tree can be reduced to range queries since it really doesn't matter what are the actual elements of $$$T_1$$$, $$$T_2$$$ and $$$T_3$$$.

Finally, there is just one small optimization left to be done. Notice that when $$$T_2$$$ gets eliminated, only $$$3$$$ queries are used and when $$$T_1$$$ and $$$T_3$$$ get eliminated, $$$4$$$ queries are used. So, it must be more optimal to keep the size of $$$T_2$$$ smaller than $$$T_1$$$ and $$$T_3$$$ but by how much? The answer is given by the equation $$$(1-x)^3 = (2x)^4$$$. It has two imaginary and two real roots out of which only one is positive $$$x=0.35843$$$. So by taking the size of the segments approximately $$$36\%$$$, $$$28\%$$$ and $$$36\%$$$, you can do it in lesser number of queries which is less than $$$\max(\lceil\log_{\sqrt[4]{0.64^{-1}}} n\rceil, \lceil\log_{\sqrt[3]{0.72^{-1}}} n\rceil)-\log_{1.116} 2$$$ which is less than $$$\lceil\log_{1.116} n\rceil-1$$$.

During testing, the testers were able to come up with harder versions requiring lesser number of queries. Specifically, try to solve the problem under the following constraints assuming $$$n\leq 10^5$$$:

• Harder version: $$$70$$$ queries by dario2994
• Even harder version: $$$55$$$ queries by kevinsogo

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

void assemble(vector<int> &x,vector<int> &x1,vector<int> &x2,vector<int> &x3,string mask)
{
    x.clear();
    if(mask[0]=='1')
    {
        for(int i=0;i<x1.size();i++)
            x.push_back(x1[i]);
    }
    if(mask[1]=='1')
    {
        for(int i=0;i<x2.size();i++)
            x.push_back(x2[i]);
    }
    if(mask[2]=='1')
    {
        for(int i=0;i<x3.size();i++)
            x.push_back(x3[i]);
    }
}

bool query(vector<int> &x1,vector<int> &x2,vector<int> &x3,string mask)
{
    vector<int> x;
    assemble(x,x1,x2,x3,mask);
    int l=x[0],r=x.back();
    cout << "? " << l << " " << r << endl;
    int y;
    cin >> y;
    return (y==r-l);
}

void guess(int x)
{
    cout << "! " << x << endl;
    int y;
    cin >> y;
}

void finish()
{
    cout << "#" << endl;
}

int main()
{
    int tc;
    cin >> tc;
    while(tc--)
    {
        int n;
        cin >> n;
        vector<int> x;
        for(int i=1;i<=n;i++)
            x.push_back(i);
        while(x.size()>2)
        {
            int m = x.size();
            int k = round(0.36*m);
            vector<int> x1,x2,x3;
            for(int i=0;i<k;i++)
                x1.push_back(x[i]);
            for(int i=k;i<m-k;i++)
                x2.push_back(x[i]);
            for(int i=m-k;i<m;i++)
                x3.push_back(x[i]);
            if(query(x1,x2,x3,"110"))
            {
                if(query(x1,x2,x3,"100"))
                {
                    if(query(x1,x2,x3,"111"))
                    {
                        assemble(x,x1,x2,x3,"011");
                    }
                    else
                    {
                        assemble(x,x1,x2,x3,"110");
                    }
                }
                else
                {
                    if(query(x1,x2,x3,"110"))
                    {
                        assemble(x,x1,x2,x3,"101");
                    }
                    else
                    {
                        if(query(x1,x2,x3,"111"))
                        {
                            assemble(x,x1,x2,x3,"110");
                        }
                        else
                        {
                            assemble(x,x1,x2,x3,"011");
                        }
                    }
                }
            }
            else
            {
                if(query(x1,x2,x3,"100"))
                {
                    if(query(x1,x2,x3,"110"))
                    {
                        if(query(x1,x2,x3,"111"))
                        {
                            assemble(x,x1,x2,x3,"011");
                        }
                        else
                        {
                            assemble(x,x1,x2,x3,"110");
                        }
                    }
                    else
                    {
                        assemble(x,x1,x2,x3,"101");
                    }
                }
                else
                {
                    if(query(x1,x2,x3,"111"))
                    {
                        assemble(x,x1,x2,x3,"110");
                    }
                    else
                    {
                        assemble(x,x1,x2,x3,"011");
                    }
                }
            }
        }
        guess(x[0]);
        guess(x[1]);
        finish();
    }
}

• Good problem:
• Ok problem:
• Bad problem:
• Did not attempt:

Greedy

The answer depends on whether the length of $$$s$$$ is even or odd and on the first and last characters of $$$s$$$ if the length is odd.

The problem can be solved greedily. Let $$$n$$$ be the length of the given string.

• If the $$$n$$$ is even, it is always optimal for Alice to remove the whole string.
• If the $$$n$$$ is odd, it is always optimal for Alice to remove either $$$s_1s_2\ldots s_{n-1}$$$ or $$$s_2s_3\ldots s_n$$$ based on which gives the higher score and then Bob can remove the remaining character ($$$s_n$$$ or $$$s_1$$$ respectively). This is optimal because if Alice chooses to remove a substring of even length $$$2k$$$ such that $$$2k < n-1$$$ then Bob can remove the remaining $$$n-2k\geq 3$$$ characters, one of which will always be either $$$s_1$$$ or $$$s_n$$$, thus increasing Bob's score and decreasing Alice's score.

Prove that -

1. Bob can win if and only if the length of the string is $$$1$$$.
2. A draw is impossible.

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

int main()
{
    int tc;
    cin >> tc;
    while(tc--)
    {
        string s;
        cin >> s;
        int n=s.length(),alice=0;
        for(int i=0;i<n;i++)
            alice += s[i]-'a'+1;
        if(n%2==0)
            cout << "Alice " << alice << '\n';
        else
        {
            int bob;
            if(s[0]<=s[n-1])
                bob = s[0]-'a'+1;
            else
                bob = s[n-1]-'a'+1;
            alice -= bob;
            if(alice > bob)
                cout << "Alice " << alice-bob << '\n';
            else if(alice < bob)
                cout << "Bob " << bob-alice << '\n';
            else
                cout << "Draw " << 0 << '\n';
        }
    }
}

• Good problem:
• Ok problem:
• Bad problem:
• Did not attempt:

The string is perfectly balanced if it is periodic and the repeating pattern contains all distinct alphabets.

Let the number of distinct characters in $$$s$$$ be $$$k$$$ and length of $$$s$$$ be $$$n$$$. Then, $$$s$$$ will be perfectly balanced if and only if $$$s_{i}, s_{i+1}, \ldots, s_{i+k-1}$$$ are all pairwise distinct for every $$$i$$$ in the range $$$1\leq i\leq n-k+1$$$.

Prove that the condition is equivalent to the following two conditions -

1. The first $$$k$$$ characters of $$$s$$$ are pairwise distinct.
2. For each $$$i$$$ in the range $$$1\leq i\leq n-k$$$, $$$s_i=s_{i+k}$$$.

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

int main()
{
    int tc;
    cin >> tc;
    while(tc--)
    {
        string s;
        cin >> s;
        int n = s.length();
        set<char> c;
        bool ok = true;
        int k;
        for(k=0;k<n;k++)
        {
            if(c.find(s[k])==c.end())
                c.insert(s[k]);
            else
                break;
        }
        for(int i=k;i<n;i++)
        {
            if(s[i]!=s[i-k])
                ok = false;
        }
        if(ok)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}

• Good problem:
• Ok problem:
• Bad problem:
• Did not attempt:

The number of palindromes less than $$$4\cdot 10^4$$$ is relatively small.

The rest of the problem is quite similar to the classical partitions problem.

First, we need to observe that the number of palindromes less than $$$4\cdot 10^4$$$ is relatively very small. The number of $$$5$$$-digit palindromes are $$$300$$$ (enumerate all $$$3$$$-digit numbers less than $$$400$$$ and append the first two digits in the reverse order). Similarly, the number of $$$4$$$-digit, $$$3$$$-digit, $$$2$$$-digit and $$$1$$$-digit palindromes are $$$90$$$, $$$90$$$, $$$9$$$ and $$$9$$$ respectively, giving a total of $$$M=498$$$ palindromes.

Now, the problem can be solved just like the classical partitions problem which can be solved using Dynamic Programming.

Let $$$dp_{k,m} =$$$ Number of ways to partition the number $$$k$$$ using only the first $$$m$$$ palindromes. It is not hard to see that $$$dp_{k,m} = dp_{k,m-1} + dp_{k-p_m,m}$$$ where $$$p_m$$$ denotes the $$$m^{th}$$$ palindrome. The first term corresponds to the partitions of $$$k$$$ using only the first $$$m-1$$$ palindromes and the second term corresponds to those partitions of $$$k$$$ in which the $$$m^{th}$$$ palindrome has been used atleast once. As base cases, $$$dp_{k,1}=1$$$ and $$$dp_{1,m}=1$$$. The final answer for any $$$n$$$ will be $$$dp_{n,M}$$$.

The time and space complexity is $$$\mathcal{O}(n\cdot M)$$$.

Try to optimize the space complexity to $$$\mathcal{O}(n)$$$.

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

const int N = 40004, M = 502;
const long long MOD = 1000000007;
long long dp[N][M];

int reverse(int n)
{
    int r=0;
    while(n>0)
    {
        r=r*10+n%10;
        n/=10;
    }
    return r;
}

bool palindrome(int n)
{
    return (reverse(n)==n); 
}

int main()
{
    vector<int> palin;
    palin.push_back(0);
    for(int i=1;i<2*N;i++)
    {
        if(palindrome(i))
            palin.push_back(i);
    }
    for(int j=1;j<M;j++)
        dp[0][j]=1;
    for(int i=1;i<N;i++)
    {
        dp[i][0]=0;
        for(int j=1;j<M;j++)
        {
            if(palin[j]<=i)
                dp[i][j]=(dp[i][j-1]+dp[i-palin[j]][j])%MOD;
            else
                dp[i][j]=dp[i][j-1];
        }
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--)
    {
        int n;
        cin >> n;
        cout << dp[n][M-1] << '\n';
    }
}

• Good problem:
• Ok problem:
• Bad problem:
• Standardish problem and boring to solve:
• Standardish problem but learned something new today
• Did not attempt:

First check if all elements of $$$C$$$ are present in $$$B$$$ or not. If not, the answer is $$$0$$$.

Then check if the answer is infinite or not. It depends on only the first and last elements of $$$B$$$ and $$$C$$$.

If $$$p$$$ is the common difference of $$$A$$$ then $$$lcm(p,q)=r$$$. $$$p$$$ must necessarily be a factor of $$$r$$$ and $$$\mathcal{O}(\sqrt n)$$$ works here.

If all elements of $$$C$$$ are not present in $$$B$$$, then the answer is $$$0$$$. It is sufficient to check the following $$$4$$$ conditions to check if all elements of $$$C$$$ are present in $$$B$$$ or not -

• The first term of $$$B\leq$$$ The first term of $$$C$$$, i.e., $$$b\leq c$$$.
• The last term of $$$B\geq$$$ The last term of $$$C$$$, i.e., $$$b+(y-1)q\geq c+(z-1)r$$$.
• The common difference of $$$C$$$ must be divisible by the common difference of $$$B$$$, i.e., $$$r\bmod q=0$$$.
• The first term of $$$C$$$ must lie in $$$B$$$, i.e., $$$(c-b)\bmod q=0$$$.

Now suppose the following conditions are satisfied. Let's denote an Arithmetic Progression (AP) with first term $$$a$$$, common difference $$$d$$$ and $$$n$$$ number of terms by $$$[a,d,n]$$$.

If $$$b>c-r$$$ then there are infinite number of progressions which can be $$$A$$$ like $$$[c,r,z]$$$, $$$[c-r,r,z+1]$$$, $$$[c-2r,r,z+2]$$$ and so on. Similarly, if $$$b+(y-1)q<c+zr$$$, there are infinite number of progressions which can be $$$A$$$ like $$$[c,r,z]$$$, $$$[c,r,z+1]$$$, $$$[c,r,z+2]$$$ and so on.

Otherwise, there are a finite number of progressions which can be $$$A$$$. Let's count them. Let $$$A$$$ be the AP $$$[a,p,x]$$$ and $$$l=a+(x-1)p$$$. It can be seen that $$$lcm(p,q)=r$$$, $$$(c-a)\bmod p=0$$$, $$$a>c-r$$$ and $$$l<c+rz$$$ for any valid $$$A$$$. The first two conditions are trivial. The third condition is necessary because if $$$a\leq c-r$$$ then $$$c-r$$$ will always be present in both $$$A$$$ and $$$B$$$ contradicting the fact that $$$C$$$ contains all the terms common to $$$A$$$ and $$$B$$$. Similarly, the fourth condition is also necessary.

The only possible values $$$p$$$ can take according to the first condition are factors of $$$r$$$ which can be enumerated in $$$\mathcal{O}(\sqrt{r})$$$. The $$$lcm$$$ condition can be checked in $$$\mathcal{O}(\log r)$$$. For a particular value of $$$p$$$, there are $$$\frac{r}{p}$$$ possible values of $$$a$$$ satisfying conditions 2 and 3 and $$$\frac{r}{p}$$$ possible values of $$$l$$$ satisfying conditions 2 and 4. Thus, the answer is $$$\displaystyle\sum_{lcm(p,q)=r}\Big(\frac{r}{p}\Big)^2$$$.

Time complexity: $$$\mathcal{O}(t\,\sqrt{r}\,\log r)$$$

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

const long long MOD = 1000000007;

long long gcd(long long a,long long b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}

long long lcm(long long a,long long b)
{
    long long g = gcd(a,b);
    return (a*b)/g;
}

int main()
{
    int tc;
    cin >> tc;
    while(tc--)
    {
        long long b,c,q,r,y,z;
        cin >> b >> q >> y;
        cin >> c >> r >> z;
        long long e = b+q*(y-1);
        long long f = c+r*(z-1);
        if(c<b || c>e || f<b || f>e || r%q!=0 || (c-b)%q!=0)
            cout << 0 << '\n';
        else if(c-r<b || f+r>e)
            cout << -1 << '\n';
        else
        {
            long long ans = 0;
            for(long long p=1;p*p<=r;p++)
            {
                if(r%p==0)
                {
                    if(lcm(p,q)==r)
                    {
                        long long a = ((r/p)*(r/p))%MOD;
                        ans = (ans+a)%MOD;
                    }
                    if(p*p!=r && lcm(r/p,q)==r)
                    {
                        long long a = (p*p)%MOD;
                        ans = (ans+a)%MOD;
                    }
                }
            }
            cout << ans << '\n';
        }
    }
}

• Good problem:
• Ok problem:
• Bad problem:
• Did not attempt:

All numbers in $$$A$$$ are powers of $$$2$$$ and the modulo is also a power of $$$2$$$ and $$$B_i\geq 1$$$.

Fix all operators in a particular subsegment as $$$\texttt{Power}$$$ and fix the operators around the segment as $$$\texttt{XOR}$$$. Find the contribution of this segment independent of other segments.

Maximum possible length for such a subsegment which can contribute to the answer is $$$20$$$.

Use Lucas' Theorem or Submasks DP or precomputation in order to count the parity of the number of valid unambiguous expressions in which the subsegment appears as in Hint 2.

Let's consider a subsegment $$$[A_{l}\wedge A_{l+1}\wedge A_{l+2}\wedge\ldots\wedge A_r]$$$. Let all the $$$\wedge$$$ symbols in this segment be replaced by $$$\texttt{Power}$$$ and the $$$\wedge$$$ symbols before $$$A_l$$$ and after $$$A_r$$$ be replaced by $$$\texttt{XOR}$$$. Then the value of this segment will not be affected by the rest of the expression. Moreover, out of all the expressions in which this segment appears as above, it will contribute the same value to the final answer. Since the final answer is also a $$$\texttt{XOR}$$$, if the segment $$$[l\ldots r]$$$ appears in the above mentioned form in odd number of valid unambiguous expressions, it will contribute $$$(\ldots((A_l^{A_{l+1}})^{A_{l+2}}) \ldots )^ {A_r}$$$ to the final answer else it will contribute nothing. We can find the contribution of each segment $$$[l\ldots r]$$$ independently for all values of $$$1\leq l < r \leq n$$$.

Now, there are two things we need to find out:

1. How much $$$(\ldots((A_l^{A_{l+1}})^{A_{l+2}}) \ldots )^ {A_r}$$$ will contribute to the final answer, modulo $$$MOD = 2^{1048576}$$$.
2. What is the parity of the count of valid unambiguous expressions, in which the segment $$$[l...r]$$$ appears as $$$... \oplus (\ldots((A_l^{A_{l+1}})^{A_{l+2}}) \ldots )^ {A_r} \oplus \ldots$$$.

Part 1: Notice that since all the elements of $$$A$$$ are powers of $$$2$$$, $$$S(l,r)=(\ldots((A_l^{A_{l+1}})^{A_{l+2}}) \ldots )^ {A_r}$$$ will also be a power of $$$2$$$. It means that $$$\texttt{XOR}$$$-ing it with answer will flip not more than $$$1$$$ bit in the answer. The rest of the calculations is pretty straightforward. $$$S(l,r) = 2^{B_l\cdot A_{l+1}\cdot A_{l+2}\cdot\ldots\cdot A_{r}}$$$ by properties of exponents. So, if it contributes to the answer, it will flip the $$$B_l\cdot A_{l+1}\cdot A_{l+2}\cdot\ldots\cdot A_{r}-$$$th bit of the answer. Now, note that if $$$S\geq 2^{1048576}$$$, it will have no effect on the answer because $$$S(l,r) \bmod 2^{1048576}$$$ will then be $$$0$$$. So, we care only for those $$$(l,r)$$$ for which $$$S(l,r) < 2^{1048576}$$$. Since $$$B_i\geq 1$$$, $$$A_i\geq 2$$$ and so, $$$r-l \leq 20$$$ because $$$2^{20} = 1048576$$$. Thus, it is sufficient to calculate $$$S(l,r)$$$ for only $$$20$$$ values of $$$r$$$ per value of $$$l$$$.

Part 2: We have used $$$r-l$$$ $$$\wedge$$$ operators as $$$\texttt{Power}$$$ and $$$0$$$, $$$1$$$ or $$$2$$$ $$$\wedge$$$ operators as $$$\texttt{XOR}$$$. Let's say that out of the $$$m$$$ unused operators, we need to use at least $$$q$$$ of them as $$$\texttt{XOR}$$$. Then the number of ways to do this is $$$\binom{m}{q}+\binom{m}{q+1}+\binom{m}{q+2}+\ldots+\binom{m}{m}$$$. Infact, instead of finding this value, we are only interested in finding whether it is even or odd. So, we need the value of $$$\big[\binom{m}{q}+\binom{m}{q+1}+\binom{m}{q+2}+\ldots+\binom{m}{m}\big]\bmod 2=$$$ $$$\big[\binom{m-1}{q}+\binom{m-1}{q-1} + \binom{m-1}{q+1}+\binom{m-1}{q} + \binom{m-1}{q+2}+\binom{m-1}{q+1} + \ldots + \binom{m-1}{m-1}+\binom{m-1}{m-2} + \binom{m}{m}\big] \bmod 2=$$$ $$$\big[\binom{m-1}{q-1} + \binom{m-1}{m-1} + \binom{m}{m}]\bmod 2 =$$$ $$$\binom{m-1}{q-1} \bmod 2$$$ as $$$(a + a) \bmod 2 = 0$$$ and $$$\binom{x}{x} = 1$$$ by definition. $$$\binom{m-1}{q-1} \bmod 2$$$ can be found using Lucas' Theorem. It turns out that $$$\binom{n}{r}$$$ is odd if and only if $$$r$$$ is a submask of $$$n$$$, i.e., $$$n | r = n$$$. Note that there are also many other ways to find this value (like Submasks DP or using the fact that $$$r-l\leq 20$$$ for precomputation) but this is the easiest one.

Some final notes -

1. We can maintain the final answer as a binary string of length $$$1048576$$$. Find the value $$$X = B_l\cdot A_{l+1}\cdot A_{l+2}\cdot\ldots\cdot A_{r}$$$ and if the required parity is odd and $$$X < 1048576$$$, flip the $X-$th bit of the string.
2. We need to be careful while calculating $$$B_l\cdot A_{l+1}\cdot A_{l+2}\cdot\ldots\cdot A_{r}$$$ since $$$A_i$$$ can be as large as $$$2^{1048575}$$$. But since we are interested in values that evaluate to something smaller than $$$1048576$$$, we will never try to multiply $$$A_i$$$ for anything with $$$B_i > 20$$$.
3. Calculating the parity of $$$\binom{n}{r}$$$ in $$$\mathcal{O}(\log n)$$$ may time out. The constraints are strict enough.

Total time Complexity — $$$\mathcal{O}(n \log \log MOD)$$$

Try to solve the problem if $$$B_i\geq 0$$$ and if powers are calculated from right to left.

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

const int N = 1048576;
long long b[N];
char ans[N];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,k;
    cin >> n >> k;
    for(int i=0;i<n;i++)
    {
        cin >> b[i];
    }
    for(int i=0;i<1048576;i++)
        ans[i]='0';
    for(int l=0;l<n;l++)
    {
        long long p=1;
        for(int r=l;r<n;r++)
        {
            if(r==l)
                p*=b[r];
            else
            {
                if(b[r]>=20)
                    break;
                else
                    p*=(1ll<<b[r]);
            }
            if(p>=1048576)
                break;
            int m = n-r+l-3;
            int q = k-2;
            if(l==0)
            {
                m++;
                q++;
            }
            if(r==n-1)
            {
                m++;
                q++;
            }
            if(m>=q && (m==0 || (q>0 && ((m-1)|(q-1))==(m-1))))
                ans[p]='1'+'0'-ans[p];
        }
    }
    bool start=false;
    for(int i=1048575;i>=0;i--)
    {
        if(ans[i]=='0' && start)
            cout << 0;
        else if(ans[i]=='1')
        {
            cout << 1;
            start=true;
        }
    }
    if(!start)
        cout << 0;
    cout << '\n';
}

• Good problem:
• Ok problem:
• Bad problem:
• Did not attempt:

The main goal is to assign numbers $$$A_{i,j}$$$ from $$$0$$$ to $$$1023$$$ to all buildings such that all buildings get distinct numbers and assign the road lengths between buildings $$$B_{x_1,y_1}$$$ and $$$B_{x_2,y_2}$$$ as $$$A_{x_1,y_1}\oplus A_{x_2,y_2}$$$. Among all such assignments, try to find the one which has the least sum of road lengths.

$$$2$$$-Dimensional Gray Code works

For now, lets ignore $$$n<=32$$$ and assume $$$n=32$$$.

Let's try to build the roads in such a way that no matter what path the thief takes to reach building $$$B_{i,j}$$$, the tracker will always return a fixed value $$$A_{i,j}$$$ such that all $$$A_{i,j}$$$ are distinct. Then by knowing the values returned by the tracker, one can easily find which building the theft occurred in. The main problem here is not to choose the lengths of the roads, since by choosing the length of road between buildings $$$B_{x_1,y_1}$$$ and $$$B_{x_2,y_2}$$$ as $$$A_{x_1,y_1}\oplus A_{x_2,y_2}$$$, one can always achieve this property. But there is a constraint which needs to be satisfied: The total length of all roads must not exceed $$$48000$$$. This is, in fact, a tight constraint (model solution uses $$$47616$$$) due to which one needs to choose the values of $$$A_{i,j}$$$ very efficiently.

Consider this problem — Find a permutation of numbers from $$$0$$$ to $$$2^m-1$$$ such that the sum of XOR of consecutive integers is minimized. The answer to this is Gray Code or Reflected Binary Code. In the standard Gray Code, bit $$$0$$$ is flipped $$$2^{m-1}$$$ times, bit $$$1$$$ is flipped $$$2^{m-2}$$$ times, bit $$$2$$$ is flipped $$$2^{m-3}$$$ times, $$$\ldots$$$, bit $$$m-1$$$ is flipped $$$1$$$ time. The idea is to use small bits more number of times compared to the larger ones.

Our task is to implement this idea in $$$2$$$-dimensions. Let's look at the algorithm used to build Gray Code. If we have the Gray Code for $$$k$$$ bits, it can be extended to $$$k+1$$$ bits by taking a copy of it, reflecting it and appending $$$1$$$ to the beginning of the reflected code and $$$0$$$ to the beginning of the original one. Here, if we have the Gray Code for $$$2^k \times 2^k$$$ matrix, it can be first extended to a Gray Code for $$$2^k \times 2^{k+1}$$$ matrix and this can further be extended to a Gray Code for $$$2^{k+1} \times 2^{k+1}$$$ matrix. If we build a $$$2^m \times 2^m$$$ matrix using this algorithm, the total length of roads used will be $$$\frac{3}{2}\cdot(4^m)\cdot(2^m-1)$$$. In this problem, $$$m = 5$$$. So, total length of roads used = $$$\frac{3}{2} \cdot 1024 \cdot 31 = 47616$$$.

Once this construction is complete, finding the buildings where thefts occurred is elementary since there can now be only one building corresponding to each value returned by the tracker.

Now, coming back to the original problem, we can simply take the first $$$n$$$ rows and the first $$$n$$$ columns from the constructed matrix. The cost won't increase and the properties still hold.

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

const int N = 32;

int maxpower2(int n)
{
    int p=1;
    while(n%2==0)
    {
        p*=2;
        n/=2;
    }
    return p;
}

int main()
{
    int n,k;
    cin >> n >> k;
    int h[N][N-1];
    for(int i=0;i<N;i++)
    {
        for(int j=1;j<=N-1;j++)
        {
            h[i][j-1]=maxpower2(j)*maxpower2(j);
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n-1;j++)
        {
            cout << h[i][j] << " ";
        }
        cout << endl;
    }
    int v[N-1][N];
    for(int i=1;i<=N-1;i++)
    {
        for(int j=0;j<N;j++)
        {
            v[i-1][j]=2*maxpower2(i)*maxpower2(i);
        }
    }
    for(int i=0;i<n-1;i++)
    {
        for(int j=0;j<n;j++)
        {
            cout << v[i][j] << " ";
        }
        cout << endl;
    }
    int b[n][n];
    b[0][0]=0;
    for(int j=1;j<n;j++)
    {
        b[0][j]=b[0][j-1]^h[0][j-1];
    }
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            b[i][j]=b[i-1][j]^v[i-1][j];
        }
    }
    map<int,pair<int,int> > m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            m[b[i][j]]={i,j};
        }
    }
    int y=0;
    while(k--)
    {
        int x;
        cin >> x;
        pair<int,int> ans = m[x^y];
        cout << ans.first+1 << " " << ans.second+1 << endl;
        y^=x;
    }
}

• Good problem:
• Ok problem:
• Bad problem:
• Did not attempt:

No powers of $$$2$$$ were harmed during the making of this round. Always remember that $$$1048576$$$ is the most superior power of $$$2$$$.

$$$GCD(a,b)=GCD(a-b,b)$$$ if $$$a>b$$$

$$$a-b$$$ does not change by applying any operation. However, $$$b$$$ can be changed arbitrarily.

If $$$a=b$$$, the fans can get an infinite amount of excitement, and we can achieve this by applying the first operation infinite times.

Otherwise, the maximum excitement the fans can get is $$$g=\lvert a-b\rvert$$$ and the minimum number of moves required to achieve it is $$$min(a\bmod g,g-a\bmod g)$$$.

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--)
    {
        long long a,b;
        cin >> a >> b;
        if(a==b)
            cout << 0 << " " << 0 << '\n';
        else
        {
            long long g = abs(a-b);
            long long m = min(a%g,g-a%g);
            cout << g << " " << m << '\n';
        }
    }
}

In the optimal arrangement, the number of cars will be distributed as evenly as possible.

In the optimal arrangement, the number of traffic cars will be distributed as evenly as possible, i.e., $$$\lvert a_i-a_j\rvert\leq 1$$$ for each valid $$$(i,j)$$$.

Now that we have constructed the optimal arrangement of traffic cars, let's find out the value of minimum inconvenience of this optimal arrangement. Finding it naively in $$$\mathcal{O}(n^2)$$$ will time out.

Notice that in the optimal arrangement we will have some (say $$$x$$$) elements equal to some number $$$p+1$$$ and the other $$$(n-x)$$$ elements equal to $$$p$$$. Let the sum of all elements in $$$a$$$ be $$$sum$$$. Then, $$$x=sum\bmod n$$$ and $$$p=\bigg\lfloor\dfrac{sum}{n}\bigg\rfloor$$$. For each pair $$$(p,p+1)$$$, we will get an absolute difference of $$$1$$$ and for all other pairs, we will get an absolute difference of $$$0$$$. Number of such pairs with difference $$$1$$$ is equal to $$$x\cdot(n-x)$$$. So, the minimum inconvenience we can achieve is equal to $$$x\cdot(n-x)$$$. That's all we need to find out!

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        int a[n];
        long long s=0;
        for(int i=0;i<n;i++)
        {
            cin >> a[i];
            s+=a[i];
        }
        long long k = s%n;
        long long ans = k*(n-k);
        cout << ans << '\n';
    }
}

Did you notice that $$$v\geq 0.1$$$?

The probability of drawing a pink slip can never decrease.

What would be the complexity of a bruteforce solution?

Make sure to account for precision errors while comparing floating point numbers.

Bruteforce over all the possible drawing sequences until we are sure to get a pink slip, i.e., until the probability of drawing a pink slip becomes $$$1$$$.

What's left is just implementing the bruteforce solution taking care of precision errors while dealing with floating point numbers, especially while comparing $$$a$$$ with $$$v$$$ as this can completely change things up, keeping an item valid when it should become invalid. It follows that an error approximation of 1e-6 or smaller is sufficient while comparing any two values because all the numbers in the input have at most $$$4$$$ decimal places. Another alternative is to convert floating point numbers given in the input to integers using a scaling factor of $$$10^6$$$.

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

const long double eps = 1e-9;
const long double scale = 1e+6;

long double expectedRaces(int c,int m,int p,int v)
{
    long double ans = p/scale;
    if(c>0)
    {
        if(c>v)
        {
            if(m>0)
                ans += (c/scale)*(1+expectedRaces(c-v,m+v/2,p+v/2,v));
            else
                ans += (c/scale)*(1+expectedRaces(c-v,0,p+v,v));
        }
        else
        {
            if(m>0)
                ans += (c/scale)*(1+expectedRaces(0,m+c/2,p+c/2,v));
            else
                ans += (c/scale)*(1+expectedRaces(0,0,p+c,v));
        }
    }
    if(m>0)
    {
        if(m>v)
        {
            if(c>0)
                ans += (m/scale)*(1+expectedRaces(c+v/2,m-v,p+v/2,v));
            else
                ans += (m/scale)*(1+expectedRaces(0,m-v,p+v,v));
        }
        else
        {
            if(c>0)
                ans += (m/scale)*(1+expectedRaces(c+m/2,0,p+m/2,v));
            else
                ans += (m/scale)*(1+expectedRaces(0,0,p+m,v));
        }
    }
    return ans;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        long double cd,md,pd,vd;
        cin >> cd >> md >> pd >> vd;
        int c = round(cd*scale);
        int m = round(md*scale);
        int p = round(pd*scale);
        int v = round(vd*scale);
        long double ans = expectedRaces(c,m,p,v);
        cout << setprecision(12) << fixed << ans << '\n';
    }
}

In this version, $$$x\oplus z=y$$$ or in other words, $$$z=x\oplus y$$$ where $$$\oplus$$$ is the Bitwise XOR operator.

The number of queries allowed is equal to the number of possible initial passwords.

The grader provides us no information other than whether our guess was correct or not. So, we need to find a way to ask queries such that the $$$x$$$-th query will give the correct answer if the original password was $$$(x-1)$$$.

Try to ask queries in such a way that the $$$i$$$-th query reverses the effect of the $$$(i-1)$$$-th query and simultaneously checks if the initial password was $$$(i-1)$$$.

Try to use the self-inverse property of Bitwise XOR, i.e., $$$a\oplus a=0$$$.

In this version of the problem, $$$k=2$$$. So, the $$$k$$$-itwise XOR is the same as Bitwise XOR.

In case of incorrect guess, the system changes password to $$$z$$$ such that $$$x\oplus z=y$$$. Taking XOR with $$$x$$$ on both sides, $$$x\oplus x\oplus z=x\oplus y\implies z=x\oplus y$$$ because we know that $$$x\oplus x = 0$$$.

Since the original password is less than $$$n$$$ and we have $$$n$$$ queries, we need to find a way to make queries such that if the original password was $$$(x-1)$$$, then the $$$x$$$-th query will be equal to the current password. There are many different approaches. I will describe two of them.

The generalised $$$k$$$-itwise XOR does not satisfy the Self-Inverse property. So, the solution for the Easy Version won't work here.

Any property which is satisfied by $$$k$$$-its will also be satisfied by base $$$k$$$ numbers since a base $$$k$$$ number is nothing but a concatenation of $$$k$$$-its. So, try to prove properties for $$$k$$$-its as they are easier to work with.

Let $$$x_j$$$ denote the $$$j$$$-th $$$k$$$-it of $$$x$$$. Then, $$$x_j\oplus_k z_j=y_j$$$ $$$\forall$$$ valid $$$j$$$. Simplifying this,
$$$x_j\oplus_k z_j=y_j$$$ $$$\implies$$$ $$$(x_j+z_j)\bmod k=y_j$$$ $$$\implies$$$ $$$z_j=(y_j-x_j)\bmod k$$$ $$$\implies$$$ $$$z_j=(y_j\ominus_k x_j)$$$ where $$$a\ominus_k b$$$ operation is defined as $$$a\ominus_k b=(a-b)\bmod k$$$.

See Hints 2, 3 and 4 of the Easy Version.

Try to generalise the solutions for easy version by exploring properties of $$$\oplus_k$$$ and $$$\ominus_k$$$ operators.

Note — It is strongly recommended to read the proofs also to completely understand why the solutions work.

The solutions described for the easy version won't work here because the general $$$k$$$-itwise operation does not satisfy self-inverse property, i.e., $$$a\oplus_k a\neq 0$$$.

In this whole solution, we will work in base $$$k$$$ only and we will convert the numbers to decimal only for I/O purpose. Notice that any property which is satisfied by $$$k$$$-its will also be satisfied by base $$$k$$$ numbers since a base $$$k$$$ number is nothing but a concatenation of $$$k$$$-its.

When we make an incorrect guess, the system changes the password to $$$z$$$ such that $$$x\oplus_k z=y$$$. Let's denote the $$$j$$$-th $$$k$$$-it of $$$x$$$ by $$$x_j$$$. Expanding this according to the definition of $$$k$$$-itwise XOR, for all individual $$$k$$$-its $$$(x_j+z_j)\bmod k=y_j$$$ $$$\implies z_j=(y_j-x_j)\bmod k$$$. So, let's define another $$$k$$$-itwise operation $$$a\ominus_k b$$$ $$$= (a-b)\bmod k$$$. Then, $$$z=y\ominus_k x$$$. Now, let's extend the solutions of the Easy Version for this version.

This part may be interesting for hackers and those who would like to understand what goes in the background checkers and interactors which determine the correctness of their solutions.

You must have noticed a large number of submissions failing on Test 1 itself. If you check the checker logs of those solutions, you will find that they fail on many different test cases although the test itself has 1 or 2 test cases. This is because the grader is also adaptive apart from the Rap Sheet System being adaptive. The initial password is not fixed and the grader checks if the solution will give correct answer or not for all possible initial passwords in just a single run! Here is how this is implemented.

The grader maintains a set which initially contains all possible initial passwords. Whenever you ask a query, the grader finds out which initial password will give correct answer for this query. This is found using the generalised expression of queries derived in the Method 2 solution. Take some time to convince yourself that this initial password will be unique. It then removes this initial password from the set if it still exists. After that, if the set is empty, the grader returns 1 (meaning that there is no other password for which the solution can give Wrong Answer), otherwise 0 (obviously after checking the constraints on $$$y$$$). In this way, only a solution which gives correct answers for all possible initial passwords for a particular $$$n$$$ and $$$k$$$ defined in the input will manage to pass.

Sometimes, checkers and adaptive interactors are more difficult to write than the solution itself! This was one such case.

In a simple $$$n$$$-Dimensional Hypercube, two vertices are connected if and only if they differ by exactly $$$1$$$ bit in their binary representation.

The $$$n$$$-Dimensional Hypercubes are highly symmetric and all vertices are equivalent.

If we select a particular vertex, then all directions in which the edges connected to it goes are also equivalent.

For any two vertices $$$a$$$ and $$$b$$$ separated at a distance of exactly $$$2$$$, there are exactly $$$2$$$ vertices connected to both $$$a$$$ and $$$b$$$.

Any permuted $$$n$$$-Dimensional Hypercube is isomorphic to the simple $$$n$$$-Dimensional Hypercube. So, its structure is same as the simple $$$n$$$-Dimensional Hypercube.

You can find the permutation greedily

Before moving to the solution, notice a very important property of simple $$$n$$$-Dimensional Hypercubes — Two vertices $$$a$$$ and $$$b$$$ are connected if and only if $$$a$$$ and $$$b$$$ differ by exactly one bit in their binary representations.

The permutation can be found using the following greedy algorithm — First, assign any arbitrary vertex as $$$p_0$$$. This is obvious since all vertices are equivalent. Then, in the simple $$$n$$$-Dimensional Hypercube, all powers of $$$2$$$ must be connected to the vertex $$$0$$$. Moreover, these vertices are added only when we are adding another dimension to the cube. Since all directions are also equivalent, it does not matter in which direction we add a new dimension. So, we can assign all the $$$n$$$ vertices connected to $$$p_0$$$ in the permuted $$$n$$$-Dimensional Hypercube as $$$p_1$$$, $$$p_2$$$, $$$p_4$$$, $$$p_8$$$, $$$\ldots$$$, $$$p_{2^{n-1}}$$$ in any arbitrary order. Now, we will find $$$p_u$$$ for the remaining vertices in increasing order of $$$u$$$.

In order to find $$$p_u$$$, first find a set $$$S$$$ of vertices $$$v$$$ such that $$$v < u$$$ and $$$v$$$ is connected to $$$u$$$ in the simple $$$n$$$-Dimensional Hypercube. Then find any vertex $$$w$$$ connected to all the vertices $$$p_v$$$ such that $$$v\in S$$$ in the permuted $$$n$$$-Dimensional Hypercube and assign $$$p_u=w$$$. I claim that we can never make a wrong choice because we will never have a choice! There will only be one such vertex $$$w$$$ for any $$$u$$$. Let's prove it.

Instead of colouring the permuted $$$n$$$-Dimensional Hypercube, try to colour the simple $$$n$$$-Dimensional Hypercube and map these colours to the permuted one in the end using the permutation found in Part 1.

The number of vertices of each colour will be equal.

Try to colour a simple $$$4$$$-Dimensional Hypercube. This is not a graph problem, rather a constructive problem.

The way in which vertices are connected in a simple $$$n$$$-Dimensional Hypercube suggests something related to Bitwise XOR.

Let's try to colour the simple $$$n$$$-Dimensional Hypercube instead of the permuted one. We can map the colours to the permuted one in the end using the permutation found in Part 1.

I claim that if $$$n$$$ is not a power of $$$2$$$, then no colouring exists. A simple explanation is that the graph is symmetric and also the colours. So, it is natural that the number of vertices of each colour must be equal meaning $$$2^n$$$ must be divisible by $$$n$$$ or in other words, $$$n$$$ must be a power of $$$2$$$ itself. But if symmetry doesn't satisfy you, I have a formal proof too.

Construction - This is the most interesting and difficult part of the whole problem. The following construction works —

Consider a vertex $$$u$$$. Let its binary representation be $$$b_{n-1}b_{n-2}\ldots b_2 b_1 b_0$$$. Then the colour of this vertex will be $$$\bigoplus\limits_{i=0}^{n-1} i\cdot b_i$$$. Let's show why this works.

• $$$\bigoplus\limits_{i=0}^{n-1} i\cdot b_i$$$ will always lie between $$$0$$$ and $$$n-1$$$ inclusive because $$$n$$$ is a power of $$$2$$$.
• If we are at a vertex $$$u$$$ with a colour $$$c_1$$$ and we want to reach a vertex of colour $$$c_2$$$, we can reach the vertex $$$v=u\oplus(1\ll (c_1\oplus c_2))$$$. This is a vertex adjacent to $$$u$$$ since it differs from it by exactly $$$1$$$ bit and this is the $$$(c_1\oplus c_2)$$$-th bit. Notice that the colour of this vertex $$$v$$$ will be $$$c_1\oplus (c_1\oplus c_2) = c_2$$$.
• $$$(c_1\oplus c_2)$$$ will always lie between $$$0$$$ and $$$n-1$$$ because $$$n$$$ is a power of $$$2$$$. So, $$$v$$$ will always be a valid vertex number.

You can see that many of these facts break when $$$n$$$ is not a power of $$$2$$$. So, this colouring will not work in such cases.

Finally, after colouring the simple hypercube, we need to restore the vertex numbers of the permuted hypercube. This can be simply done by replacing all vertices $$$u$$$ with $$$p_u$$$ using the permutation we found in Part 1.

Well, that's enough of theoretical stuff. For those who like visualising things, here is a 4-D Hypercube and its colouring -

Finding the permutation takes $$$\mathcal{O}(n\cdot\log_2 n\cdot 2^n)$$$ time if implemented using set or $$$\mathcal{O}(n^2\cdot 2^n)$$$ time if implemented using vector. Constructing the colouring for the simple $$$n$$$-Dimensional Hypercube takes $$$\mathcal{O}(n\cdot 2^n)$$$ time. Restoring colours for the permuted $$$n$$$-Dimensional Hypercube takes $$$\mathcal{O}(2^n)$$$ time.

So, the overall time complexity is $$$\mathcal{O}(n\cdot\log_2 n\cdot 2^n)$$$ or $$$\mathcal{O}(n^2\cdot 2^n)$$$ depending upon implementation.

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

void permuteHypercube(int n,int m,vector<int> adj[],set<int> s[],int p[])
{
    for(int i=0;i<m;i++)
        p[i]=-1;
    bool used[m];
    for(int i=0;i<m;i++)
        used[i]=false;
    p[0]=0;
    used[0]=true;
    for(int u=1;u<m;u++)
    {
        vector<int> req;
        for(int i=0;i<n;i++)
        {
            int v=u^(1<<i);
            if(v<u)
                req.push_back(v);
        }
        if(req.size()==1)
        {
            int v=req[0];
            for(int i=0;i<adj[p[v]].size();i++)
            {
                int w=adj[p[v]][i];
                if(used[w])
                    continue;
                p[u]=w;
                used[w]=true;
                break;
            }
        }
        else
        {
            int v=req[0];
            for(int i=0;i<adj[p[v]].size();i++)
            {
                int w=adj[p[v]][i];
                if(used[w])
                    continue;
                if(s[w].find(p[req[1]])!=s[w].end())
                {
                    p[u]=w;
                    used[w]=true;
                    break;
                }
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        int m = (1<<n);
        int p[m];
        set<int> s[m];
        vector<int> adj[m];
        for(int i=0;i<n*m/2;i++)
        {
            int u,v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
            s[u].insert(v);
            s[v].insert(u);
        }
        permuteHypercube(n,m,adj,s,p);
        for(int i=0;i<m;i++)
            cout << p[i] << " ";
        cout << '\n';
        if(n!=1 && n!=2 && n!=4 && n!=8 && n!=16)
        {
            cout << -1 << '\n';
            continue;
        }
        int temp[m];
        for(int i=0;i<m;i++)
        {
            int clr=0;
            for(int j=0;j<n;j++)
            {
                if(i&(1<<j))
                    clr=clr^j;
            }
            temp[i]=clr;
        }
        int c[m];
        for(int i=0;i<m;i++)
            c[p[i]]=temp[i];
        for(int i=0;i<m;i++)
            cout << c[i] << " ";
        cout << '\n';
    }
}

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <utility>
#include <queue>
#include <map>
#include <assert.h>
#include <stack>
#include <string>
#include <ctime>
#include <chrono>
#include <random>
using namespace std;
 
const int MAX=65536;
int power[21]={0};
vector<int> adj[MAX+1];
bool xtra[MAX+1];
bool in[MAX+1];
vector<int> f(vector<int> s)
//given a set of vertices [graph], returns the permutation that was applied to the simple hypercube to get this graph
{
	/*
	cout << "set\n";
	for (auto it : s)
	{
		cout << it << " ";
	}
	cout << '\n';
	*/
	if ((int)s.size()==2)
	{
		vector<int> p(2);
		p[0]=s[0];
		p[1]=s[1];
		return p;
	}
	for (auto i: s) in[i]=true;
	int v1=s[0];
	int v2=-1;
 
	for (auto i: adj[v1])
	{
		if (in[i])
		{
			v2=i;
			break;
		}
	}
	assert(v2!=-1);
	//cout << "v1= " << v1 << " v2 = " << v2 << '\n';
	vector<int> component;
	//multisource BFS from (v1, v2)
	{
		queue<int> q;
		q.push(v1);
		q.push(v2);
		map<int, bool> vis;
		vis[v1]=true;
		vis[v2]=true;
		map<int, bool> cmp;
		cmp[v1]=true;
		component.push_back(v1);
		while (!q.empty())
		{
			auto u=q.front();
			q.pop();
			for (auto i: adj[u])
			{
				if ((!vis[i])&&in[i])
				{
					vis[i]=true;
					q.push(i);
					cmp[i]=cmp[u];
					if (cmp[i]) component.push_back(i);
				}
			}
		}
	}
	for (auto i: s) in[i]=false;
	for (auto i: component) in[i]=true;
	vector<int> p1=f(component);
	for (auto i: s) in[i]=true;
	for (auto i: component) xtra[i]=true;
	
	vector<int> p((int)s.size());
	
	int z=component.size();
	assert(2*z==(int)s.size());
	
	for (int i=0; i<z; i++) p[i]=p1[i];
	
	for (int i=0; i<z; i++)
	{
		//i+z
		int g=-1;
		for (auto i: adj[p[i]])
		{
			if (in[i]&&(!xtra[i]))
			{
				g=i;
				break;
			}
		}
		assert(g!=-1);
		p[z+i]=g;
	}
	for (auto i: component) xtra[i]=false;
	for (auto i: s) in[i]=false;
	return p;
}
 
vector<int> colorit(int n)
{
	vector<int> ret(n);
	for (int i=0; i<n; i++)
	{
		int res=0;
		for (int z=0; z<20; z++) res^=z*((power[z]&i)!=0);
		ret[i]=res;
	}
	return ret;
}
 
void solve()
{
	int n;
	cin>>n;
	for (int i = 0; i < power[n]; i++) adj[i].clear();
	for (int j = 0; j < n * power[n - 1]; j++)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	vector<int> p;
	
	{
		vector<int> s;
		for (int i=0; i<power[n]; i++) s.push_back(i);
		p=f(s);
	}
	
	for (int i=0; i<power[n]; i++) cout<<p[i]<<' ';
	cout<<'\n';
	
	if (power[n]%n)
	{
		cout<<-1<<'\n';
		return;
	}
	vector<int> col=colorit(power[n]);
	vector<int> out(power[n]);
	for (int i=0; i<power[n]; i++)
	{
		out[p[i]]=col[i];
	}
	for (int i=0; i<power[n]; i++) cout<<out[i]<<' ';
	cout<<'\n';
	return;
}
 
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	int t;
	cin >> t;
	//t=1;
	
	power[0]=1;
	for (int j=1; j<=20; j++) power[j]=power[j-1]*2;
	
	while (t--)
	{
		solve();
	}
	return 0;
}

All characters and incidents portrayed in this round are fictitious. In the real world, drive safe and make sure to always wear your seatbelt.