tzc_wk's blog

By tzc_wk, 2 weeks ago, In English

You may see that in Codeforces Round #668 (Div. 1) and Codeforces Round #666 (Div. 1) and Codeforces Round #659 (Div. 1). Problem B are all game theory/conclusion problems. It seems that putting a conclusion problem on problem B has become a new trend.

Personally, I don't think it's very suitable that so many Div.1s have a game theory on B. Problems like this require thinking but is relatively much easier to write, sometimes 2~3 for's and if's may solve the problem, which makes no or little improvement to your abilities of writing programs. You can see that in large scale contests like CEOI or APIO or USACO, problemsetters tend to set problems that require both thinking and writing.

Make no offense, but I'd like to know what do those problemsetters think about it.

Read more »

 
 
 
 
  • Vote: I like it
  • -17
  • Vote: I do not like it

By tzc_wk, history, 7 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, 9 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