And while everyone is relaxing after TopCoder, I would like to remind that today at 21:00 UTC the Round 2 of Facebook Hacker Cup 2014 is taking place. It will run for 3 hours. Top 100 advance to Round 3 and get a T-shirt.

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

1 | tourist | 3751 |

2 | Benq | 3727 |

3 | cnnfls_csy | 3691 |

4 | Radewoosh | 3651 |

5 | jiangly | 3632 |

6 | orzdevinwang | 3559 |

7 | -0.5 | 3545 |

8 | inaFSTream | 3478 |

9 | fantasy | 3468 |

10 | Rebelz | 3415 |

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

1 | adamant | 178 |

2 | awoo | 167 |

3 | BledDest | 165 |

4 | Um_nik | 164 |

5 | maroonrk | 163 |

6 | SecondThread | 160 |

7 | nor | 158 |

8 | -is-this-fft- | 154 |

9 | kostka | 146 |

10 | TheScrasse | 144 |

And while everyone is relaxing after TopCoder, I would like to remind that today at 21:00 UTC the Round 2 of Facebook Hacker Cup 2014 is taking place. It will run for 3 hours. Top 100 advance to Round 3 and get a T-shirt.

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/29/2023 01:01:01 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

The contest will be available here.

All those who could not qualify for this round (like me)can view leader board here !

My thoughts about the problems:

WAT? 3 times combinatorics? It's too narrow, even if all 3 problems could be solved in different ways...

Hm, the results are out. WAT? again, I flew up 100 places and got to round 3... submitting 5 minutes before the end, like a boss :D

Problem 1 was suitably easy, just two pointers using set<>s to store the sets of colours was sufficient.

Problem 3 was also suitably hard, requiring the right idea, and an efficient, although not difficult, implementation.

I managed to finalize this idea about 30 minutes before the end: Every vertex

igives us the number of waysP_{i}to choose slopes leading to it directly, and it's only dependent on the firstinumbers of the input (denote those asA_{i}). To find it, we construct a tree where vertexjis the son of vertexA_{j}. If we add a direct slope fromj<itoi, every path containing that slope will be passing through every vertex on the path from the root (vertex 0) toj, and there will be some path not passing through any vertex not on that path and <i, soA_{i}must be on that path, or equivalently, we can only add direct slopes toifrom children ofA_{i}in that tree. By the same idea, we find out that those direct slopes can't all be from the subtree of one of the sons ofA_{i}; if those sons have subtree sizesS_{1..k}, then . All that's left is constructing the tree, counting by one DFS and countingP_{i}, all inO(N), giving usO(N^{2}) total complexity. I wonder if it could be solved more efficiently...I didn't like problem 2, though. I couldn't escape a lot of casework by inclusion/exclusion... is there any nice way to solve it?

Problem 3 is solvable in

O(Nlog^{2}N) time(UPD: WRONG). All that we need is to keep track of sizes of subtrees. Let build an heavy light decomposition on the whole tree (with allNvertices). Then after processing vertexi, we will add it to the tree. Adding vertex is equivalent to increasing by one all sizes on the path from the root to this vertex.Of course, for this problem it is an overkill and during the competition I've implemented

O(N^{2}) one :)In the worst case you need to get sizes of subtrees

O(N^{2}) times (for example whenA_{i}= 0 for alli).O(N^{5}) brute force worked in Problem 2...Ok, you are right. But, if I'm not wrong again (at least now is not 3 AM), there is an solution.

Let construct the whole tree and divide there all vertices into two sets:

bigandsmallvertices.Bigvertices will be all vertices with size of subtree (in the whole tree) greater than ,smallwill be all other vertices. Also, like in the first (slow) solution, let build an heavy light decomposition on the whole tree.Now, we will again add to the tree vertices one by one, but we will keep track of two values:

S_{V}— size of subtree in current tree and , whereUis looping through allsmallsons of vertexV.Now, how we will add a vertex: I can't explain it clearly in words, so the pseudocode:

I hope it's clear, that while loop will iterate at most times per vertex, so adding one vertex takes time.

Now, how to calculate

P_{V}(from Xellos comment):, where

Uis looping through allbigsons of vertexV. This step takes time, because each vertex has at mostbigsons.So, the overall complexity of this solution is .

You can solve Problem 2 with dynamic programming in

O(n). You can count the remaining three pairs from those with higher maximum numbers towards lower. Let's say that pair (x,y),x<ywill be the largest. If you fixy, you can choosexfrom somewhere in the range 1..x'. When you'll have to choose the next pair (a,b), b<y, you know that the range of possible values forawill be 1..a',x' ≤a'. Therefore, it doesn't matter whichxwas chosen in the previous step, only how many pairs were chosen before.In fact you're solving a generalized problem

f(k,n) of choosingkpairs from numbers 1..nsuch that their sum is at mostc_{1}+c_{2}. Time complexity is justO(kn). You either usenas a part of the largest pair or not. There are a couple of things to consider, like how to handle used valuesc_{1},c_{2}and make sure thatx<y, but it can be done.Pretty nice approach,thanks for sharing