Editorial for ECOO '21 P6 - Problematic Pathways
Submitting an official solution before solving the problem yourself is a bannable offence.
Authors:
,Subtask 1
For every segment between and
, we can either direct it from
to
or we can direct it from
to
. This means that every segment has two different states. So, we can try all
different configurations and find the minimal one. We can find the number of pairs for each configuration in
time.
Time complexity:
Subtask 2
We can think about this problem as partitioning the segments into multiple contiguous parts where every segment in one part has the same orientation and different orientation from the adjacent contiguous parts. We will try to apply dynamic programming to this program. will be a boolean.
is true when it is possible to get
pairs among the first
friends and false otherwise. To find whether
is true or not, we can try to consider every suffix
where
is a contiguous segment described above. So, we have
where is the number of pairs of the same element in the subarray
. We can quickly compute
by adding the number of other elements that are equal to
in
to
. This can be done quickly by having a frequency array. Thus, it is possible to have
states and
transition.
Time Complexity:
Subtask 3
Note that for a fixed and
, then for all
, if
is true, then
is true. Since
is constant, then we can simulate all
together with a bitset by getting the Bitwise Or of
shifted to the left by
with the current
for each
.
Time Complexity: where
is the word size. In our case,
.
Subtask 4
Note that we have states, so we cannot compute all the states if we want to solve for
. We want to find some structure of
that allows us to compute less states. Define
to be minimal such that
, define
to be the maximal such that
, define
to be the maximal such that
,
. We can calculate
,
, in
time. Define
recursively as
and
. We claim that
is large
for large
. Some intuition for this is:
,
will be extended if there exists
such that
and
. Since
is bounded by
, and
is large for
by induction, such a segment must exist.
Once we have that is large, for
, we can only compute states
where
, which turns out to be very few states for
, but this is not enough for full points.
Subtask 5
Note that since we are only considering states where is very large, the number of
that we can transition to from
is very small. For each
, we can precompute the order in which we can transition to
for all
in
time. Then, when solving for
, we can binary search for the first
in the order that we can transition to, instead of looping over all possible transitions. With these observations, we compute far less states than in the Subtask 4 solution, and compute each state much faster, allowing us to solve for
.
If you have a proof or countercase for this solution, feel free to put it in the comments.
Comments