[Solution] Image Labele solution kickstart

Image Labele solution kickstart – Crowdsource is organizing a campaign for Image Labeler task with participants across NN regions. The number of participants from each of these regions are represented by A1,A2,,ANA1,A2,…,AN.

Table of Contents

[Solution] Image Labele solution kickstart

In the Image Labeler task, there are MM categories. Crowdsource assigns participants to these categories in such a way that all participants from a region are assigned to the same category, and each category has at least one region assigned to it. The success metric of the campaign is measured by the sum of medians of the number of participants in each category. (Let us remind you here that the median of a list of integers is the “middle” number when those numbers are sorted from smallest to largest. When the number of integers in a list is even, we have two “middle” numbers, therefore the median is defined as the arithmetic mean (average) of the two middle values.)

For example, imagine that we have N=3N=3 regions with A1=5A1=5A2=8A2=8, and A3=9A3=9 participants respectively and we want to assign them to M=2M=2 categories. If we assign regions 22 and 33 to category 11 and region 11 to category 22, then the success metric would be median of {A2=8,A3=9} +{A2=8,A3=9} + median of {A1=5}=8+92+5=8.5+5=13.5{A1=5}=8+92+5=8.5+5=13.5. We can also assign regions 11 and 22 to category 11 and region 33 to category 22. Then the success metric would be equal to the sum of the median of {A1=5,A2=8}{A1=5,A2=8} and the median of {A3=9}{A3=9}, which is 5+82+9=6.5+9=15.55+82+9=6.5+9=15.5.

Your task is to find the maximum possible value of the success metric that can be obtained by assigning participants in regions to the categories.

[Solution] Image Labele solution kickstart

The first line of the input gives the number of test cases, TTTT test cases follow.
The first line of each test case contains two integers NN and MM: the number of regions, and the number of categories respectively.
The next line contains NN integers A1,A2,,ANA1,A2,…,AN.

Output

For each test case, output one line containing Case #xxyy, where xx is the test case number (starting from 1) and yy is the maximum possible value of the success metric.

yy will be considered correct if it is within an absolute or relative error of 10610−6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

 

Limits

Memory limit: 1 GB.
1T1001≤T≤100.
1N1041≤N≤104.
1M1041≤M≤104.
1MN1≤M≤N.
1Ai1051≤Ai≤105, for all ii.

Test Set 1

Time limit: 20 seconds.
0NM10≤N−M≤1.

Test Set 2

Time limit: 40 seconds.
No additional constraints.

[Solution] Image Labele solution kickstart

Note: there are additional samples that are not run on submissions down below.

Sample Input
content_copy
1
3 2
11 24 10
Sample Output
content_copy
Case #1: 34.5

In this test, we can assign participants in regions to categories in 66 possible ways:

    • Assign {11,24}{11,24} to category 11 and {10}{10} to category 22, in which case the success metric is 11+242+10=17.5+10=27.511+242+10=17.5+10=27.5.
    • Assign {24,10}{24,10} to category 11 and {11}{11} to category 22, in which case the success metric is 24+102+11=17+11=2824+102+11=17+11=28.
    • Assign {11,10}{11,10} to category 11 and {24}{24} to category 22, in which case the success metric is 11+102+24=10.5+24=34.511+102+24=10.5+24=34.5.
    • 33 other ways, where assignments to category 11 and 22 are swapped, which does not alter the value of success metric.

So, the maximum possible value of the success metric is 34.534.5.

 

 

[Solution] Image Labele solution kickstart

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.

Sample Input
content_copy
1
5 1
6 2 5 1 9
Sample Output
content_copy
Case #1: 5.0

In this test, there is only one category, so participants in all regions will be assigned to it. The only possible value of the success metric is the median of {6,2,5,1,9}{6,2,5,1,9} which is 55.

For Solution

Click Here

Leave a Comment