11026 - A Grouping Problem

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

11026 - A Grouping Problem

Post by Jan » Sat Apr 01, 2006 9:37 pm

Can anyone describe the idea to solve this problem.

Thanks in advance.
Ami ekhono shopno dekhi...
HomePage

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Apr 01, 2006 9:44 pm

I've used O(n^2) dynamic programming. The recurrence is very similar to binomial's formula.

(spoiler:)
If C[m][k] denotes the sum of products of elements of all subsets of size k chosen from first m elements,
then we have: C[m][k] = C[m-1][k] + C[m-1][k-1] * A[m], (where A[m] is m-th number in input.)

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo » Sat Apr 01, 2006 9:50 pm

Hi Jan, this problem can be solved using Dynamic Programming.

if there are 4 elements
"Life is more beautiful with algorithm"

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Apr 01, 2006 9:56 pm

Thanks Timo and mf for your beautiful explanations.

I have got the idea.

Thanks again.
Ami ekhono shopno dekhi...
HomePage

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

Post by trulo17 » Sun Apr 02, 2006 12:53 am

I don't know if what i did is the same that you're talking.
Let a=1, b=2, c=3
(x-1)*(x-2)*(x-3) = x^3-6x^2+11x-6
a + b + c =6
ab+ac+bc= 11
abc=6
so we can multiply (x-x1)*(x-x2).....(x-xn) store the coeficients in an array and look for the coeficient with highest value mod m
it got ac in 1.2 seconds during contest
Time complexity O(n^2)
Space Complexity O(n)

suhendry
New poster
Posts: 14
Joined: Sat Aug 31, 2002 6:55 am

Post by suhendry » Sun Apr 02, 2006 6:09 am

I don't understand this problem at all..

I think this problem wants us to compute max-fitness from all K-combination out of N elements ( 1 <= K <= N ), but I don't see any relation between this idea and the problem's Sample I/O.

eg. on 2nd sample i/o :

4 100
1 2 3 4

if K = 0 --> 0...
if K = 1 --> 1 + 2 + 3 + 4 --> 10
if K = 2 --> 1.2 + 1.3 + 1.4 + 2.3 + 2.4 + 3.4 -- > 35
if K = 3 --> 1.2.3 + 1.2.4 + 2.3.4 --> 38
if K = 4 --> 1.2.3.4 --> 24
if K > 4 --> don't tell me this one is possibe..

how can the maximum fitness be 50 ? :o
Suhendry Effendy

ferng1021
New poster
Posts: 9
Joined: Thu Feb 23, 2006 5:09 pm
Location: Taipei, Taiwan

Post by ferng1021 » Sun Apr 02, 2006 6:28 am

if K = 3 --> 1.2.3 + 1.2.4 + 2.3.4 --> 38
actually, 1.2.3 + 1.2.4 + 1.3.4 + 2.3.4 = 50

you have missed 1.3.4

suhendry
New poster
Posts: 14
Joined: Sat Aug 31, 2002 6:55 am

Post by suhendry » Sun Apr 02, 2006 7:05 am

ups.. too late. someone has replied my question. yeah. it's a very stupid mistake :oops: I've just figured this out. How can ( 4! / 3! ) be 3... :lol:
shouldn't fall into this again..

btw, my friend also participate in this contest and i asked the same question to him. but he also forgot 1.3.4 :) how can both of us fell into the same mistake..

anyway, thanks ferng1021. it's time to code..
Suhendry Effendy

rajkon
New poster
Posts: 5
Joined: Sun Apr 02, 2006 11:59 am

Post by rajkon » Sun Apr 02, 2006 12:00 pm

Would it be ok if I post my code here, becouse I'm getting WA, and I don't know what can be the reason :(

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Mon Apr 03, 2006 2:14 pm

I got WA in this problem

How about the output of
4 20
1 1 2 3
3 2
2 4 6
My output is 17 and 0, did they wrong?
By the way,can someone give me some strick inputs? Thanks

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Apr 03, 2006 3:05 pm

My accepted program prints 1 for your second test case.

Here are some tests:

Code: Select all

10 2147483647
1000 999 998 997 996 995 994 993 992 991
10 2147483647
997 997 997 997 997 997 997 997 997 997
13 2147483647
997 991 983 977 971 967 953 947 941 937 929 919 911
2 1
1 1
0 0

Code: Select all

2111939040
1668905003
1828513970
0

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

Post by sohel » Mon Apr 03, 2006 4:09 pm

mf wrote: My accepted program prints 1 for your second test case.
My AC code produces 0 for Wei-Ming Chen's second case.
{2 4 6}, should produce an even fitness for any combination.

And any even number mod 2 should produce 0.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Apr 03, 2006 4:19 pm

Why are you so sure that the output should be 0?
The problem statement IMHO doesn't say that I can't take K=0. For K=0, the complete grouping system consists of an empty set, product of whose elements is usually defined as 1.

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

Post by sohel » Tue Apr 04, 2006 8:56 am

Luckily there was no similar case in the judge data.
Even though (K=0) isn't mentioned in the problem statement, but one gets the feeling that it shouldn't be considered, just by reading the problem statement.

But this is of course my opinion.
Last edited by sohel on Tue May 30, 2006 11:07 am, edited 1 time in total.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Tue Apr 04, 2006 11:18 am

Assuming that when k=0, the sum of product = 1 is natural and makes it easier to code.

Post Reply

Return to “Volume 110 (11000-11099)”