BREAK - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Vlad Zavodnik
Tester: Suchan Park
Editorialist: William Lin

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Game Theory

PROBLEM:

Chef has N cards with ranks a_1, a_2, \dots, a_N and his friend has N cards with ranks b_1, b_2, \dots, b_N. The game is played in rounds, with one person being the attacker and the other person being the defender.
Each round starts with the attacker placing a card on the table. The defender will either give up the round or place a card with a higher rank on the table. Then, the following happens until somone gives up: The attacker places a card with its rank equal to some card on the table, and the defender gives up or beats the card that the attacker just placed. If the attacker gives up, all cards on the table are discarded and the roles are swapped for the next round. If the defender gives up, he takes all cards on the table and the round ends.
Initially, Chef is the attacker. The game ends when someone runs out of cards at the beginning of his turn. Determine if it’s possible for the game to end with both players not having any cards given that:

Subtask 1: The game needs to end in one round.

Subtask 2: The game can end in any number of rounds.

QUICK EXPLANATION 1:

In each turn, the player should play his smallest card. If some move is invalid, then the answer is impossible.

QUICK EXPLANATION 2:

  • We can check if we can end in one round with the algorithm for subtask 1.
  • If we can’t end in one round, check for the case N=2.
  • We are left with N>2.
  • If all of Chef’s cards are the same and have ranks greater than equal to all of his friend’s cards, the answer is impossible.
  • If all of Chef’s friend’s cards are the same and have ranks smaller than or equal to all of Chef’s cards, the answer is impossible.
  • If there exists a card which appears more than N times, the answer is impossible.
  • Otherwise the answer is possible.

EXPLANATION 1:

In each turn, the player should play his smallest card. If some move is invalid, then the answer is impossible.

In order to show that this algorithm works, let’s prove that if there exists an solution, there must be a solution where both players play their cards in order.

Let’s suppose that a is sorted according to the order that Chef plays the cards in (so Chef will play a_1 first, then a_2, and so on). Let a be a solution with the minimum number of inversions.

If a has 0 inversions, a is sorted. Otherwise, there exists an i such that a_i>a_{i+1}.

After swapping a_i with a_{i+1}, the solution will still be valid.

Proof

If i=1, then it’s impossible that a_i>a_{i+1}. This is because, after playing a_1, Chef’s friend must play a bigger card b_1. Then, a_2 must be already on the table, but since a_2<a_1<b_1, the move is invalid.

If i>1, obviously we can play a_i on the i+1-th turn (if card a_i is on the table before Chef’s i-th turn, then it will still be on the table before Chef’s i+1-th turn). It remains to prove that we can play a_{i+1} on the i-th turn. In the original solution, we know that a_{i+1} must have been on the table before Chef’s i+1-th turn. Since a_{i+1}<a_i<b_i, a_{i+1} could not have been placed after Chef’s i-th turn, so a_{i+1} must have been on the table before Chef’s i-th turn.

So, we obtain a solution such that a has one less inversion, which contradicts the fact that the original a has the minimum number of inversions.

Now, out of all solutions such that a is sorted, consider the solution such that b has the minimum number of inversions. If b has 0 inversions, b is sorted. Otherwise, there exists an i such that b_i>b_{i+1}.

After swapping b_i with b_{i+1}, the solution will still be valid.

Proof

We know that a_{i+1}<b_{i+1}. Additionally, a_i<a_{i+1}, so a_i<b_{i+1}, and b_i>b_{i+1}, so a_{i+1}<b_i. Thus, in the new order, the cards Chef’s friend plays will still be able to beat the cards that Chef plays.

We just need to make sure that when Chef plays a_{i+1}, a card with the same value will already be on the table. Since a_{i+1}<b_i, b_i doesn’t matter and switching b_i with b_{i+1} cannot cause a_{i+1} to not have been on the table.

So, we obtain a solution such that b has one less inversion, which contradicts the fact that the original b has the minimum number of inversions.

Thus, if there is any solution, there exists a solution such that each player plays his cards in order.

EXPLANATION 2:

Assume that a and b are sorted. Let’s run the algorithm for subtask 1 first, which will take care of N=1. It will also take care of the case N=2 when the game ends in one round.

