Thanks a ton. I found finite calculus very interesting and useful !
On Fri, Nov 6, 2009 at 11:35 AM, abhijith reddy abhijith200...@gmail.comwrote:
Thank you so much ! :)
On Fri, Nov 6, 2009 at 11:00 AM, Prunthaban Kanthakumar
pruntha...@gmail.com wrote:
On a related note,
The solution I
It is clearly O(n^2) . However i am sure there must be better methods
available then this semi-naive method. Once i saw a problem which was on 4
lists and not three like here. So same algorithm on that case delievers
O(n^3) and was giving me TLE. So yes , we should be able to do it nlogn
somehow.
This is a very common problem actually. And is most often solved using curve
fitting only. We choose the curve to be polynomial of minimum degree and
then use some interpolation method to get the exact polynomial.
You may like to see the same problem at spoj:
https://www.spoj.pl/problems/CMPLS/
Check google for Newton's interpolation method. That should help.
cheers
-
nikhil
On Fri, Oct 30, 2009 at 10:02 AM, Shiqing Shen ssq...@gmail.com wrote:
match the sequence exactly?
how to get that polynomial function, i am curious
2009/10/29, Vladimir Reshetnikov v.reshetni...@gmail.com:
for this .
On Mon, Oct 26, 2009 at 12:06 PM, nikhil garg nikhilgar...@gmail.comwrote:
We at any one step can measure only 3 quantities: A liters , B liters , or
(A-B) litres. ( assuming AB)
With every operation we have a cost associated: For A liter , we need 2
operations( Fill A , transfer from
probably the only entirey different approach ( except small variations in
Bsearch ) is use of Hashing ( or for that matter , HashMaps )
On Sun, Oct 25, 2009 at 1:36 PM, harit agarwal agarwalha...@gmail.comwrote:
the only other way can be the jump exponentially during search as in binary
search
We at any one step can measure only 3 quantities: A liters , B liters , or
(A-B) litres. ( assuming AB)
With every operation we have a cost associated: For A liter , we need 2
operations( Fill A , transfer from A to vessel) . For B liter , similarly we
need 2 operations And for (A-B) litres we
a very simple proof of the formula is using generating function for counting
On Sat, Oct 10, 2009 at 3:08 PM, Prunthaban Kanthakumar
pruntha...@gmail.com wrote:
I just noticed that in your problem the balls are 'similar'.
Then the solution is a simple composition and the answer is {n-1, k-1}
This is a simple dp problem .
define for each i following 2 quantities :
best1[i] : best sum in similar constraint of first i elements only when last
( ith ) term is always included
best2[i] : best sum in similar constraint of the first i elements only when
last (ith ) term is NOT included
so we
