Problem solving and Point in Plane.
Problem solving: Dilworth theorem and use bipartite matching. I have to use Hopcroft and Karp's O(n^2.5) algorithm as the graph is dense, and I need some early termination when doing BFS to set up layers. Anyway it is pretty fast after that implementation optimization. Knowing algorithm seems not enough.
Point in Plane: calculating the min number of turns is easy, but counting is a bit tricky. My first idea is to enumerate all bit masks but this will give 2^16*2^16 which is way to slow for even a single case, not to mention T=50 cases. Then it is simple to notice that each submask you remove must be collinear and you can order the sequence by the bit pattern you removed in each turn so that pt[0] always being the first point to remove. The advantage is that then you can simply multiply by factorial of number of opt move to get the count, because each op in a seq is different and between different seq they have at least one op different because the first op is different: pt[0] is with a different subset of points. One trick is to enumerate all subsets of a given bit pattern with a simple loop:
for(int i=b; i>0; i=(i-1)&b)
I know I have seen this somewhere before but have to google it to find from stackoverflow.com
Now I have only 3 unsolved, with xorkey passed 10/11 and TLE on the last.
The other two are:
lucky numbers, with 10^4 cases seems I need a better DP, or I can manipulate the 10^4 cases somehow.
count scoreboard, this one is tough, with only 8 people solved. The least solved problem so far.
Subscribe to:
Post Comments (Atom)
Hi,
ReplyDeleteI noticed you had Grid Walk solved. Can you please help me because I'm somewhat stuck. I realize that without constraints, i.e. infinite grid the sum of all the paths is (2*dimensions)^m, where m is the number of steps. I also realize how to use dynamic programming to generate the number of paths at a specific point, it is the sum of the surrounding 2n positions because that is the number of n-1 paths. However with 10 dimensions this doesn't quite yield itself to dynamic programming, unless I figure out how to subtract the part that would be there if the grid was infinite. Can you please clue me in on the point I'm missing, thanks?
Codeforces has a very similar problem and that inspired my solution. Basic approach is do a DP from dim=1, 2, ... N, and remember some state up to current dim. You also need some precalculation to speed up things, which is apparent once you have the DP figured out.
ReplyDelete