Connection Status:
Competition Arena > LollipopHoney

LollipopHoney

TCO19 SRM 758 · 2019-05-09 · by IH19980412

TCO19 SRM 758 · 2019-05-09 · by IH19980412 · Dynamic Programming
Class Name: LollipopHoney
Return Type: int[]
Method Name: count
Arg Types: (int, vector<int>, vector<int>)
Problem Statement

Problem Statement

Yui loves lollipops. She has a precious collection of tasty lollipops.

Each lollipop has some flavor and some level of deliciousness. Both parameters are represented by positive integers.

You are given the information about Yui's collection in the int[]s flavor and deliciousness. For each i, flavor[i] and deliciousness[i] represent one lollipop in the collection.

Yui wants to give 2K lollipops to her best friend as a birthday present. She wants to satisfy the following conditions:

  • It must be possible to split the lollipops into K pairs such that within each pair the two lollipops have different flavors.
  • The total deliciousness of all 2K selected lollipops must be maximized.

If Yui cannot select K pairs of lollipops meeting the conditions, return an empty int[]. Otherwise, return a int[] with two elements: Element 0 should be the largest possible total deliciousness of selected lollipops, and element 1 should be the number of ways in which the set of 2K lollipops can be selected, modulo 1,000,000,007.

Notes

  • Two ways of selecting lollipops differ if and only if there exists a lollipop which is selected in one way and not in the other way.

Constraints

  • N will be between 2 and 50, inclusive.
  • K will be between 1 and N/2, inclusive.
  • flavor will contain exactly N elements.
  • deliciousness will contain exactly N elements.
  • Each element in flavor will be between 1 and 50, inclusive.
  • Each element in deliciousness will be between 1 and 10^7, inclusive.
Examples
0)
1
{1,1,2,2}
{10,20,30,40}
Returns: {60, 1 }

Yui must select lollipop 1 (flavor 1, deliciousness 20) and lollipop 3 (flavor 2, deliciousness 40). The total deliciousness is 20+40 = 60, and this solution is unique.

1)
2
{1,1,1,2,2,2}
{10,10,10,20,20,20}
Returns: {60, 9 }

Yui must select two of the three lollipops with flavor 1 and two of the three lollipops with flavor 2. Note that she cannot select three lollipops with flavor 2 and one element with flavor 1: the total deliciousness would be higher, but she would not be able to create two pairs of lollipops such that within each pair the flavors are distinct.

2)
2
{1,1,1,1,1,2}
{10,20,30,40,50,60}
Returns: { }

Here, Yui is unable to select 2K lollipops with the desired properties.

3)
3
{48,33,22,9,37,44,5,49,24,14,45,1}
{9,1,7,10,7,10,5,1,3,3,4,5}
Returns: {48, 2 }
4)
10
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: {20, 846527861 }

Please don't forget to use modulo 1,000,000,007 when computing the number of ways.

Submissions are judged against all 53 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LollipopHoney with a public method vector<int> count(int K, vector<int> flavor, vector<int> deliciousness) · 53 test cases · 2 s / 256 MB per case

Submitting as anonymous