In this game to win, Alice has to choose one 2 and all 3 in his first chances only otherwises he loses. So, if he have number 2 less than two then he lose otherwise win.

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector <int> a(n);
        int x=0;
        for(int i=0;i<n;i++){
            cin>>a[i];
            if(a[i]==2)x++;
        }
        if(x>=2){
            cout<<"Alice\n";
        }
        else{
            cout<<"Bob\n";
        }
    }
}

To visit every cell exactly once in a $$$3 \times N$$$ grid starting at a corner and ending at the opposite corner, the path must move in a specific "snake" or "zigzag" fashion.In a $$$3 \times N$$$ grid, for every column $$$i$$$ (from $$$2$$$ to $$$N-1$$$), the path has two choices on how to "traverse" that column's height to reach the next section while ensuring no cells are left behind. Since there are $$$N-2$$$ such intermediate columns where these choices matter, we get $$$2 \times 2 \times \dots \times 2$$$ ($$$N-2$$$ times). And for $$$N$$$=$$$1$$$ answer will be 1.

#include <bits/stdc++.h>
using namespace std;
 
static const long long MOD = 1000000007LL;
 
long long modpow(long long a, long long e) {
    long long r = 1 % MOD;
    a %= MOD;
    while (e > 0) {
        if (e & 1) r = (r * a) % MOD;
        a = (a * a) % MOD;
        e >>= 1;
    }
    return r;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
    while (T--) {
        long long N;
        cin >> N;
        if (N == 1) cout << 1 << "\n";
        else cout << modpow(2, N - 2) << "\n";
    }
    return 0;
}

Kael's Private Pool ($$$K$$$): Numbers divisible by $$$x$$$ but not $$$y$$$. Liora's Private Pool ($$$L$$$): Numbers divisible by $$$y$$$ but not $$$x$$$. The Shared Pool ($$$S$$$): Numbers divisible by both $$$x$$$ and $$$y$$$. Game Strategy: Optimal players will always prioritize the Shared Pool ($$$S$$$). Why? Because every time a player picks from $$$S$$$, they take away a potential move from their opponent while keeping their own "Private Pool" intact for later. The game's outcome depends on who is forced to start picking from their private pool first. Case AnalysisIf $$$|S|$$$ is Even, Kael and Liora will pick an equal number of shared elements. The shared pool neutralizes itself. The winner is simply whoever has the larger private pool. Kael wins if $$$|K| \gt |L|$$$. Liora wins if $$$|L| \geq |K|$$$. If $$$|S|$$$ is Odd, Kael (the first player) gets to take the "extra" shared element. This gives him a +1 advantage in the turn order. Effectively, Kael can win even if his private pool is equal to Liora's. Kael wins if $$$|K| \geq |L|$$$. Liora wins if $$$|L| \gt |K|$$$.

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#endif
#define int long long
#define pii pair<int, int>
const int INF = 1e18;
const int MOD = 1e9 + 7;

void solve() {
    int n;
    long long x, y;
    cin >> n >> x >> y;

    int kael_moves = 0;
    int liora_moves = 0;
    int common_moves = 0;

    for (int i = 0; i < n; i++) {
        long long val;
        cin >> val;

        bool div_x = (val % x == 0);
        bool div_y = (val % y == 0);

        if (div_x && div_y) {
            common_moves++;
        } else if (div_x) {
            kael_moves++;
        } else if (div_y) {
            liora_moves++;
        }
    }

    if (common_moves % 2 == 0) {
        if (kael_moves > liora_moves) {
            cout << "Kael" << "\n";
        } else {
            cout << "Liora" << "\n";
        }
    } 
    else {
        if (liora_moves > kael_moves) {
            cout << "Liora" << "\n";
        } else {
            cout << "Kael" << "\n";
        }
    }
}

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

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

