10694 - Combinatorial Summation

[Larry]

I didn't write the program yet, but I figured out the pattern. I think it's fascinating how and where fibonacci numbers keep popping up.. (and I guess noteworthy to remark!)

[Larry]

I've found that there are negative inputs (thanks, Manzoor!), is the answer just 0? I get WA.. grr.

for 1000, I get:

288924218456143360241882819981631900915673130543819759032778173440536722190488904520034507723846345056055096007885942673814977857042829762586259661446114504634668393210192357419233828310479227982326069668667250

Can someone check this, thanks.

[abishek]

29792421850814336033688281998163190091567313054381975903277817344053672219048890 45200345081638463455390550965338859432428149784690428304175862603594461152456346 68393210192357419233828310479227982326069668667250


my AC program gives this

[abishek]

and it is clearly given in the input that there will be an INTEGER (<999)
and so negative inputs are no suprise and I print a 0 as an answer for anything <1
so obviously there are zeros as well

the thanks to shariar manzoor is there in the problem statement itself.
really a nice question indeed
i liked it very much


bye
abi

[Larry]

Thanks, I corrected my error and got AC.

[abishek]

congrats

[shahriar_manzoor]

If the problem is nice all credits go to Mohammad Sajjad Hossain the problemsetter

[abishek]

and the negative inputs were your idea is it?

[shahriar_manzoor]

and the negative inputs were your idea is it?

NO! I am not the only bad person in this world. If u recall you will see than in the a^n+b^n=0 problem the alternate solution was written by "Md Sajjad Hossain" this very problem setter. And he had no objection . So there are many people who like to give negative inputs...

[little joey]

Must be a Bengal thing, then

BTW
Meeting so many fine programmers from Bangladesh via the internet, makes you realise how small the distances between the different countries in the world have become in the recent deciennia.

Reading in the news about the terrible floodings that are going on in that country (and neighboring countries), and the many people dying in need of fresh drinking water and food, makes you realise how big the differences in the world still are...

[Maniac]

I must be missing something completely here, but could someone please help me out figuring out why the output for n=3 is 7?

- k C j in the picture means 'k choose j' as in k!/(j! (k-j)!) right?
- does 'sum k=n to minus infinity' mean: sum over k=n, k=n-1, k=n-2, etc..?

Cause if this is true then I don't see why the output of n=3 is finite: the terms coming from i=3, i=4, i=5, etc. all have the same positive contribution...

Any help would be welcome!

[Larry]

You should count any term as zero which has k < j.

[Krzysztof Duleba]

The way the first sum is written is misleading - usually it would mean all combinations of i and k such that 1 <= i <= oo, n >= k >= -oo. But here both variables are changing in the same time. In each iteration, i increases, but k decreases.

The sum looks like:
C(3,1) - first iteration
C(2,1) + C(2, 2) - second
C(1,1) - third
Since then, C = 0, and the final value is 3 + 2 + 1 + 1 = 7.

[Maniac]

ahhhh!!! OK, thanks, now I can start working on the problem.

That first sum is indeed misleading! I'm surprised to see so many people figured it out anyway...

[Maniac]

got AC now
By the way, with this kind of problems I must say that integer-sequence-lookups on the internet are very tempting...