The only case left for N=2 is when the game ends in two rounds. Chef will play a card, Chef’s friend will play a card, and Chef will give up. Then Chef’s friend will play his last card, Chef will play his last card, and Chef’s friend will give up. This can happen only if a_1<b_2 and b_1<a_2 (it’s obvious that each player should play his smaller card when being the attacker and his larger card when being the defender).

From now on, N>2.

Bad condition 1. If there’s some card appears >N times, there is no solution.

Proof

Each time the attacker gives up, if 2x cards are removed, then each type of card can have at most x occurrences. If there are more than x occurrences for some card y, then there must exist a pair of turns when both the attacker and the defender play y, which is impossible since the defender needs to beat the attacker’s card.

If we remove all 2N cards over all rounds (which is required for a draw), each type of card can have at most N occurrences.

Bad condition 2. If all of Chef’s cards are the same and have ranks greater than equal to all of his friend’s cards, there is no solution.

Proof

There are no cards greater than any of Chef’s cards, so it will be impossible for Chef’s friend to ever beat Chef’s card. Chef will always be the attacker and will get rid of all his cards first.

Bad condition 3. If all of Chef’s friend’s cards are the same and have ranks smaller than or equal to all of Chef’s cards, there is no solution.

Proof

If Chef’s friend never becomes the attacker, it will be impossible for the game to end in a tie. In the first round, Chef’s friend must give up because he has small cards. Then, Chef’s friend will have more cards, so the game can’t be tied in one round, and Chef’s friend will need to give a card back to Chef by becoming the attacker.

Chef’s friend becomes the attacker when Chef gives up. Let’s say that 2x cards are removed, and note that none of them can be the smallest card. So we end up with 2(N-x) cards, but the N smallest cards will exist. By Bad Condition 1, it’s impossible to end with a tie.

If none of the bad conditions are satisfied, then there always exists a solution.

Proof

For the first N-2 rounds, Chef will be the attacker and Chef’s friend will always give up, basically transferring one card from Chef to Chef’s friend. Let x be the smallest card and let y be the largest card that Chef has. The N-2 cards that Chef transfers to his friend has to include y and the last 2 cards has to include x.

In the next round, Chef will start by putting x on the table and Chef’s friend will put any card larger than x, say z. Note that Chef’s friend must have such a card. If y>x, then z=y. If y=x, then Chef’s friend must already have a card that is greater than x, otherwise Bad Condition 1 would be satisfied.

We need to be careful if there exists a card which appears N times and make sure that we remove at least one of them. If two cards appear N times, then it must be x and z, so we are done. If one card which is not x or z appears N times, we will change z into that card (note that Chef’s friend must have that card since it appears N times).

At this point, Chef has 1 card and his friend has 2N-3 cards. For the next N-2 rounds, Chef’s friend will transfer N-2 cards to Chef so that both players will have N-1 cards after that. Then, there will be N-1 rounds, where in each round, the attacker will play one card, the defender will play one card, and the attacker will give up (thus removing one pair of cards and reversing the roles). We need to prove that it is possible for Chef’s friend to transfer N-2 cards such that the last N-1 rounds can occur in this way.

Let c be the sorted sequence of 2N-2 cards that Chef and his friend has. We will pair c_i with c_{i+N-1}, each pair will be played in one of the last N-1 rounds, so one of them should be given to Chef and the other should be given to Chef’s friend. Note that c_i<c_{i+N-1} since we guaranteed that each card appears at most N-1 times. Also, in \lceil \frac{N-1}{2} \rceil of the pairs, Chef’s friend should be the attacker, and in \lfloor \frac{N-1}{2} \rfloor of the pairs, Chef should be the attacker.

Chef can have any set of N-1 cards after Chef’s friend transfers N-2 cards, with the restriction that Chef must have his original card, so the person who is the attacker of the pair containing Chef’s original card has already been determined. However, we can set the attacker of the other N-2 pairs arbitrarily, so we are easily able to make sure that Chef is the attacker in exactly \lfloor \frac{N-1}{2} \rfloor of the pairs.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
 
ll mod = 998244353;
const ld error = 1e-8;
const ld PI = acosl(-1); //const ld PI = acosl(-1)
 
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define eq(x, y) (fabs((x)-(y))<error)
#define bt(i) (1LL<<(i))
 
