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.