## 11026 - A Grouping Problem

Moderator: Board moderators

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

### 11026 - A Grouping Problem

Can anyone describe the idea to solve this problem.

Ami ekhono shopno dekhi...
HomePage

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
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
Contact:
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
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
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 ?
Suhendry Effendy

ferng1021
New poster
Posts: 9
Joined: Thu Feb 23, 2006 5:09 pm
Location: Taipei, Taiwan
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
ups.. too late. someone has replied my question. yeah. it's a very stupid mistake I've just figured this out. How can ( 4! / 3! ) be 3...
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
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
I got WA in this problem

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:
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
``````

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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:
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.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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