Editorial for COCI '22 Contest 2 #3 Lampice

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
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 $(0, 0)$ ~(0, 0)~ and the ones that don't separately.

If the rectangle contains the point $(0, 0)$ ~(0, 0)~, then it must also contain all points $(x_2, y_2)$ ~(x_2, y_2)~, and for it to have an area different from $0$ ~0~ it must also contain the point $(1, 1)$ ~(1, 1)~. If it has a width of $x$ ~x~ and a height of $y$ ~y~, we get that for all points $(x_2, y_2)$ ~(x_2, y_2)~, $x \ge x_2$ ~x \ge x_2~ and $y \ge y_2$ ~y \ge y_2~. We also know $x \le n$ ~x \le n~ and $y \le m$ ~y \le m~, so if we add $1$ ~1~ to $x_2$ ~x_2~ and $y_2$ ~y_2~ we get the condition $\max(x_2) \le x \le n$ ~\max(x_2) \le x \le n~ and $\max(y_2) \le y \le m$ ~\max(y_2) \le y \le m~, so we have $n+1-\max(x_2)$ ~n+1-\max(x_2)~ possibilities for $x$ ~x~ and $m+1-\max(y_2)$ ~m+1-\max(y_2)~ possibilities for $y$ ~y~, which is in total $(n+1-\max(x_2))(m+1-\max(y_2))$ ~(n+1-\max(x_2))(m+1-\max(y_2))~ possible rectangles.

If the rectangle doesn't contain the point $(0, 0)$ ~(0, 0)~, then it can't contain any other point $(x_2, y_2)$ ~(x_2, y_2)~, 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 $i$ ~i~), we can calculate the number of such rectangles by finding the rightmost column left of $i$ ~i~ which has a lower or equal maximum height (let's call it $l$ ~l~; let it be $-1$ ~-1~ if there is no such column) and the leftmost column right of $i$ ~i~ which has a lower maximum height (let's call it $r$ ~r~; let it be $m+1$ ~m+1~ if there is no such column), then we know that the height must be between $1$ ~1~ and the maximum height for column $i$ ~i~ (let's call it $h$ ~h~), that the leftmost column of the rectangle is between $l+1$ ~l+1~ and $i$ ~i~ and that the rightmost column of the rectangle is between $i$ ~i~ and $r-1$ ~r-1~. So, for the leftmost column we have $i-l$ ~i-l~ options, for the rightmost column we have $r-i$ ~r-i~ options, but we must subtract the option that the rectangle has a width of $0$ ~0~, for the height we have $h$ ~h~ options, so the number of rectangles that we're looking for is $h((i-l)(r-i)-1)$ ~h((i-l)(r-i)-1)~. Quickly calculating $l$ ~l~ and $r$ ~r~ for each $i$ ~i~ is a well-known problem that can be solved using a stack, and $h$ ~h~ can quickly be calculated for each $i$ ~i~ if we know what its value was for the last row, so the time complexity ends up being $\mathcal O(nm+k)$ ~\mathcal O(nm+k)~.

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 $\mathcal O(k(nm)^2)$ ~\mathcal O(k(nm)^2)~.

For the third subtask, let's uniformly randomly generate a $60$ ~60~-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 $x \mathbin{\text{xor}} x = 0$ ~x \mathbin{\text{xor}} x = 0~, 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 $0$ ~0~. If it's not, then for each colour which has exactly $1$ ~1~ lamp of its colour in the rectangle the value is xored with a uniformly randomly distributed number between $0$ ~0~ and $2^{60}-1$ ~2^{60}-1~; the result of that is another uniformly randomly distributed number between $0$ ~0~ and $2^{60}-1$ ~2^{60}-1~, so the probability that the xor ends up being $0$ ~0~ is $\frac{1}{2^{60}}$ ~\frac{1}{2^{60}}~. Since there are $\frac{n(n+1)m(m+1)}{4}$ ~\frac{n(n+1)m(m+1)}{4}~ rectangles in total, the probability of this solution saying that a rectangle is good even though it isn't is at most $\frac{n(n+1)m(m+1)}{2^{62}}$ ~\frac{n(n+1)m(m+1)}{2^{62}}~, 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 $\mathcal O((nm)^2+k)$ ~\mathcal O((nm)^2+k)~.

For the fourth subtask, if we fix the leftmost and rightmost column of the rectangle (let's call them $l$ ~l~ and $r$ ~r~), our goal is to find the number of rectangles with xor $0$ ~0~ with their leftmost column being $l$ ~l~ and their rightmost column being $r$ ~r~. If we say that $a_i$ ~a_i~ is equal to the xor of all values in the $i^\text{th}$ ~i^\text{th}~ row and the $l^\text{th}$ ~l^\text{th}~ to $r^\text{th}$ ~r^\text{th}~ column, our goal is to find the number of subarrays of $a_i$ ~a_i~ whose xor is $0$ ~0~ and whose length is at least $2$ ~2~ (the second condition can be solved by erasing subarrays of size $1$ ~1~, so we'll ignore them from now on). Let $p_i = \text{xor}(a_{0 \dots i-1})$ ~p_i = \text{xor}(a_{0 \dots i-1})~. Then $\text{xor}(a_{l \dots r}) = p_l \mathbin{\text{xor}} p_{r+1}$ , so we're looking for the number of pairs in the array $p$ ~p~ whose xor is $0$ ~0~, so we're looking for the number of pairs of equal elements in the array $p$ ~p~, which can easily be solved in $\mathcal O(m \log m)$ ~\mathcal O(m \log m)~. The total time complexity is $\mathcal O(n^2 m \log m)$ ~\mathcal O(n^2 m \log m)~.

Comments

0

patrickngo2007 commented on Nov. 12, 2024, 7:18 a.m. ← edited →

jit crazy