#define debug(x) cerr<<#x<<" = "<<(x)<<"\n"
#define hoise cerr<<"hoise - "<<__LINE__<<"\n"
#define tham getchar()
mt19937 rng((unsigned)chrono::system_clock::now().time_since_epoch().count()); //mt199937_64 for ll
 
inline ll MOD(ll x, ll m = mod)
{
    ll y = x % m;
    return (y >= 0) ? y: y+m;
}
 
const int inf = 1e9;
const ll infl = 1e18+1;
const int nmax = bt(17);
///===========================================  template  =======================================================
ll modexpo(ll x, ll n, ll m = mod){
    ll ret = 1%m;
    while(n){
        if(n&1) ret = ret * x % m;
        x = x * x % m;
        n >>= 1;
    }
    return ret;
}
 
ll fac[nmax];
ll facinv[nmax];
void precal()
{
    fac[0] = 1;
    for(int i = 1; i<nmax; i++)
        fac[i] = (fac[i-1]*i) % mod;
    facinv[nmax-1] = modexpo(fac[nmax-1], mod-2);
    for(int i = nmax-1; i>0; i--)
        facinv[i-1] = (facinv[i]*i) % mod;
    return;
}
 
ll NCR(int n, int r){
    if(n < r) return 0;
    return fac[n] * facinv[r] % mod * facinv[n-r] % mod;
}
 
 
int arr[nmax], bsz = 1;
ll ans[nmax];
 
struct query{
    int l, r, i;
    bool operator<(query other){
        return make_pair(l/bsz, r) < make_pair(other.l/bsz, other.r);
    }
} Q[nmax];
 
int freq[nmax], frfreq[nmax], xorval;
int L[nmax], R[nmax];
 
/*
inserting frequency a (if needed)
*/
void ins(int a, int b, int c){
    if(frfreq[b] != 1) return;
    L[b] = a, R[b] = c;
    R[a] = L[c] = b;
}
 
/*
deleting frequency a (if needed)
*/
void del(int a){
    if(frfreq[a] != 0) return;
    R[L[a]] = R[a];
    L[R[a]] = L[a];
}
 
/*
Adding or removing value x from current active subarray
*/
void update(int x, int c){
    freq[x] += c;
    frfreq[freq[x]-c]--;
    frfreq[freq[x]]++;
    xorval ^= freq[x] ^ (freq[x] - c);
    if(c == 1) ins(freq[x]-1 , freq[x], R[freq[x]-1]);
    else ins(L[freq[x]+1], freq[x], freq[x]+1);
    del(freq[x]-c);
    return;
}
 
/*
Initialization before Mo's algo
*/
void init(int n){
    memset(freq, 0, sizeof(freq));
    memset(frfreq, 0, sizeof(freq));
    frfreq[0] = n+1;
    xorval = 0;
 
    L[0] = L[nmax-1] = 0;
    R[0] = R[nmax-1] = nmax-1;
    return;
}
 
 
/*
    Mo's algo to maintain frequency of each element and frequency of these frequencys.
*/
void mo(int n, int m){
    bsz = max(int(n / sqrt(m+1)), 1);
    sort(Q, Q+m);
    init(n);
    int l = 0, r = 0;
    update(arr[0], 1);
    for(int i = 0; i<m; i++){
        query q = Q[i];
        while(r < q.r) update(arr[++r], 1);
        while(q.l < l) update(arr[--l], 1);
        while(q.r < r) update(arr[r--], -1);
        while(l < q.l) update(arr[l++], -1);
 
        ans[q.i] = 0;
        for(int cur = 0; cur != nmax-1; cur = R[cur]){
            if((cur^xorval) < cur){
                ans[q.i] += frfreq[cur]*NCR(cur, cur^xorval);
                if(ans[q.i] >= mod) ans[q.i] %= mod;
            }
        }
    }
    return;
}
 
