11379 - Chichi's Home Work

[baodog]

Nevermind,... I got it...

[Robert Gerbicz]

How is it solvable? I know only that the total number of ways to place n circles (without x,y restrictions) is the n-th Catalan number. I've tried recursion, but it wasn't worked.

[rio]

Heres some hint how I solved.

Code: Select all

c(n) := total numbers of ways to place n circles (Catalan number)
f(n, k) := total numbers of ways to place n circles with k'th circle does not include any other circles.

For example, f(3,2) is 3.

Code: Select all

()()(), (())(), (()())

Using c(n) and f(n,k), you could get the answer with O(n).
-----
Rio

[sonyckson]

Hello, any hints for calculating f(n,k) in less than n^3 ( using dp )?? Thanks, Eric.

[baodog]

With precomputation f can be computed in O(n^2) dp, which
may or may not be fast enough

[rio]

I calculated f(n,k) with O(n^2) DP using c(n).

PS: Be careful that the correct output for the sample input will be:

Code: Select all

57
774474320

Written in "Real Time Clarification".
-----
Rio

[suhendry]

Arggh! so there's a clarification They haven't fixed the sample output for this problem yet.

Thanks Rio.

[tobby]

Can anyone share some hint how to compute f(n,k) in O(n^2)? Mine is too slow. O(n^3).

[sonyckson]

Suppose that g(n, k) is the number of ways of placing n circles with the k-th including at least one circle .
Now, f(n, k) = c(n)-g(n,k);........ think about g . gl! Eric.

[tobby]

Your hint is great! After reading your hint I rewrite my code in 10 minutes and get AC. How do you get this awesome idea?

Instead of bottom-up dp, my code uses top-down memoization. Would precomputing f(n, k) using dp be faster?

[sonyckson]

In my case it took me some hours... and the hint above that f(n,k) could be computed in O ( n^2 )... is a good hint to start thinking... because it gives some information about how f(n,k) may be defined . gl! Eric.

[baodog]

I can get f(n,k), but not the rest from it. It gets complicated when circles at the ends of the interval [X,Y] intersect with ones before it, or after it. I can not get the right answer using inclusion exclusion principle.

[sonyckson]

It gets complicated when circles at the ends of the interval [X,Y] intersect with ones before it, or after it.

I dont understand, what do you mean by that? ( circles should not intersect... could you give like an example?) gl! Eric.