The goal is to construct an array such that $$$PrefixXor(k) = T$$$ and $$$SuffixAnd(k) = T$$$, with $$$T = 2^{29}$$$. We use high-bit "flags" to ensure all elements are distinct and within the 31-bit integer range.

1. Suffix Construction (AND sum = $$$T$$$) To force the suffix AND to exactly $$$T$$$, every element must have the $$$29^{th}$$$ bit set, and the intersection of all other bits must be $$$0$$$. For $$$n-k=0$$$: $$$a_k = T$$$. For $$$n-k \gt 0$$$: * Set $$$a_k = T \mid 2^{30}$$$ (Anchor bit). Set $$$a_i = T \mid 2^{27} \mid i$$$ for the remaining elements. The bits $$$2^{30}$$$ and $$$2^{27}$$$ are unique to the suffix, ensuring distinctness. At the same time, the inclusion of $$$i$$$ (index) eventually clears all bits except $$$2^{29}$$$ during the AND operation.

2. Prefix Construction (XOR sum = $$$T$$$) We use the property $$$S \oplus (S \oplus T) = T$$$. Fill $$$a_0 \dots a_{k-2}$$$ with unique values: $$$2^{25} \mid (i+1)$$$. Let their XOR sum be $$$S$$$. Set the pivot $$$a_{k-1} = S \oplus T$$$. The $$$2^{25}$$$ flag ensures these values never collide with the suffix.

#include <bits/stdc++.h>

using namespace std;