int main(){
    FASTIO;
    precal();
    int tc;
    cin>>tc;
    assert(1 <= tc && tc <= 5);
    for(int cs = 1; cs <=tc; cs++){
        int n, cnt = 0;
        cin>>n;
        assert(1 <= n && n <= 1000);
        map<int, int> mp;
        for(int i = 0; i<n; i++){
            cin>>arr[i];
            assert(1 <= arr[i] && arr[i] <= 1e9);
            if(!mp[arr[i]]) mp[arr[i]] = ++cnt;
            arr[i] = mp[arr[i]];
        }
 
        int m;
        cin>>m;
        assert(1 <= m && m <= 1000);
        for(int i = 0; i<m; i++){
            int l, r;
            cin>>l>>r;
            assert(1 <= l && l <= r && r <= n);
            Q[i] = {l-1, r-1, i};
        }
 
        mo(n, m);
        for(int i = 0; i<m; i++)
            cout<<ans[i]<<"\n";
    }
    return 0;
}
Tester's Solution
#include <bits/stdc++.h>
 
const int BUFFER_SIZE = int(1.1e5);
 
char _buf[BUFFER_SIZE + 10];
int _buf_pos, _buf_len;
 
char seekChar() {
    if(_buf_pos >= _buf_len) {
        _buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
        _buf_pos = 0;
    }
    assert(_buf_pos < _buf_len);
    return _buf[_buf_pos];
}
 
bool seekEof() {
    if(_buf_pos >= _buf_len) {
        _buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
        _buf_pos = 0;
    }
    return _buf_pos >= _buf_len;
}
 
char readChar() {
    char ret = seekChar();
    _buf_pos++;
    return ret;
}
 
int readInt(int lb, int rb) {
    char c = readChar();
    int mul = 1;
    if(c == '-') {
        c = readChar();
        mul = -1;
    }
    assert(isdigit(c));
 
    long long ret = c - '0';
    int len = 0;
    while(!seekEof() && isdigit(seekChar()) && ++len <= 19) {
        ret = ret * 10 + readChar() - '0';
    }
    ret *= mul;
 
    assert(len <= 18);
    assert(lb <= ret && ret <= rb);
    return (int)ret;
}
 
void readEoln() {
    char c = readChar();
    //assert(c == '\n');
    assert(c == '\n' || (c == '\r' && readChar() == '\n'));
}
 
void readSpace() {
    assert(readChar() == ' ');
}
 
// https://github.com/the-tourist/algo/blob/master/numeric/mint.cpp
template <typename T>
T inverse(T a, T m) {
    T u = 0, v = 1;
    while (a != 0) {
        T t = m / a;
        m -= t * a; swap(a, m);
        u -= t * v; swap(u, v);
    }
    assert(m == 1);
    return u;
}
 
template <typename T>
class Modular {
public:
    using Type = typename std::decay<decltype(T::value)>::type;
 
    constexpr Modular() : value() {}
    template <typename U>
    Modular(const U& x) {
        value = normalize(x);
    }
 
    template <typename U>
    static Type normalize(const U& x) {
        Type v;
        if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
        else v = static_cast<Type>(x % mod());
        if (v < 0) v += mod();
        return v;
    }
 
    const Type& operator()() const { return value; }
    template <typename U>
    explicit operator U() const { return static_cast<U>(value); }
    constexpr static Type mod() { return T::value; }
 
    Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
    Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
    template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
    template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
    Modular& operator++() { return *this += 1; }
    Modular& operator--() { return *this -= 1; }
    Modular operator++(int) { Modular result(*this); *this += 1; return result; }
    Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
    Modular operator-() const { return Modular(-value); }
 
    template <typename U = T>
    typename std::enable_if<std::is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
#ifdef _WIN32
        uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
    uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
    asm(
      "divl %4; \n\t"
      : "=a" (d), "=d" (m)
      : "d" (xh), "a" (xl), "r" (mod())
    );
    value = m;
#else
        value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
        return *this;
    }
    template <typename U = T>
    typename std::enable_if<std::is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type& operator*=(const Modular& rhs) {
        int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
        value = normalize(value * rhs.value - q * mod());
        return *this;
    }
    template <typename U = T>
    typename std::enable_if<!std::is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
        value = normalize(value * rhs.value);
        return *this;
    }
 
    Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
 
    template <typename U>
    friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
 
    template <typename U>
    friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
 
    template <typename U>
    friend std::istream& operator>>(std::istream& stream, Modular<U>& number);
 
