PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
N people stand in a queue, but are unaware of which direction they’re facing with respect to the front of the queue.
The i-th person sees A_i people ahead of him in the direction he’s facing.
How many orderings of people exist that can satisfy this?
EXPLANATION:
Consider the person standing at the i-th position from the front of the queue (we use 1-indexing).
If he’s facing forward, he’ll see i-1 people ahead of him; whereas if he’s facing backward, he’ll see N-i people ahead of him.
Turning this around, if someone sees A_i people ahead of them, they’re either facing forward (meaning they’re at position A_i + 1), or they’re facing backward (meaning they’re at position N - A_i).
So, for each person i, we obtain (at most) two positions where i can be standing in the queue.
Further, observe that these positions are paired up: 1 is always paired to N, 2 is always paired to N-1, and so on.
In general, for each i we obtain the pair (A_i+1, N-A_i) where he can be; which has the nice property that the two numbers sum up to N+1.
This means that any two pairs are either equal or completely disjoint.
Now that we have the pairs, let’s try to place people according to them.
Let c_x be the number of people corresponding to the pair (x, N+1-x) (where x \lt N-x).
Then,
- If c_x = 2, we have two people and two positions to place them in.
Clearly there are two ways to do this. - If c_x \neq 2, there is in fact no way to place people.
This is because:- If c_x \gt 2 then we’re trying to place more than two people in two positions, which is obviously impossible.
- If c_x \lt 2 then after placing people we’ll have at least one empty position.
However, since pairs are disjoint, people corresponding to other pairs cannot be placed in this empty position; meaning that in the final queue there will still be an empty position - which is also impossible.
So, quite simply, if c_x = 2 we have two choices, and otherwise we have none.
The total number of choices is just obtained by multiplying all the possibilities.
In particular, if
then the answer is just the product of 2, \left\lfloor \frac{N}{2} \right\rfloor times, i.e.
In any other case, where at least one c_i is not two, the answer is 0.
Note that one minor detail we didn’t consider is the pair (x, N+1-x) where x = N+1-x.
This only occurs when N is odd, and corresponds to the “middle position” of the queue.
Here, rather than two, there’s only one position available; so this x should satisfy c_x = 1.
However, this condition doesn’t need to be explicitly checked for: if all other values of c_x are 2 then this will definitely be 1; and if some other c_x is not 2 then the answer is 0 anyway.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 998244353;
void Solve()
{
int n; cin >> n;
vector <int> f(n, 0);
for (int i = 0; i < n; i++){
int x; cin >> x;
x = min(x, n - 1 - x);
f[x]++;
}
for (int i = 0; i < n / 2; i++){
if (f[i] != 2){
cout << 0 << "\n";
return;
}
}
int ans = 1;
for (int i = 0; i < n / 2; i++){
ans *= 2;
ans %= mod;
}
cout << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Editorialist's code (PyPy3)
mod = 998244353
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ct = [0]*n
for x in a:
ct[min(x, n-1-x)] += 1
ans = 1
for i in range(n):
if i >= n-1-i: break
if ct[i] != 2: ans = 0
ans = ans*2 % mod
print(ans)