void solve(){
    int n,k;
    cin>>n>>k;

    const long long T=(1LL<<29);
    const long long P_FLAG=(1LL<<25);
    const long long S_FLAG=(1LL<<27);
    const long long ANCHOR=(1LL<<30);

    vector<long long> a(n);

    if(n-k==1){
        a[k]=T;
    } 
    else{
        a[k]=T|ANCHOR;
        for(int i=k+1;i<n;i++){
            a[i]=T|S_FLAG|(long long)i;
        }
    }

    long long current_xor=0;
    for(int i=0;i<k-1;i++){
        a[i]=P_FLAG|(long long)(i+1);
        current_xor^=a[i];
    }
    
    a[k-1]=T^current_xor;

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

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

    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Problem Insight The values in the array are small, specifically in the range [1, 30]. This allows us to use bitmask dynamic programming based on prime factorizations. A subsequence is square-free if its product contains no repeated prime factor. Key Observations 1. Each prime factor can appear at most once in the subsequence. 2. Each number greater than 1 can be chosen at most once. 3. If a number x appears cnt[x] times and is selected, it contributes cnt[x] choices. Prime Mask Representation All primes up to 30 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Each number from 2 to 30 is mapped to a 10-bit mask representing its prime factors. Numbers divisible by a square are discarded. Dynamic Programming We define dp(mask, num), where mask represents used prime factors and num is the current number being processed. For each state, we either skip num or take it if its prime mask does not conflict. Handling Number 1 The number 1 has no prime factors and can be chosen any number of times. It contributes a multiplier of 2^{cnt[1]}. Final Answer The final result is dp(0, 30) multiplied by 2^{cnt[1]}, minus 1 to exclude the empty subsequence, taken modulo 10^9 + 7. Complexity Analysis Time Complexity: O(2^10 × 30) Space Complexity: O(2^10 × 30)

#include <bits/stdc++.h>
using namespace std;
 
#define vi vector<int>
#define ll long long
 
const ll mod = 1000000007;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
 
    int prime[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
 
    while (t--) {
        int n;
        cin >> n;
 
        vi nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        unordered_map<int, int> m;
        int ones = 0;
 
        vi dp(1 << 10, 0), tmp;
        dp[0] = 1;
 
        for (int x : nums) {
            if (x % 4 == 0 || x % 9 == 0 || x % 25 == 0) continue;
            if (x == 1) ones++;
            else m[x]++;
        }
 
        for (auto &x : m) {
            int curr_mask = 0;
            for (int i = 0; i < 10; i++) {
                if (x.first % prime[i] == 0)
                    curr_mask |= (1 << i);
            }
 
            tmp.assign(1 << 10, 0);
            for (int mask = 0; mask < (1 << 10); mask++) {
                if ((mask & curr_mask) == 0) {
                    tmp[mask | curr_mask] =
                        (tmp[mask | curr_mask] + (ll)dp[mask] * x.second) % mod;
                }
            }
 
            for (int i = 0; i < (1 << 10); i++) {
                dp[i] = (dp[i] + tmp[i]) % mod;
            }
        }
 
        ll res = 0;
        for (int i = 1; i < (1 << 10); i++) {
            res = (res + dp[i]) % mod;
        }
 
        ll pow2 = 1;
        while (ones--) pow2 = (pow2 * 2) % mod;
 
        res = (res * pow2) % mod;
 
        cout << res << '\n';
    }
 
    return 0;
}

To unlock the vault, the problem translates into a graph reachability game where nodes are crystals and edges exist between numbers sharing a prime factor. Using DSU and Prime Factorization, we group the $$$N$$$ crystals into disjoint components based on their prime divisors. Kael and Liora can only "claim" a component if their base frequency ($$$X$$$ or $$$Y$$$) shares a prime factor with at least one element in that component. Logically, since players prioritize a Tie (Perfect Resonance) over a loss, the result is a Tie if and only if the union of all components reachable by Kael and Liora covers all $$$N$$$ crystals ($$$|Reach_K \cup Reach_L| = N$$$). If a Tie is impossible, the game reduces to a comparison of their maximum potential power: Kael wins if the total size of all components reachable by him is strictly greater than those reachable by Liora ($$$|Reach_K| \gt |Reach_L|$$$); otherwise, Liora wins.

#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include <C:/Users/ajiit/Desktop/Future/Coding/Problem Solving/debug.cpp>
#endif
#define int long long
#define pii pair<int, int>
const int INF = 1e18;
const int MOD = 1e9 + 7;
 
const int SQ = 32000;
const int MX = 200005;
 
vector<int> mp(SQ + 1, 0);
vector<int> pr;
int arr[MX];
vector<int> fac[MX];
map<int, vector<int>> pos;
int n, x, y;
 
void sieve() {
    if (!pr.empty()) {
        return;
    }
    for (int i = 2; i <= SQ; ++i) {
        if (mp[i] == 0) {
            mp[i] = i;
            pr.push_back(i);
        }
        for (int p : pr) {
            if (p > mp[i] || i * p > SQ) {
                break;
            }
            mp[i * p] = p;
        }
    }
}
 
vector<int> getf(int v) {
    vector<int> f;
    for (int p : pr) {
        if (p * p > v) {
            break;
        }
        if (v % p == 0) {
            f.push_back(p);
            while (v % p == 0) {
                v /= p;
            }
        }
    }
    if (v > 1) {
        f.push_back(v);
    }
    return f;
}
 
vector<bool> bfs(int v) {
    vector<bool> rch(n, false);
    set<int> vis;
    queue<int> q;
    vector<int> sf = getf(v);
    for (int p : sf) {
        if (vis.find(p) == vis.end()) {
            vis.insert(p);
            q.push(p);
        }
    }
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        if (pos.find(p) == pos.end()) {
            continue;
        }
        for (int i : pos[p]) {
            if (!rch[i]) {
                rch[i] = true;
                for (int np : fac[i]) {
                    if (vis.find(np) == vis.end()) {
                        vis.insert(np);
                        q.push(np);
                    }
                }
            }
        }
    }
    return rch;
}
 
