JOI 18 Final Round - Snake Escaping
Author: Kai Wang
We use SOS DP to compute and , which denote and respectively.
For a query, let be the set of 's, be the set of 's, and be the set of 's. By Pigeonhole principle, , and I claim we can answer queries in .
If a query has , we can brute force over all the subsets with 0's at A and 1's at B. Since there are subsets, this takes operations.
Otherwise, we can answer queries with the principle of inclusion-exclusion. The answer is simply , which we can calculate in .
The answer is also , which we can calculate in . They can be computed efficiently with submask enumeration. For a detailed explanation on how submask enumeration works, check cp-algorithms.
Time Complexity:
We compute and in with SOS DP, and we process each query in .
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!