Try to write out the pattern for small values of n and k and observe when you get stuck in invalid cycles. What are the gaps between the numbers in the invalid cycles?

There are 2 valid approaches to the problem under the given constraints.

Approach 1: You may simulate the process of jumping and mark the visited halls using an array or set. When you reach a hall already visited check if the number of halls visited is n.

Approach 2: This problem is a classic application of modular arithmetic. It is a known mathematical property that a sequence of jumps of size k will generate all elements 1 to n if and only if n and k are coprime. In particular, the gaps between the elements generated are equal to the gcd of n and k. Thus, you will visit all n halls if and only if $$$\gcd(n, k) = 1$$$. This reduces the problem to a single-line check per test case.

Time Complexity: $$$\mathcal{O}(\log(\min(n, k)))$$$ per testcase for the GCD approach, or $$$\mathcal{O}(n)$$$ for the simulation approach.

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

long long gcd(long long a, long long b)
{
    while (b)
    {
        a %= b;
        swap(a, b);
    }
    return a;
}

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

    int t;
    cin >> t;
    while (t--)
    {
        long long n, k;
        cin >> n >> k;

        if (gcd(n, k) == 1)
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
    }
    return 0;
}

Try to see for different arrays, which values can be created from the previous values. Can you notice a pattern?

For some arrays, there are some values which can never be created. Can you observe which values they are?

There are three cases for this problem, when the mex of the initial array is $$$0, 1$$$ and $$$\ge 2$$$. When mex of the array is $$$0$$$, no operation can create a value $$$0$$$, since, the minimum value in the array will be $$$1$$$, and the minimum value created will be $$$1+1=2$$$.

When the mex of the array is $$$1$$$, no operation can create a value $$$1$$$, as the creating $$$1$$$ will require $$$1+0$$$ or $$$0+1$$$. Since $$$1$$$ is not present in the array initially, it cannot be created.

For every other case, you can always create each number. This is because, initially there is a $$$0$$$ and $$$1$$$. With these 2 you can create $$$1+0=1$$$. With $$$1,1$$$, you can create $$$1+1=2$$$. Then you can create $$$1+2=3, 1+3=4, \cdots$$$. Thus every value can be created and the answer for this is $$$1000000000$$$.

Time Complexity: Since we only iterate through the array and find the mex of the initial array, the time complexity is O(n)

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

void solve()
{
    int n;
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    int c0=0,c1=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==0)c0=1;
        if(a[i]==1)c1=1;
    }
    if(!c0)
    {
        cout<<0<<endl;return;
    }
    else if(!c1)
    {
        cout<<1<<endl;return;
    }
    else
    {
        cout<<1000000000<<endl;return;
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)solve();
}

Hint 1: The total energy is constrained by the minimum lifetime among all chosen bulbs. If you decide that the minimum lifetime of your circuit is going to be exactly $$$L$$$, which bulbs should you choose to maximize the energy?

Hint 2: If the minimum lifetime is fixed at $$$L$$$, you should include all bulbs that have a lifetime $$$l_i \ge L$$$. Since power outputs are strictly positive, adding more valid bulbs will always increase the total power sum without dropping the minimum lifetime below $$$L$$$.

This problem can be solved optimally using a Greedy approach combined with sorting.

Let's pair each bulb's power output $$$p_i$$$ and lifetime $$$l_i$$$ together. To efficiently check all possible minimum lifetimes, we should sort the bulbs in descending order based on their lifetimes.

Once sorted, we can iterate through the array from the longest-lasting bulb to the shortest-lasting bulb. As we iterate:1. 1. We maintain a running sum of the power outputs we have seen so far. 2. At the $$$i$$$-th step, the current bulb's lifetime $$$l_i$$$ represents the minimum lifetime of all bulbs chosen so far. 3. The energy generated by this prefix of bulbs is exactly:

1. We take the maximum of these energy values across all steps.

Time Complexity: Sorting the array takes $$$\mathcal{O}(N \log N)$$$. The linear scan takes $$$\mathcal{O}(N)$$$. Therefore, the overall time complexity is $$$\mathcal{O}(N \log N)$$$, which comfortably passes within the 2.0-second time limit.

Common Trap: The maximum possible energy can be roughly $$$(10^5 \cdot 10^6) \times 10^6 = 10^{17}$$$. This heavily exceeds the limit of a 32-bit integer. You must use 64-bit integers (long long in C++) for your running sums and the final answer to avoid integer overflow.

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