void solve() {
    cin >> n >> x >> y;
    pos.clear();
    for (int i = 0; i < n; ++i) {
        fac[i].clear();
    }
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        fac[i] = getf(arr[i]);
        for (int p : fac[i]) {
            pos[p].push_back(i);
        }
    }
    
    vector<bool> r1 = bfs(x);
    vector<bool> r2 = bfs(y);
    
    int k = 0, l = 0, s = 0;
    for (int i = 0; i < n; ++i) {
        if (r1[i] && r2[i]) {
            s++;
        } else if (r1[i]) {
            k++;
        } else if (r2[i]) {
            l++;
        }
    }
 
    if (k + l + s == n) {
        cout << "Tie\n";
        return;
    }
 
    if (k > l) {
        cout << "Kael\n";
    } 
    else {
        cout << "Liora\n";
    }
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    sieve();
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
} 

DP. 2D-DP, with dp[i][j] stating min distance travelled from the initial point to (xi, jth integer in range). Transition is s1s2, if the gap size of the i-1th wall is s1 and the gap of the ith wall is s2. Time Complexity: $$$\sum_{i=1}^{i=n-1} wiw(i+1)$$$, where wi = window size of ith wall.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long               ll;
typedef vector<ll>             vll;
typedef vector<vll>           vvll;
typedef long double             ld;
typedef vector<long double>    vld;
 
ld sq(ld x){
    return (x*x);
}
 
void solve(){
    ll n,tar; cin >>n >>tar;
    vvll ar(n+1, vll (3));
    ar[0] = {0,0,0};
    for(int i=0; i<n; i++){
        for(int j=0; j<3; j++) cin >>ar[i+1][j];
    }
    
    vector<vld> dp(103, vld(n+1, 1e18));
    dp[0][0] = 0;
 
    for(int i=1; i<n+1; i++){
        ld of1 = ar[i-1][1];
        for(ld j=ar[i-1][1]; j<=ar[i-1][2]; j++){
            ld of2 = ar[i][1];
            for(ld k=ar[i][1]; k<=ar[i][2]; k++){
                ld dis = sqrt( sq(k-j) + sq(ar[i][0]-ar[i-1][0]) );
                dp[k-of2][i] = min(dp[k-of2][i], dp[j-of1][i-1]+dis);
            }
        }
    }
 
    ld ans = 1e18;
    for(int i=0; i<103; i++){
        ans = min(ans, dp[i][n]+tar-ar[n][0]);
    }
cout << fixed << setprecision(10) << ans << "\n";\
    
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t;
    cin>>t;
    for(int i=0; i<t; i++){
        solve();
    }
    return 0;
}

1. Mathematical Formulation Let $$$P = [p_{1}, p_{2}, \dots, p_{N}]$$$ be a permutation of the integers $$$1, \dots, N$$$. The problem asks whether we can partition the index set $$${1, \dots, N}$$$ into two disjoint sets $$$J_{1}$$$ and $$$J_{2}$$$ such that: Partition:$$$J_{1} \cup J_{2} = {1, \dots, N}$$$ 2$J_{1} \cap J_{2} = \emptyset$ Strict Chronology: For any $$$k \in {1, 2}$$$ and any $$$i, j \in J_{k}$$$ with $$$i \lt j$$$, we require: $$$p_{i} \lt p_{j}$$$ That is, both induced subsequences must be strictly increasing. Perfect Symmetry:$$$|J_{1}| = |J_{2}| [cite_start]= \frac{N}{2}$$$. Immediate Constraint: If $$$N$$$ is odd, the condition $$$|J_{1}| = |J_{2}|$$$ is impossible. In this case, we immediately output UnBalanced.

