11026 - A Grouping Problem

[Jan]

Can anyone describe the idea to solve this problem.

Thanks in advance.

[mf]

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]

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

if there are 4 elements

[Jan]

Thanks Timo and mf for your beautiful explanations.

I have got the idea.

Thanks again.

[trulo17]

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]

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 ?

[ferng1021]

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]

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

[rajkon]

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]

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]

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]

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]

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]

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.

[sclo]

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