11028 - Sum of Product

jan_holmes · Post by **jan_holmes** » Mon May 15, 2006 5:15 am

How to solve this problem ??? should we generate all permutation ???

or is there any faster method ???? Thx...

sohel · Post by **sohel** » Mon May 15, 2006 5:35 am

generation of all permutation will surely time out... n < 2^31

do you have to consider all the characters..
... or only half

hope it helps.

Darko · Post by **Darko** » Mon May 15, 2006 7:46 am

I think you two are talking about different problems?

sohel · Post by **sohel** » Mon May 15, 2006 3:21 pm

ooops...

i was talking about 11027 -- palindromic permutation.

But for 11028 --> no you don't have time to generate all the permutations.
One hint: Look at the AC times of everyone.. most 0.00 sec(and that's without precalculation)

Hope i am talking about the right problem this time...

ayon · Post by **ayon** » Mon May 15, 2006 10:29 pm

i think it's a very good idea to always mention the problem name with the problem number as the subject ("11028 - sum of product"). it helps people to quickly understand which problem is that, without seeing the problem set.

C · Post by C » Mon May 15, 2006 11:18 pm

Any hint about how to calculate? Is there a formula? I have tried to get a formula, but without success..

vinay · Post by **vinay** » Tue May 16, 2006 8:38 am

sohel wrote:ooops...

no you don't have time to generate all the permutations.
One hint: Look at the AC times of everyone.. most 0.00 sec(and that's without precalculation)

Hope i am talking about the right problem this time...

I have got accepted

I think people have solved in the same way I did

Find few of them and try (by any means programming or non-programming ) to get the others.. Yes, I mean any means

Hope didn't say too much nor too less

C · Post by C » Tue May 16, 2006 6:18 pm

vinay wrote:
sohel wrote:ooops...

no you don't have time to generate all the permutations.
One hint: Look at the AC times of everyone.. most 0.00 sec(and that's without precalculation)

Hope i am talking about the right problem this time...

I have got accepted
I think people have solved in the same way I did
Find few of them and try (by any means programming or non-programming ) to get the others.. Yes, I mean any means
Hope didn't say too much nor too less

Hi,vinay, u said too less

I still have no idea how to get others...Or can anyone give any more hints ?? Thanks in advance!

sohel · Post by **sohel** » Wed May 17, 2006 8:04 am

I think Vinay said enough...

I was looking for a closed form solution !!!

Then, the obvious question might arise: why is the input range <= 20 ?
It is some sort of trick or a deceiver, if you will. I tried to create some confusion, so that many will be tempted to think there is some sort of backtrack solution.

Normally, this sort of problems should not be set in real time programming contests, but since this was an online contest I thought otherwise. Everyone has access to resources that hunts for integer sequence. If this type of problems were set in icpc, i would have been the first one to make a complaint...

BTW: all of my above points are based on the fact that there is no backtrack solution( AFAIK ) , but if there is a bctr soln or the formula is derivable in real time contest.. then forget everything i said.

However, the prob itself is interesting enough, eventhough the soln isn't.

morpheous · Post by **morpheous** » Wed May 17, 2006 8:40 am

vinay wrote:
I have got accepted
I think people have solved in the same way I did
Find few of them and try (by any means programming or non-programming ) to get the others.. Yes, I mean any means
Hope didn't say too much nor too less

I dont think that non progrmming skills are needed here you just focus on the problem it's a little trickier but can be solved ( without googling).
Solved the problem and got AC in .002 sec

vinay · Post by **vinay** » Wed May 17, 2006 8:53 am

morpheous wrote: I dont think that non progrmming skills are needed here you just focus on the problem it's a little trickier but can be solved ( without googling).
Solved the problem and got AC in .002 sec

How do u know that i googled. I may have used yahoo or any other resource

vinay · Post by **vinay** » Wed May 17, 2006 8:56 am

I see that sohel has set the paper and has favored me. So there is no
problem with my solution. If there are other ways Morpheous may suggest
some other ways

Darko · Post by **Darko** » Wed May 17, 2006 7:27 pm

I think "google" is a verb in English now, meaning "search Internet", not necessarily using Google. It might even be in the Oxford dictionary by now (not sure).

And - given a sequence of integers, you can come up with polynomials that will produce them, but I never tried that approach.

The whole point is - people should be aware of the Online Encyclopedia of Integer Sequences, especially if that was the intended solution. There is a link to Dartboard Sequence there. Note that Brown said that at that time the sequence wasn't in the Encyclopedia. (I don't know how long ago "that time" was)

Just spread the word

Solaris · Post by **Solaris** » Wed Jun 14, 2006 4:25 pm

Hi .. I have wasted a whole today thinking about a traditional solution to this problem ... is GOOGLE the only solution to this problem ??? If anyone has solved it with some other way plz can u share your algo ??

And I completely agree with Darko .. GOOGLE is an english verb now (at least for us

)

lovemagic · Post by **lovemagic** » Fri Jun 23, 2006 6:30 am

while trying to formulate,i have got one,i dont know its right or wrong.fibonacci comes with every 2nd integer f the sequence.

for,
n=3 ans=1
n=4,ans=3
n=5,ans=8
n=6,ans=21

m i right here???

what's the ans for n=1 & n=2???
i think in both case the ans will be 1.

plz response...

OJ Board

11028 - Sum of Product

11028 - Sum of Product

um..

close form... :-)