Editorial for COCI '22 Contest 2 #3 Lampice
Submitting an official solution before solving the problem yourself is a bannable offence.
For the first subtask, let's look at rectangles which contain the point and the ones that don't separately.
If the rectangle contains the point , then it must also contain all points
, and for it to have an area different from
it must also contain the point
. If it has a width of
and a height of
, we get that for all points
,
and
. We also know
and
, so if we add
to
and
we get the condition
and
, so we have
possibilities for
and
possibilities for
, which is in total
possible rectangles.
If the rectangle doesn't contain the point , then it can't contain any other point
, so our goal is to find the number of rectangles without any of the chosen points. If we fix the lower row of the rectangle, then for each column we can calculate the maximum height of a rectangle in that column (i.e. how far up can we go without reaching a lamp). If we fix the leftmost column that has the lowest maximum height (let's call it
), we can calculate the number of such rectangles by finding the rightmost column left of
which has a lower or equal maximum height (let's call it
; let it be
if there is no such column) and the leftmost column right of
which has a lower maximum height (let's call it
; let it be
if there is no such column), then we know that the height must be between
and the maximum height for column
(let's call it
), that the leftmost column of the rectangle is between
and
and that the rightmost column of the rectangle is between
and
. So, for the leftmost column we have
options, for the rightmost column we have
options, but we must subtract the option that the rectangle has a width of
, for the height we have
options, so the number of rectangles that we're looking for is
. Quickly calculating
and
for each
is a well-known problem that can be solved using a stack, and
can quickly be calculated for each
if we know what its value was for the last row, so the time complexity ends up being
.
For the second subtask, we can just check all rectangles and for each colour of lamps see if the condition is fulfilled or not, which works in a time complexity of .
For the third subtask, let's uniformly randomly generate a -bit number for each colour of lamps where all of the generated numbers are independent, and let's give each lamp the value equal to the number generated for its colour. If we look at the xor of the values of all the lamps in a rectangle, for each colour, if both lamps of that colour are in the rectangle, then, since
, that colour won't contribute to the xor, and that's also obviously true for colours that aren't included in the rectangle. Therefore, if for each colour either both lamps of that colour are in the rectangle or both aren't, then the xor of all values in that rectangle will be
. If it's not, then for each colour which has exactly
lamp of its colour in the rectangle the value is xored with a uniformly randomly distributed number between
and
; the result of that is another uniformly randomly distributed number between
and
, so the probability that the xor ends up being
is
. Since there are
rectangles in total, the probability of this solution saying that a rectangle is good even though it isn't is at most
, which is small enough. The xor of all values in the rectangle can easily be calculated using prefix sums, which gives us a complexity of
.
For the fourth subtask, if we fix the leftmost and rightmost column of the rectangle (let's call them and
), our goal is to find the number of rectangles with xor
with their leftmost column being
and their rightmost column being
. If we say that
is equal to the xor of all values in the
row and the
to
column, our goal is to find the number of subarrays of
whose xor is
and whose length is at least
(the second condition can be solved by erasing subarrays of size
, so we'll ignore them from now on). Let
. Then
, so we're looking for the number of pairs in the array
whose xor is
, so we're looking for the number of pairs of equal elements in the array
, which can easily be solved in
. The total time complexity is
.
Comments
jit crazy