private:
    Type value;
};
 
template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }
 
template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
 
template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }
 
template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
 
template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
 
template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
 
template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
 
template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
    assert(b >= 0);
    Modular<T> x = a, res = 1;
    U p = b;
    while (p > 0) {
        if (p & 1) res *= x;
        x *= x;
        p >>= 1;
    }
    return res;
}
 
template <typename T>
std::string to_string(const Modular<T>& number) {
    return to_string(number());
}
 
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
    return stream << number();
}
 
template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
    typename std::common_type<typename Modular<T>::Type, int64_t>::type x;
    stream >> x;
    number.value = Modular<T>::normalize(x);
    return stream;
}
 
/*
using ModType = int;
 
struct VarMod { static ModType value; };
ModType VarMod::value;
ModType& md = VarMod::value;
using Mint = Modular<VarMod>;
*/
 
constexpr int MOD = 998244353;
using Mint = Modular<std::integral_constant<std::decay<decltype(MOD)>::type, MOD>>;
 
const int MAXN = int(1e5);
 
Mint fac[MAXN+5], inv[MAXN+5], invfac[MAXN+5];
 
Mint comb (int n, int r) {
    return fac[n] * invfac[r] * invfac[n-r];
}
 
void run() {
    int N = readInt(1, MAXN);
    readEoln();
 
    std::vector<int> A(N);
    for(int i = 0; i < N; i++) {
        A[i] = readInt(1, int(1e9));
        if(i + 1 < N) readSpace(); else readEoln();
    }
 
    int Q = readInt(1, 100000);
    readEoln();
    for(int q = 0; q < Q; q++) {
        int l = readInt(1, N);
        readSpace();
        int r = readInt(l, N);
        readEoln();
        l -= 1;
        r -= 1;
 
        std::unordered_map<int, int> freq;
        for(int i = l; i <= r; i++) {
            freq[A[i]] += 1;
        }
 
        int all_xored = 0;
        for(auto &it : freq) all_xored ^= it.second;
 
        Mint ans = 0;
        if(all_xored != 0) {
            for(auto &it : freq) {
                all_xored ^= it.second;
                if(it.second >= all_xored) {
                    ans += comb(it.second, all_xored);
                }
                all_xored ^= it.second;
            }
        }
 
        printf("%d\n", ans());
 
    }
 
}
 
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
 
    int T = readInt(1, 5);
    readEoln();
 
    fac[0] = 1;
    invfac[0] = 1;
    fac[1] = 1;
    inv[1] = 1;
    invfac[1] = 1;
    for(int i = 2; i <= MAXN; i++) {
        fac[i] = fac[i-1] * i;
        inv[i] = inv[MOD % i] * (MOD - MOD / i);
        invfac[i] = invfac[i-1] * inv[i];
        assert((fac[i] * invfac[i])() == 1);
        assert((i * inv[i])() == 1);
    }
 
    while(T--) {
        run();
    }
    return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

const int mxN=1e5;
int s, n, a[mxN], b[mxN];

bool solve1() {
	//set of cards on the table
	set<int> s;
	//play cards in non-decreasing order
	for(int i=0; i<n; ++i) {
		if(i>0&&s.find(a[i])==s.end()) {
			//card is not on the table
			return 0;
		}
		if(a[i]>=b[i]) {
			//chefina can't beat
			return 0;
		}
		s.insert(a[i]);
		s.insert(b[i]);
	}
	return 1;
}

bool solve2() {
	if(n==2) {
		//the only way to have 2 turns is to play a[0], b[1], then b[0], a[1]
		return a[0]<b[1]&&b[0]<a[1];
	} else if(n>2) {
		//if all a are the same and >= all b then impossible
		if(a[0]==a[n-1]&&a[0]>=b[n-1])
			return 0;
		//if all b are the same and <= all a then impossible
		if(b[0]==b[n-1]&&b[n-1]<=a[0])
			return 0;
		//make sure there is no majority element
		map<int, int> c;
		for(int i=0; i<n; ++i)
			++c[a[i]];
		for(int i=0; i<n; ++i)
			++c[b[i]];
		for(auto p : c)
			if(p.second>n)
				return 0;
		//all other cases are possible
		return 1;
	}
	return 0;
}

