OJ Board

Nevermind,... I got it...

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.

Heres some hint how I solved. For example, f(3,2) is 3. Using c(n) and f(n,k), you could get the answer with O(n).
-----
Rio

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

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

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: Written in "Real Time Clarification".
-----
Rio

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

Thanks Rio.

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

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.

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?

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.

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.

baodog wrote: 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.