I'm a simple guy. When I find out I can reduce a problem to something known (or something I suspect must be known) and I've never learned it, then I just look in the internet to see if my approach may be feasible. When I was solving 2155F - Juan's Colorful Tree, which I'll refer on the blog as JCT, and found out it could be reduced to finding the size of the intersection of ordered sets, I did just that. What I found was

Binary Search

Given two ordered sets $$$A$$$ and $$$B$$$, which Im assuming to be of type vector<int>, then this one works in time $$$O(|A| log |B| )$$$ where $$$|A|\leq |B|$$$. The code is something like

int res=0;
for(int ac:A)res+=binary_search(B.begin(),B.end(),ac);

When I sent it to JCT. It got AC with $$$\approx 1.8$$$ seconds and a total complexity of something like $$$O(n\sqrt{n}lgn)$$$. However, now it seems to be patched out (it got in $$$\approx 1.8$$$ seconds when testing, now it gets TLE). But I decided I could do better...

Weird? Binary Search

I noticed that always doing binary search on the range $$$ [0,|B|) $$$ should be a bit costly, as on every iteration I'm binary searching from 0. I noticed that the maximum index $$$j$$$ that makes $$$ A[i]\geq B[j] $$$ is monotonically increasing on $$$i$$$. This means that if the last index I found was $$$j$$$, then the new index will be in $$$ j'\in[j,|B|) $$$. This should reduce the running time a bit, so I implemented something like

int ind=0,jmp=1,res=0;
for(int ac:A){
	while( jmp+ind<int(B.size()) && B[jmp+ind]<=ac ) {
		iv+=jmp;
		jmp*=2;
	}
	while( jmp>1 ) {
		jmp/=2;
		if( jmp+ind<int(B.size())&& B[jmp+ind]<=ac)iv+=jmp;
	}
	res+=B[ind]==ac;
}

I assumed the complexity of this fragment was also $$$O(|A| log |B|)$$$. Then I sent it to JCT. It got AC with $$$\approx 0.8$$$ seconds and assumed the total complexity on my submission was something like $$$O(n\sqrt{n}lgn)$$$. Then I went to sleep

Real Complexity

My best solution actually went through with more or less the same time as the model solution, so I was asked (jampm) if I was sure the real complexity on JCT was $$$O(n\sqrt{n}lgn)$$$. After a while thinking, I realized there where some cases when the second algorithm worked in time $$$O(|A|)$$$, which is when $$$|A|=|B|$$$ as it can become the two-pointer idea. This more or less countered the worst case I thought that gave the $$$O(n\sqrt{n}lgn)$$$ complexity, reducing it to $$$O(n\sqrt{n})$$$ (at least in the construction I thought).

I kept thinking on the real complexity of the second algorithm. I conjectured it was something like $$$O(|A|(1+log|B|-log|A|))=O(|A|(1+log(|B|/|A|)))$$$, where the +1 is just for it to be 'well-conditioned' when $$$|A|=|B|$$$. It turns out that's true

Concluding

This idea is not actually new. After looking further in internet, it appears this problem has been studied in research (this same idea and many others have been discovered); however, I still find it interesting enough to write about it on this format because I found the second complexity a bit unexpected, the algorithm is somewhat simple and this version seems not so easy to find.

My submission to JCT is 342818172. I didn't actually found an upper-bound to the complexity on my submission; I assume it's $$$O(n\sqrt{n})$$$ and found a case that forces it to go to $$$O(n\sqrt{n})$$$, but it's not proven.

Testing was a fun experience. I found solving JCT interesting. I now know a bit more about the submission I cooked.

osvarp out