tzc_wk's blog

By tzc_wk, history, 6 months ago, In English,

Recently I'm learning network flow. Could anyone give me a list of problems of network flow on Codeforces & Gym & Atcoder. Not too hard, just with difficulty 2300~2700. Thanks a lot.

Read more »

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

By tzc_wk, history, 7 months ago, In English,

I've thought of another solution of problem D during the contest, which may also be possible.

Let $$$S_{i,0}$$$ be the set of intervals that overlaps with interval in venue A, and $$$S_{i,1}$$$ be the set of intervals that overlaps with interval in venue B. Then we only need to check $$$S_{i,0}!=S_{i,1}$$$.

As a set is hard to express, we can express them in the binary form, i.e. the $$$2^0$$$ digit of the binary form is $$$1$$$ if the $$$i$$$-th interval overlaps with interval $$$1$$$, $$$0$$$ otherwise; the $$$2^1$$$ digit of the binary form is $$$1$$$ if the $$$i$$$-th interval overlaps with interval $$$1$$$, $$$2$$$ otherwise and so on. As the number is rather large, we may modulo with a large number, for example $$$993244853$$$. Then the only thing we need to do is calculate $$$S_{i,0}$$$ and $$$S_{i,1}$$$.

Take venue A as an example. We may find that $$$S_{i,0}$$$ equals to the whole set $$$-$$$ the set of intervals that do not intersect with them. Suppose there is an interval $$$[a,b]$$$, then interval $$$[c,d]$$$ do not intersect with it if and only if $$$d<a$$$ or $$$c>b$$$. To calculate the first situation, we can sort the intervals by left bound non-decreasing order, add $$$2^{id_i}$$$ on position $$$y_i$$$ using BIT, where $$$id_i$$$ is the original index of the interval, and the set of the first situation equals to $$$sum(x_i-1)$$$. To calculate the second situation, we can sort the intervals by right bound non-increasing order, add $$$2^{id_i}$$$ on position $$$x_i$$$ using BIT, where $$$id_i$$$ is the original index of the interval, and the set of the first situation equals to $$$sum(1e9)-sum(y_i)$$$. Then we use $$$2^n-1$$$ minus the two sets and we can get $$$S_{i,0}$$$. As the bounds may be large, we need to discrete it.

Total time complexity: $$$O(nlogn)$$$.

Read more »

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