11028 - Sum of Product

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

11028 - Sum of Product

Post by jan_holmes »

How to solve this problem ??? should we generate all permutation ??? :oops: or is there any faster method ???? Thx...

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

um..

Post by sohel »

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

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

hope it helps.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

I think you two are talking about different problems?

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel »

ooops... :oops:

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... :D

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon »

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.
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm

Post by C »

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

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay »

sohel wrote:ooops... :oops:

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... :D

I have got accepted :lol:
I think people have solved in the same way I did :wink:
Find few of them and try (by any means programming or non-programming ) to get the others.. Yes, I mean any means :wink:
Hope didn't say too much nor too less :lol:
If I will myself do hashing, then who will do coding !!!

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm

Post by C »

vinay wrote:
sohel wrote:ooops... :oops:

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... :D

I have got accepted :lol:
I think people have solved in the same way I did :wink:
Find few of them and try (by any means programming or non-programming ) to get the others.. Yes, I mean any means :wink:
Hope didn't say too much nor too less :lol:
Hi,vinay, u said too less :evil: :P
I still have no idea how to get others...Or can anyone give any more hints ?? Thanks in advance!

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

close form... :-)

Post by sohel »

I think Vinay said enough... :D

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. :wink:

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... :D

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. :wink:

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

morpheous
New poster
Posts: 1
Joined: Wed May 17, 2006 8:32 am

Post by morpheous »

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 :D
Efficiency is more important than just solving the problem.

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay »

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 :D
How do u know that i googled. I may have used yahoo or any other resource
If I will myself do hashing, then who will do coding !!!

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay »

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 :wink:
If I will myself do hashing, then who will do coding !!!

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

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
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris »

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 :wink:)
Where's the "Any" key?

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

Post by lovemagic »

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...
khobaib

Post Reply

Return to “Volume 110 (11000-11099)”