bool solve() {
	//input
	cin >> n;
	for(int i=0; i<n; ++i)
		cin >> a[i];
	sort(a, a+n);
	for(int i=0; i<n; ++i)
		cin >> b[i];
	sort(b, b+n);

	//try to solve in 1 turn
	if(solve1())
		return 1;

	//try to solve in any number of turns
	if(s==2&&solve2())
		return 1;

	return 0;
}

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

	int t;
	cin >> t >> s;
	while(t--)
		cout << (solve()?"YES":"NO") << "\n";
}

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

4 Likes

conditions for n=2?
isn’t the conditions for n>2 same as n=2?

It can only end in 2 turns so a[0]<b[1]&&b[0]<a[1], where a and b are sorted.

1 Like

Can you helpe !
How can i think in this way specially by looking in question because i thinking about some backtracking but my idea is fail…So please help me and suggest some good advice so that i can solve more questions like this …

2 Likes

Best way for pattern based questions is a tester

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
vector<int> seq1,seq2;
bool playing=0;
bool solve1turn(){
    int n;
    cin>>n;
    long long int seq1[n],seq2[n];
    for(int i=0;i<n;i++){
        cin>>seq1[i];
    }
    for(int i=0;i<n;i++){
        cin>>seq2[i];
    }
    sort(seq1,seq1+n);
    sort(seq2,seq2+n);
    bool poss=1;
    bool mine=1;
    unordered_map<int,bool> done;
    for(int i=0;i<n;i++){
        if(seq2[i]<=seq1[i]){
            return 0;
            }
        if(i>0){
            if(seq1[i]!=seq1[i-1]){
                mine=0;
            }
        }
        if(!done[seq1[i]] && !mine){
            return 0;
            
        }
        done[seq1[i]]=1;
        done[seq2[i]]=1;
    }
    return 1;
}
bool solve(){
   if(playing)
        int n=seq1.size();
        int total[2*n];
        for(int i=0;i<n;i++){
            total[i]=seq1[i];
        }
        for(int i=0;i<n;i++){
            total[i+n]=seq2[i];
        }
        if(n==1){
             if(seq2[0]>seq1[0]){
                return 1;
             }
        return 0;
        }
        sort(seq1.begin(),seq1.end());
        sort(seq2.begin(),seq2.end());
        sort(total,total+2*n);
        for(int i=0;i<n;i++){
            if(total[i]==total[i+n]){
                return 0;
            }
        }
        if(seq1[0]==seq1[n-1] && seq1[0]>=seq2[n-1]){
            return 0;
        }
        if(n==2){
            if(seq1[0]>seq2[0] && seq1[1]>seq2[1]){
                if(seq1[1]!=seq1[0] && seq1[1]!=seq2[0]){
                    return 0;
                }
            }
        }
        return 1;
    }
    else{
        int n;
        cin>>n;
        int seq1[n];
        int seq2[n];
        int total[2*n];
        for(int i=0;i<n;i++){
            cin>>seq1[i];
            total[i]=seq1[i];
        }
        for(int i=0;i<n;i++){
            cin>>seq2[i];
            total[i+n]=seq2[i];
        }
        sort(seq1,seq1+n);
        sort(seq2,seq2+n);
        sort(total,total+2*n);
        for(int i=0;i<n;i++){
            if(total[i]==total[i+n]){
                return 0;
            }
        }
        if(seq1[0]==seq1[n-1] && seq1[0]>=seq2[n-1]){
            return 0;
        }
        if(n==2){
            if(seq1[0]>seq2[0] && seq1[1]>seq2[1]){
                if(seq1[1]!=seq1[0] && seq1[1]!=seq2[0]){
                    return 0;
                }
            }
        }
        return 1;
    }    
}
void play(multiset<int> p1, multiset<int> p2){
       playing=1;
       multiset<int> table;
       bool turn=1;
       int last;
       while(p1.size()!=0 || p2.size()!=0){
            int a;
            cin>>a;
            if(a==-2){
                break;
            }
            if(a==-1){
                if(p1.size()==0 || p2.size()==0){
                    break;
                }
                if(turn && table.size()){
                    table.clear();
                    swap(p1,p2);
                }
                else{
                    for(int x:table){
                        p2.insert(x);
                    }
                    table.clear();
                }
                turn=1;
                cout<<"p1 : ";
                for(int x : p1){
                    cout<<x<<" ";
                }
                cout<<"\n";
                cout<<"p2 : ";
                for(int x : p2){
                    cout<<x<<" ";
                }
                cout<<"\n";
                cout<<"table : ";
                for(int x: table){
                    cout<<x<<" ";
                }
                cout<<"\n\n";
                continue;
            }
            if(turn){
                if(p1.find(a)!=p2.end()){
                    if(table.size()==0 || table.find(a)!=table.end()){
                        p1.erase(p1.find(a));
                        table.insert(a);
                        last=a;
                        turn=0;
                    }
                }
            }
            else{
                if(p2.find(a)!=p2.end()){
                    if(a>last){
                        p2.erase(p2.find(a));
                        table.insert(a);
                        turn=1;
                    }
                }
             }
            cout<<"p1 : ";
            for(int x : p1){
              cout<<x<<" ";
            }
            cout<<"\n";
            cout<<"p2 : ";
            for(int x : p2){
              cout<<x<<" ";
            }
            cout<<"\n";
            cout<<"table : ";
            for(int x: table){
              cout<<x<<" ";
            }
            cout<<"\n\n";
       }
       if(p1.size()==0 && p2.size()==0){
           if(solve()){
                cout<<"success\n";
           }
           else{
               cout<<"failure\n";
           }
       }
       else{
           if(!solve()){
               cout<<"success\n";
           }
           else{
               cout<<"failure\n";
           }
       }
}
int main(){
    int t,s;
    cin>>t>>s;
    if(s==0){
        int n;
        cin>>n;
        multiset<int> p1,p2;
        for(int i=0;i<n;i++){
            int a;
            cin>>a;
            seq1.push_back(a);
            p1.insert(a);
        }
        for(int i=0;i<n;i++){
            int a;
            cin>>a;
            seq2.push_back(a);
            p2.insert(a);
        }
        play(p1,p2);
    }
    else if(s==2){
        while(t--){
            if(solve()){
                cout<<"YES\n";
            }
            else{
                cout<<"NO\n";
            }
        }
    }
    else{
        while(t--){
            if(solve1turn()){
                cout<<"YES\n";
            }
            else{
                cout<<"NO\n";
            }
        }
    }
}

