Foxlings

It's Christmas time in the forest, and both the fox and the wolf families are celebrating. The rather large fox family consists of two parents as well as N (1 ≤ N ≤ 1,000,000,000) little foxlings. The parents have decided to give their children a special treat this year - crackers! After all, it's a well-known fact that foxen love crackers.

With such a big family, the parents can't afford that many crackers. As such, they wish to minimize how many they give out, but still ensuring that each foxling gets at least a bit. The parents can only give out entire crackers, which can then be divided and passed around.

With this many children, not all of them know one another all that well. The foxlings have names, of course, but their parents are computer scientists, so they have also conveniently numbered them from 1 to N. There are M (1 ≤ M ≤ 100,000) unique two-way friendships among the foxlings, where relationship i is described by the distinct integers A_i and B_i (1 ≤ A_i, B_i ≤ N), indicating that foxling A_i is friends with foxling B_i, and vice versa. When a foxling is given a cracker, he can use his tail to precisely split it into as many pieces as he wants (the tails of foxen have many fascinating uses). He can then pass these pieces around to his friends, who can repeat this process themselves.

Line 1: Two integers - N and M
Next M lines: Two integers - A_i and B_i

Output

Sample Input

9 5
3 1
6 1
7 6
2 7
8 9

Sample Output

4

Explanation

The parents can give one cracker to foxling 6, who will then split it into three and give pieces to his friends (foxlings 1 and 7). Foxling 7 can then give half of his piece to his other friend, foxling 2.

They can give another cracker to foxling 8, who will split it with foxling 9.

This leaves foxlings 4 and 5, who have no friends (don't worry, foxen have long since outgrown the need for friends), and who must be given one cracker each. This brings the total up to 4 crackers.

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Mar 11, 2009
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Not that it really needs fixing, but for posterity:
Case #1 has m = 0
Cases #5 through #12 have A_i = B_i for some i
These violate the specification. See http://wcipeg.com/submissions/status/335913

[s]Is there anyway to speed up the compression of the nodes in my algorithm?
It seems that even compressing the nodes on the TLE cases causes it to TLE...[/s]

[s]Edit 1: Seems that quicksort times out on the 13th test case...
Darn worst case of O(n^2)[/s]

Edit 2: Heap sort seems to work... Thanks for the help!

Do a quick time analysis of your code.

1. Your get() code takes log(M) time for the binary search, and on average M/2 time for the insertion. (The binary search is kinda useless, since you insert anyway) Since you'll eventually run get() for every vertex, this takes about M*M/2 steps.

2. In the find procedure, you go through all the edges for every vertex - this takes about M*M steps.

Overall, you can see that it takes some multiple of M*M time.
Since M <= 100,000, this is far too slow. A modern computer will only run approximately 20-50 million operations per second.

To compress the nodes in a smarter way, try reading all the nodes in, and then sorting them with something like quick/merge sort. (which takes N*log(N) time on average). Then you can find the indices pretty easily, with a binary search.

In the find() loop, you can use something similar. Unfortunately, Pascal doesn't have any library functions for this sort of thing, so you'll have to do a lot of extra coding.

The new algorithm should take roughly M*log(M) time, which is ~2 million - more than fast enough to run in time.

Think of this as an undirected graph - the foxlings are nodes, and the friendships are edges. This problem is just asking for the number of separate "connected component" (a component is a group of nodes that can all be reached from one another). This can be done with floodfill in linear time.

However, N is far too large for this to run in time. The key observation is that with M edges, only up to 2M nodes can be connected to others, leaving many nodes with no neighbours (hence forming their own connect components).

shouldn't the output for the sample input be three? because u give one cracker to 6 which will be divided among 6,1,7,3,2. that leaves 4,5,8,9. you give one to 5 and that cracker will be divided among 5,8,9 and you give one more cracker to the friendless 4. so you have 3 crackers...or am i reading this problem wrong?

Foxling 5 has no friends, so if you give a cracker to him, why would it be divided among 5,8,9???

Keep in mind that the first line of input is NOT a friendship, it's N and M.

oh crap! i forgot about that. k that makes sense...thanks!