void solve() {
    int n;
    cin >> n;
    vector<pair<long long, long long>> v(n);
    
    for (int i = 0; i < n; i++) cin >> v[i].second; // power
    for (int i = 0; i < n; i++) cin >> v[i].first;  // lifetime

    // Sort descending by lifetime
    sort(v.rbegin(), v.rend());

    long long max_energy = 0;
    long long sum_power = 0;

    for (int i = 0; i < n; i++) {
        sum_power += v[i].second;
        long long current_energy = sum_power * v[i].first;
        max_energy = max(max_energy, current_energy);
    }

    cout << max_energy << "\n";
}

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

Deleting the minimum number of digits is the same as finding the longest valid subsequence that forms a multiple of 11.

Think about how numbers are built left to right. If you have a number $$$X$$$ and you append a new digit $$$d$$$ to the end of it, the new number is $$$X \times 10 + d$$$.

Seeing divisibility by 11 you might be enticed to think of divisibility rules and while that approach will also lead to a similar solution using dynamic programming , we can do something more straightforward.

We want to find the longest subsequence that is divisible by 11. Let's process the string from left to right. If we have some prefix that leaves a remainder of $$$r$$$ when divided by 11, and we append a new digit $$$d$$$, the new remainder becomes $$$(10 \times r + d) \pmod{11}$$$.

Let's define our DP array: dp[r] will store the maximum length of a subsequence we can form so far that leaves a remainder of r modulo 11. We can initialize this array with -1 to represent that a remainder is currently unreachable.

As we iterate through the digits of the string, for each digit $$$d$$$, we can either:

1. Skip it: The DP states remain exactly as they were.

2. Start a new number: We just pick this digit by itself. This gives a remainder of $$$d \pmod{11}$$$ and a length of 1.

3. Append it to an existing subsequence: For every valid remainder $$$r$$$ we've seen so far (where dp[r] != -1), appending $$$d$$$ creates a new remainder new_rem = (r * 10 + d) % 11. The new length would be dp[r] + 1.

We update our DP table with the maximum lengths possible. Because we are updating states based on previous states from the same step, we should do this on a temporary copy of the DP array (next_dp) so we don't accidentally use a digit multiple times.

After iterating through the whole string, our answer relies on dp[0]. If dp[0] is still -1, it's impossible to form a multiple of 11, so we print -1. Otherwise, the minimum deletions required is the original length $$$n$$$ minus the length of the longest valid subsequence (dp[0]).

Time Complexity: $$$\mathcal{O}(n \cdot 11)$$$ per testcase, well within the time limit.

#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;
        string s;
        cin >> s;
        vector<int> dp(11, -1);
        for (int i = 0; i < n; i++)
        {
            int d = s[i] - '0';
            vector<int> next_dp = dp;
            next_dp[d % 11] = max(next_dp[d % 11], 1);
            for (int r = 0; r < 11; r++)
            {
                if (dp[r] != -1)
                {
                    int new_rem = (r * 10 + d) % 11;
                    next_dp[new_rem] = max(next_dp[new_rem], dp[r] + 1);
                }
            }
            dp = next_dp;
        }
        if (dp[0] == -1)
        {
            cout << -1 << '\n';
        }
        else
        {
            cout << n - dp[0] << '\n';
        }
    }
    return 0;
}

