Llarc's blog

By Llarc, 12 days ago, In English

problem link : https://codeforces.com/contest/1400/problem/D

I'm sorry to bother this community, but there are a lot of interesting tricks involved and I'm enjoying it so much that I'm posting it to share with you.

We first try to solve a weakened version of this problem, that is, $$$1≤a_i≤2$$$, which can be helpful to think about. For this problem just enumerate $$$k$$$ and maintain that information: the number of $$$1$$$'s and $$$2$$$'s on the left and right of $$$k$$$, and the number of $$$(x,y)$$$ binary groups satisfying $$$a_x=1$$$ and $$$a_y=2$$$ or $$$a_x=2$$$ and $$$a_y=1$$$ on the left of $$$k$$$.

This can then be computed within $$$O(n)$$$, here is the code for this part : https://codeforces.com/contest/1400/submission/167092044

We assume a number $$$b$$$ to represent the threshold of the classification discussion. When the number of a number exceeds $$$b$$$, it means that it is sufficiently large to be given separate attention. It is easy to derive that there are at most $$$n/b$$$ different such numbers.

If $$$a_i$$$ and $$$a_j$$$ are both such numbers, then we can simply extract them two by two and use the $$$O(n)$$$ algorithm above to compute them with a total complexity of $$$O(n^2/b)$$$.

If $$$a_i$$$ or $$$a_j$$$ are not such numbers, then the computation is tricky because their distribution is messy, but it is easy to know that the number of binary groups $$$(x,y)$$$ that satisfy $$$a_x=a_y$$$ and the number of $$$a_x$$$ is less than $$$b$$$ is no higher than $$$nb$$$.

So we preprocess all such binary groups and subsequently use Mo's algo optimization on them, which can be computed easily $$$O(1)$$$ moving the pointer and taking $$$O(nb^2+n^2/b)$$$ for the computation.

We just need to take $$$b=n^{0.3}$$$, then the total complexity is $$$O(n^{1.7})$$$, end.

I found it almost impossible for me to avoid Mo's algo when optimizing, if anyone finds something faster than n^(5/3), or the same time and without Mo's algo, please contact me. Thanks in advance.

 
 
 
 
  • Vote: I like it
  • +56
  • Vote: I do not like it

»
12 days ago, # |
  Vote: I like it +7 Vote: I do not like it

This problem can be improved to $$$O(n\sqrt{n\log n})$$$ also using Mo's algorithm, I think this performs better than the $$$O(n^{1.7})$$$ one when $$$n\le 10^5$$$.