a codeforces contest.
A. Grid L
two necessary conditions:
- total # of edges =
- because each L-shape removes one horizontal and one vertical edge, it must hold that
WLOG, let (rectangle more wide than tall). note that we can always tile an by square like so:
and that this can be extended to the right like so for any :
(both of these images are from the official editorial)
every vertical segment is covered by an L-piece, so this proves the sufficiency of the second condition. from the first condition, only pairs are viable, so we can just check all by brute force.
B. Unique Values
note that in an array in which every element occurs either once or twice, the parity of the number of single elements is always the same as the parity of the entire array. therefore, when we query, the only time the result does not have the same parity as is when 3 of the same value are contained. therefore, our query becomes the following:
select indices, and check whether any element occurs three times along those indices.
from here, we can binary search to find each of the three occurrences in queries, solving the entire problem in queries.
https://codeforces.com/contest/2219/submission/371073987
C. Coloring a Red Black Tree
First, note that thereβs definitely no point of operating on a red node. Thus, all nodes will toggle only from black to red, the choice that we have to make is just the order in which the nodes become red.
Formally, letβs direct edge from if turns red before . If a node is initially red, it must have 0 in-degree, and any other node must have positive in-degree (otherwise it will never be able to turn red). Then, the total time taken by this configuration is just over all nodes. We can minimize this quantity with a tree DP, in which dp[i][0/1] denotes the minimum time to turn the entire subtree of i red, and the 0/1 denotes whether the edge from to its parent is directed toward or not.