11174 - Stand in a Line

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

11174 - Stand in a Line

Post by Hadi » Sun Feb 18, 2007 3:29 pm

I could not get Accepted for this problem during contest time, but after contest, after some changes in my code, I could get Accepted for this problem in 9.8 secs! which is too much.

My solution is like this:

Code: Select all

P = population
Q = Sum of populations
C = child[root][child_index]

Solve(root, child_index, x = Q[0..child_index-1]) = Solve(root, child_index+1, x + P[C]) * Solve(C, 0, 0) * Choose(P[C], P[root] - x - 1)
Is there some better way? or you implemented Choose function nicely (which is the main overload of my approach ? :( )

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:

Post by Erik » Sun Feb 18, 2007 3:51 pm

Hi,

I don't actually understand what your code means.
But I can tell you I broke the problem down to a simple mathematical equation. The challenge then is evaluating it fast (it includes a factorial).

My final (for now) solution is in O(n) for each test case, but it requires some calculations involving prime numbers in advance. Anyway, reading the input is the bottleneck.

Cu, Erik :)

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi » Sun Feb 18, 2007 4:05 pm

Here is some explanation about my approach:
First, I make a tree in which there is an edge a->b if a is father of b. There are some nodes that don't have father, so I add a super node which is the father of all father-less nodes.

When I want to find the answer for a tree which has A as root, The answer is:
solve(child1) * solve(child2) * solve(child3) * ... * solve(childn) * n! / (count[child1]! * count[child2]! * count[child3]! ... * count[childn]!)

The Solve function I described in the post above is some modified form of this solve function, which does the same operations.

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:

Post by Erik » Sun Feb 18, 2007 4:18 pm

Hi,

I had the exactly same idea.
Now you just have to think about what happens if you evaluate the recursive calls to solve!

Cu, Erik :)

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi » Sun Feb 18, 2007 4:54 pm

Thanks for your nice hint :wink: I got it

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » Sun Feb 18, 2007 6:41 pm

During the contest, I missed that nice observation at which Erik hinted above, but I got accepted by implementing the choose function nicely. You can do this as follows:

* Calculate all primes.
* Make a function f(n,p) that calculates how many times a prime p will appear in n!
* To get choose(n,x_1,x_2,...,x_k) loop over each prime. A prime will appear exactly f(n,p)-sum(f(x_i,p),i=1..k) times in choose(n,x_1,x_2,...,x_k).

What I did during the contest was a little bit different, but also worked:
* If k>2, define a=sum(x_i,i=1..k/2) and b=sum(x_i,i=k/2+1..k), then choose(n,x_1,x_2,...,x_k)=choose(n,a,b)*choose(a,x_1,...x_(k/2))*choose(b,x_(k/2+1),...x_k)

The following was my first attempt, but timed out:
* If k>2, then choose(n,x_1,x_2,...,x_k)=choose(n,x_1,n-x_1)*choose(n-x_1,x_2,....x_k)

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Feb 18, 2007 6:53 pm

krijger wrote:The following was my first attempt, but timed out:
* If k>2, then choose(n,x_1,x_2,...,x_k)=choose(n,x_1,n-x_1)*choose(n-x_1,x_2,....x_k)
That's what I used.

I have additionally precomputed a table with factorials and their inverses modulo 1000000007 (which is a prime), so computing choose(n, x_1, n-x_1) in my solution needed just a few multiplications and divisions.

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » Sun Feb 18, 2007 8:04 pm

Ah, I should've noticed that it was a prime. It would've been a lot easier :) I used the 'looping over all primes'-thing I described above.

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

How to

Post by rushel » Tue Feb 20, 2007 6:42 am

Guys, how to use multiplication inverse in this problem. Can u describe the algorithm.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Tue Feb 20, 2007 7:06 am

You can use the extended euclidean algorithm to find the inverse.
If you figured out the formulas, you will notice that you need to do division, so instead of doing the divisions, you can multiply by the inverse.

Post Reply

Return to “Volume 111 (11100-11199)”