Connection Status:
Competition Arena > GerrymanderEasy

GerrymanderEasy

SRM 690 · 2016-05-02 · by tozangezan

SRM 690 · 2016-05-02 · by tozangezan · Brute Force, Simple Math
Class Name: GerrymanderEasy
Return Type: double
Method Name: getmax
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

Problem Statement

Cucumber Boy is trying to be elected to the city council. In order to achieve that, he needs to show that he has a lot of support in some part of the city.

The city is divided into N districts. These are numbered from 0 to N-1. For each i, there are A[i] voters in district i, and out of them B[i] support Cucumber Boy.

Cucumber Boy must choose a part of the city: K or more districts with consecutive numbers. Cucumber Boy wants to maximize the proportion of votes in his favor. Formally, Cucumber Boy wants to maximize the value X/Y, where Y is the total number of voters in the chosen districts and X is the number of Cucumber Boy's supporters among them.

You are given the int[]s A and B with N elements each. You are also given the int K. Compute and return a real number: the largest value X/Y that can be achieved.

Notes

  • The returned value must have an absolute or relative error less than 1e-9.

Constraints

  • A will contain between 1 and 1,000 elements, inclusive.
  • A and B will contain the same number of elements.
  • For each i, A[i] will be between 1 and 10,000, inclusive.
  • For each i, B[i] will be between 0 and A[i], inclusive.
  • K will be between 1 and the number of elements in A, inclusive.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{5,1,2,7}
{4,0,2,2}
2
Returns: 0.75

The optimal solution is to choose districts 0, 1, and 2. The total number of voters will be Y = 5+1+2 = 8. The total number of Cucumber Boy's supporters will be X = 4+0+2 = 6. Hence, the proportion of votes in Cucumber Boy's favor is X/Y = 0.75. Note that the chosen districts must have consecutive numbers. We are not allowed to choose only districts 0 and 2.

1)
{12,34,56,78,90}
{1,1,1,1,1}
1
Returns: 0.08333333333333333
2)
{10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}
{3,1,4,1,5,9,2,6,5,3}
5
Returns: 5.4E-4
3)
{123,4,46,88,22,34,564,87,56,311,886}
{0,0,0,0,0,0,0,0,0,0,0}
1
Returns: 0.0

Sometimes the answer will be 0.

4)
{1}
{1}
1
Returns: 1.0

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

Coding Area

Language: C++17 · define a public class GerrymanderEasy with a public method double getmax(vector<int> A, vector<int> B, int K) · 105 test cases · 2 s / 256 MB per case

Submitting as anonymous