JOI 18 Final Round - Snake Escaping

Author: Kai Wang


We use SOS DP to compute super[mask]super[mask] and sub[mask]sub[mask], which denote maskSaS\sum\limits_{mask\in S} a_S and SmaskaS\sum\limits_{S\in mask} a_S respectively.

For a query, let AA be the set of 00's, BB be the set of 11's, and CC be the set of ??'s. By Pigeonhole principle, min{A,B,C}6\min\{A,B,C\}\le 6, and I claim we can answer queries in O(2min{A,B,C})O(2^{\min\{A,B,C\}}).

If a query has C6|C|\le 6, we can brute force over all the subsets with 0's at A and 1's at B. Since there are 2C2^{|C|} subsets, this takes O(2C)\mathcal{O}(2^{|C|}) operations.

Otherwise, we can answer queries with the principle of inclusion-exclusion. The answer is simply aAsuper[Ba](1)a\sum\limits_{a\in A} super[B | a] (-1)^{|a|}, which we can calculate in O(2A)\mathcal{O}(2^{|A|}).

The answer is also bBsub[Cb](1)Bb\sum\limits_{b\in B} sub[C | b] (-1)^{|B|-|b|}, which we can calculate in O(2B)\mathcal{O}(2^{|B|}). They can be computed efficiently with submask enumeration. For a detailed explanation on how submask enumeration works, check cp-algorithms.

Time Complexity: O(2LL+2L3Q)\mathcal{O}(2^L\cdot L+2^{\frac{L}{3}}Q)

We compute supersuper and subsub in O(2LL)\mathcal{O}(2^L\cdot L) with SOS DP, and we process each query in O(2L3)\mathcal{O} (2^{\frac L3}).

import java.io.*;
import java.util.*;
public class snake_escaping {
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!