Input

1 0
n
p1 cards
p2 cards

Then you can play with different cases and add checks accordingly.

I misread the question and thought that the “next turn” happened only when the roles changed.

Anyways, thanks for the editorial!

Can u elaborate it why !!?

@tmwilliamlin can you please see my code for BREAK and suggest me how do I get 100 points.

He will elaborate it in Explanation :stuck_out_tongue:

@vijju123 everyone’s logic is pretty different I just want guidance could you help please?

Can someone plzz help to understand this

Sub-task 1 gives almost the easiest 50 points in the competition:

Sort each player’s cards into ascending order.
For the game to end in a draw in one turn, every card of index i held by player B must be greater then the corresponding card of index i held by player A, and every card held by player A must either be equal to the smallest card held by A or to a card held by B.

1 Like

Be patient editorial will be updated soon and there @tmwilliamlin will explain it.

For sub task 1

if chef(attacker) don’t use smallest card then defender will defend it with card which is higher in rank so smallest card of chef can’t be used in future unless 1st used card of chef is same as smallest;

like
chef : 1 2 3
friend:2 3 4

if chef uses 2 or 3 game could not end in one turn.

if i sort the chef(attacker) cards in non increasing order and defender cards in ascending order , whats the problem arise ?

In such case chef uses it’s maximum card in first turn then chef will not be able to use cards which are lower in rank because there will be no lower card on table which matches chef’s lower number card

Here is an example:
chef : 5 5 3 2 1 (non increasing order)
friend:2 3 5 8 10(ascending order)

there is tie possible as( 1,2,2,3,3,5,5,8,5,10)

Finished and updated.

Exactly correct …u thought in the right direction

can you plz elaborate on this ???

Just run it on terminal. You can play the game so you know when you can draw or not.