2. Structural Decomposition: The permutation can be decomposed into independent subproblems based on its internal structure. Identification of Cut PointsA Cut Point is an index $$$k$$$ such that: $$$max(p_{1}, \dots, p_{k}) \lt min(p_{k+1}, \dots, p_{N})$$$. If such a point exists, the permutation can be split at $$$k$$$. Any increasing subsequence in the prefix can be concatenated with any increasing subsequence in the suffix without violating the ordering constraint. Using all cut points, we decompose $$$P$$$ into independent segments: $$$S_{1}, S_{2}, \dots, S_{m}$$$. Local Greedy Decomposition: For each segment, we determine whether it can be partitioned into two strictly increasing subsequences. Although Dilworth's Theorem applies in general, for $$$k=2$$$ a simpler greedy strategy suffices. Greedy Strategy: Assign all prefix maximums of the segment to subsequence $$$A$$$. Assign all remaining elements to the subsequence $$$B$$$. Subsequence $$$A$$$ is strictly increasing by construction. We explicitly verify that the subsequence $$$B$$$ is also strictly increasing. If not, the segment cannot be decomposed and the answer is UnBalanced. Let the lengths of the two subsequences for segment $$$i$$$ be $$$l_{i,1}, l_{i,2}$$$. We define: $$$b_{i} = min(l_{i,1}, l_{i,2})$$$ (base contribution) $$$w_{i} = |l_{i,1} - l_{i,2}|$$$ (imbalance weight).

3. The Balancing Problem (Subset Sum)Each segment contributes $$$b_{i}$$$ elements to both journals. Let: $$$B_{total} = \sum_{i=1}^{m} b_{i}$$$. The remaining capacity required to reach $$$\frac{N}{2}$$$ is: $$$K = \frac{N}{2} - B_{total}$$$. Each segment contributes an additional weight $$$w_{i}$$$ that must be assigned to exactly one journal. We must determine whether there exists a subset $$$I \subseteq {1, \dots, m}$$$ such that: $$$\sum_{i \in I} w_{i} = K$$$. This is the Subset Sum Problem.

#include<bits/stdc++.h>
using namespace std;
const int N=501000;
// Lucifer_K->
using B=bitset<N>;
 
void solve() {
    int n; cin>>n; 
    vector<int> a(n);
    for (int i=0; i<n; i++) cin>>a[i];
    if(n%2!=0){
       cout<<"UnBalanced\n"; 
       return;
    }
    vector<int> pf=a,sf=a;
    for (int i=1; i<n; i++) pf[i]=max(pf[i],pf[i-1]);
    for (int i=n-2; i>=0; i--) sf[i]=min(sf[i],sf[i+1]);
    vector<int> cps={0};
    for (int i=0; i<n-1; i++) if (pf[i]<sf[i+1]) cps.push_back(i+1);
 
    cps.push_back(n);
    vector<int> wf; int base=0;
    for (int k=0; k<cps.size()-1; k++) {
        int l=cps[k], r=cps[k+1];
        vector<int> s1,s2;
        for (int i=l; i<r; i++)
            if (a[i]==pf[i]) s1.push_back(a[i]);
           else s2.push_back(a[i]);
        for (int i=0; i<(int)s1.size()-1; i++) {
            if (s1[i]>=s1[i+1]) {
                cout<<"UnBalanced\n"; return;
            }
        }
        for (int i=0; i<(int)s2.size()-1; i++) {
            if (s2[i]>=s2[i+1]) {
                cout<<"UnBalanced\n"; return;
            }
        }
        int len1=s1.size(), len2=s2.size();
        base+=min(len1,len2);
        wf.push_back(abs(len1-len2));
    }
    vector<int> cnt(n+1,0);
    for (int i=0; i<wf.size(); i++) cnt[wf[i]]++;
    for (int i=1; i<=n; i++) {
        if (cnt[1]>2) {
            int p=(cnt[i]-1)/2;
            if (2*i<=n) {
                cnt[2*i]+=p;
                cnt[i]-=2*p;
            }
        }
    }
    B dp; dp[0]=1;
    for (int i=1; i<=n; i++) {
        for (int k=0; k<cnt[i]; k++) {
            dp|=dp<<i;
        }
    }
    int ans=(n/2)-base;
    if (ans>=0 && dp[ans]) cout<<"Balanced\n";
    else cout<<"UnBalanced\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin>>t; while(t--) solve();
}