FILLIN0 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: ro27
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Elementary combinatorics

PROBLEM:

You’re given a permutation P of length 2N with some of its elements missing.
Find the number of ways of filling in the zeros such that

|P_1 - P_2| + |P_3 - P_4| + \ldots + |P_{2N} - P_{2N-1}|

is maximized.

In the easy version, it’s guaranteed that P_{2i} = 0 for all i.

EXPLANATION:

One way to look at this setup is that we have N pairs of indices: namely (1, 2), (3, 4), \ldots, (2N-1, 2N).
Each element must be assigned to one of these N pairs (some elements are already assigned), and then we sum up the differences between the elements of each pair.

Let’s try to solve a less restrictive version: what if P_i = 0 for every i?
To maximize the sum of differences, one greedy method that comes to mind is to pair 1 with 2N, 2 with 2N-1, and so on till N with N+1.
In this case, the sum of differences is

(2N-1) + (2N-1 - 2) + \ldots + (N+1 - N) \\ = (2N + (2N-1) + \ldots + (N+1)) - (1 + 2 + \ldots + N)

That is, we obtain the sum of the largest N numbers, minus the smallest N numbers.
This is optimal, and in fact any arrangement which ensures that elements \gt N are added and elements \leq N are subtracted will attain this optimal value - it’s not hard to see why, since each pair assigns a plus to one number and a minus to another; so we end up with N each of pluses and minuses in the end.

This means all we need to do is pair “large” (\gt N) elements with “small” (\leq N) elements - there is no other way to achieve the maximum sum.

Counting this is fairly simple:

  • There are N choices for what to pair with 1, then N-1 choices for what to pair with 2, then N-2 choices for 3, and so on till 1 choice for N.
    The total number of ways is hence N\cdot (N-1) \cdot \ldots \cdot 2\cdot 1 = N!
  • Once we have our pairs, there are N! ways to arrange them in different orders.
  • Further, the elements within a pair can be in any order.
    There are two ways for each pair, so we obtain an extra factor of 2^N.

So, in the case when P_i = 0 for all i, the answer is simply N!\cdot N!\cdot 2^N.

Now, let’s go back to the harder version, where some P_i may be non-zero.
Since P_{2i} = 0 for all i, there is at most one element in each pair.
This means we are still able to pair up each large element with some small element - it’s just that the ways of doing so are slightly more restricted.

Specifically, suppose there are already x small and y large elements.
Let there also be k pairs with no elements assigned to them yet.
Then,

  • There are (N-x) remaining small elements.
    These must be assigned to each of the (N-x) pairs that don’t yet have a small element.
    This can be done in (N-x)! ways.
  • Similarly, there are (N-y)! ways of assigning the large elements to the pairs that don’t have one yet.
  • Finally, for the k pairs that don’t have anything assigned initially, there are two ways of ordering the elements assigned to it.

So, the required number of configurations is just

(N-x)! \cdot (N-y)! \cdot 2^k

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

const int mod = 998244353;

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

    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<int> p(2*n);
        for (int &x : p) cin >> x;

        int small = 0, large = 0, empty = 0;
        for (int i = 0; i < 2*n; i += 2) {
            empty += p[i] == 0;
            small += 1 <= p[i] and p[i] <= n;
            large += p[i] > n;
        }
        
        int ans = 1;
        for (int i = 0; i < empty; ++i)
            ans = (2ll * ans) % mod;
        for (int i = 1; i <= n-small; ++i)
            ans = (1ll * ans * i) % mod;
        for (int i = 1; i <= n-large; ++i)
            ans = (1ll * ans * i) % mod;
        cout << ans << '\n';
    }
}
1 Like
2

I am wondering what is wrong with my solution? I submitted this during the contest, and this implemented exactly the editorial idea, but got failure on hidden test case that I can’t access.

Edge cases I checked: factorial(0) is 1, so when either side factorial got nothing is fine.
Python has big integers, so it might ran out of time, but it should never give wrong answer, but judge is telling me I am giving wrong answer.
I performed the modulo operation, so that should be fine too.

Anything else could get wrong with this?

from sys import stdin
from math import factorial

def run(arr):
    n = len(arr) // 2
    left = 0
    right = 0
    loose = 0
    for i in range(n):
        if arr[2 * i] == 0:
            left += 1
            right += 1
            loose += 1
        elif arr[2 * i] >= n:
            right += 1
        else:
            left += 1
    print((factorial(left) * factorial(right) * (2 ** loose)) % 998244353)

def main():
    data = []
    for line in stdin:
        data.append(line.strip())
    num_test_case = int(data[0])
    line_number = 1
    for _ in range(num_test_case):
        n = data[line_number]
        line_number += 1
        arr  = [int(x) for x in data[line_number].split()]
        line_number += 1
        run(arr)

if __name__ == "__main__":
    main()
3

Your code fails on

1
2
1 0 2 0

The answer is 2 since both [1, 3, 2, 4] and [1, 4, 2, 3] are valid.
(Your mistake is the check arr[2 * i] >= n, it should be arr[2 * i] > n.)

Once you fix correctness - yes, this will indeed become an issue.
The point of the modulo is to prevent you from having to work with numbers that are too large, which is generally quite slow.

For example, instead of factorial(n) % mod (which must first compute factorial(n) - that can be extremely large), you can do

fac = 1
for i in range(1, n+1): fac = (fac * i) % mod

The final result is still N! under modulo, but fac itself never exceeds mod so you always work with small integers, which is fast.

1 Like