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.

# | User | Rating |
---|---|---|

1 | tourist | 3735 |

2 | MiFaFaOvO | 3681 |

3 | Um_nik | 3553 |

4 | Benq | 3376 |

5 | ecnerwala | 3295 |

6 | maroonrk | 3229 |

7 | TLE | 3223 |

8 | Radewoosh | 3216 |

9 | scott_wu | 3209 |

10 | Petr | 3205 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 200 |

2 | antontrygubO_o | 191 |

3 | pikmike | 188 |

4 | Monogon | 184 |

5 | vovuh | 182 |

5 | Ashishgup | 182 |

7 | Um_nik | 179 |

8 | Radewoosh | 173 |

9 | SecondThread | 172 |

10 | McDic | 161 |

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)$$$.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/05/2020 08:35:44 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|