PROBLEM LINK:
Author: Kevin Atienza
Testers: Sergey Kulik and Vasya Antoniuk
Translators: Vasya Antoniuk (Russian), Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Range distinct-count query, lowest common ancestor, dynamic programming
PROBLEM:
Given an R\times C rectangular maze with a tree structure, answer Q queries. In each query, given the starting cell (i_1,j_1), the ending cell (i_2,j_2), and the initial direction d, find the number of visited cells if you follow the right-hand rule.
QUICK EXPLANATION:
Root the maze at node (1,1). Order the children counterclockwise.
For each node (i,j), compute its depth, subtree size, and jump pointers (to compute LCAs quickly). Also, compute these two things:
- The number of visited nodes from that node to node (1,1) assuming your direction is towards the parent and you follow the right-hand rule. Call this R(i,j).
- The number of visited nodes from that node to node (1,1) assuming your direction is towards the parent and you follow the left-hand rule. Call this L(i,j).
Then for each query, the bulk of the answer is R(i_1,j_1) - R(i_L,j_L) + L(i_2,j_2) - L(i_L,j_L) where (i_L,j_L) is the LCA of (i_1,j_1) and (i_2,j_2). You still need to adjust for some subtrees in (i_1,j_1), (i_2,j_2) and (i_L,j_L) to account for the initial direction, final direction and the change in directions.
There’s an alternate solution, which involves traversing the whole grid once, storing 4RC distinct states, and performing range distinct-count queries on it.
EXPLANATION:
Coming soon.
Time Complexity:
O((RC + Q) \log (RC))