Group the array indices by their target Longest Increasing Subsequence length, $$$a_i$$$. We construct the permutation using two rules: assign strictly smaller numbers to groups with larger target lengths (larger $$$a_i$$$), and ensure values strictly decrease from left to right within any single group (equal $$$a_i$$$). Now I'll prove why this will give the correct answer if a permutation exists. First, let's show that no longer increasing subsequence can exist. Suppose we have a valid increasing subsequence starting at $$$i$$$. The next element (let it be at index $$$j$$$ in this sequence cannot have $$$a_j = a_i$$$, because our first rule forces values to strictly decrease from left to right. Similarly, the next element cannot have $$$a_j \gt a_i$$$, because the second rule assigns strictly smaller permutation values to those groups. Therefore, to maintain an increasing sequence, every subsequent element must be chosen from a group with a strictly smaller target length. Since these target lengths must strictly decrease with each step, the maximum possible length of any increasing subsequence starting at $$$I$$$ is capped at $$$a_i$$$. Next, let's prove that an increasing subsequence of length exactly $$$a_i$$$ is always possible. To form this sequence, we simply need to select the next element from its right that has $$$a_j = a_i - 1$$$. By our first rule, because group $$$a_i$$$ was assigned strictly smaller numbers than group $$$a_i - 1$$$, $$$p_i \lt p_j$$$ is satisfied. The only way this could fail is if no such index $$$j$$$ exists to the right of $$$i$$$. This becomes our check if a permutation exists or not. This can be done $$$O(n * log(n))$$$ time. First group indices with equal $$$a_i$$$. Then for checking if each index $$$i$$$ has an index $$$j$$$ to the right with $$$a_j = a_i - 1$$$. If it's valid then construct the permutation as per the rules or else output $$$-1$$$.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    int mx = 0;
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        mx = max(mx, a[i]);
    }

    // Group indices by their required LIS length. 
    vector<vector<int>> pos(mx + 1);
    for (int i = 0; i < n; i++) {
        pos[a[i]].push_back(i);
    }

    // Every element with 'a_i' must have at least one element to its right with 'a_i -1'.
    for (int i = 2; i <= mx; i++) {
        if (pos[i].empty()) continue;
        if (pos[i - 1].empty()) {
            cout << -1 << "\n";
            return;
        }
        
        // We only need to check the strictest constraint: the rightmost element of group 'i'
        int curr = pos[i].back();
        auto it = upper_bound(pos[i - 1].begin(), pos[i - 1].end(), curr);
        
        // If no element in group i-1 exists to the right of 'curr', it's impossible.
        if (it == pos[i - 1].end()) {
            cout << -1 << "\n";
            return;
        }
    }

    // Construct the valid permutation
    vector<int> ans(n);
    int current_val = 1;
    
    // Assign the smallest numbers to the largest a_i
    for (int i = mx; i >= 1; i--) {
        // Iterate from right to left to assign smaller values to the one on the right
        for (int j = (int)pos[i].size() - 1; j >= 0; j--) {
            ans[pos[i][j]] = current_val++;
        }
    }

    for(int i = 0; i < n; i++) {
        cout<<ans[i]<<" ";
    }
    cout << "\n";
}

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

Try to think about what the condition actually means.
If $$$|i - j|$$$ is odd, then $$$i$$$ and $$$j$$$ are in opposite parity positions.
So effectively, all elements at odd indices must be coprime with all elements at even indices.

If two numbers have $$$\gcd(a_i, a_j) \gt 1$$$, they cannot be placed in opposite parity positions.
So such numbers must lie in the same group. Can you model this as a graph?

Build connected components where edges exist if $$$\gcd(a_i, a_j) \gt 1$$$.
All nodes in one component must go to the same parity side.
Now the problem reduces to splitting components into two groups of equal size.

We are given the condition:

If $$$|i - j|$$$ is odd, then $$$\gcd(b_i, b_j) = 1$$$.

This means elements at odd positions must be coprime with elements at even positions.

Key observation:

If $$$\gcd(x, y) \gt 1$$$, then $$$x$$$ and $$$y$$$ cannot be placed in opposite parity positions.

So such elements must lie in the same group.

Graph model:

• Create a graph with nodes as indices
• Add an edge between $$$i$$$ and $$$j$$$ if $$$\gcd(a_i, a_j) \gt 1$$$

Each connected component represents elements that must stay together.

Let component sizes be $$$c_1, c_2, \dots, c_k$$$.

We need to split these components into two groups such that one group has exactly $$$\frac{n}{2}$$$ elements.

This becomes a subset sum problem, which is the same as the classic knapsack problem

DP:

Let $$$dp[x] = 1$$$ if we can achieve total size $$$x$$$ using some components.

The answer is:

• YES if $$$dp[\frac{n}{2}] = 1$$$
• NO otherwise

Complexity:

• Graph construction: $$$O(n^2 \log A)$$$
• DFS: $$$O(n)$$$
• DP: $$$O(n^2)$$$

This works since $$$\sum n \le 1000$$$.

#include<bits/stdc++.h>
using namespace std;
void dfs(int c, vector<vector<int>> &g, vector<int> &si,vector<int> &vis)
{
    si[c]=1;
    vis[c]=1;
    for(auto x:g[c])
    {
        if(vis[x])continue;
        dfs(x,g,si,vis);
        si[c]+=si[x];
    }
}
void solve()
{
    int n;
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<vector<int>> g(n+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(gcd(a[i],a[j])>1)
            {
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
    vector<int> si(n+1);
    vector<int> vis(n+1);
    vector<int> l;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            dfs(i,g,si,vis);
            l.push_back(si[i]);
        }
        
    }
    int w=n/2;
    vector<int> dp(w+1);
    dp[0]=1;
    for(int i=0;i<l.size();i++)
    {
        for(int j=w;j>=l[i];j--)
        {
            dp[j]|=dp[j-l[i]];
        }
    }
    if(dp[w])cout<<"YES\n";
    else cout<<"NO\n";
}
int main()
{
    int t;
    cin>>t;
    while(t--)solve();
}