RabbitWorking

SRM 542 · 2011-11-22 · by lyrically

SRM 542 · 2011-11-22 · by lyrically · Graph Theory

Show categories

Class Name: RabbitWorking

Return Type: double

Method Name: getMaximum

Arg Types: (vector<string>)

Problem Statement

N rabbits (numbered 0 through N - 1) aim to work at the new TopCoder office in Rabbitland. You are to choose some of these applicants as employees.

Each pair of rabbits will make a certain profit when they work together. Given a group of rabbits, we can easily compute the total profit P as the sum of profits for each pair of rabbits in the group. However, hiring rabbits also brings some costs: they want to have a supply of fresh carrots. Surprisingly, the cost of supplying carrots to K rabbits is not linear in K. This cost is given by the formula C = (K * (200 - K)). The efficiency of a given group of rabbits is the real number (P / C), where P is their total profit and C is the cost of supplying carrots for them.

You are given a String[] profit, the j-th character of the i-th element of which represents the profit gained from rabbit i and rabbit j working together. The characters '0', '1', ..., '9' represent the values 0, 1, ..., 9, respectively. You may hire an arbitrary non-empty subset of the available rabbits. Return the maximum possible efficiency of the group of hired rabbits.

Notes

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

Constraints

profit will contain between 1 and 50 elements, inclusive.
Each element of profit will contain exactly N characters, where N is the number of elements in profit.
Each character in each element of profit will be a digit ('0' - '9').
For each index i and j, the i-th character of the j-th element of profit will be equal to the j-th character of the i-th element of profit.
For each index i, the i-th character of the i-th element of profit will be '0'.

Examples

{ "071", 
  "702", 
  "120" }
Returns: 0.017676767676767676

If you choose only one rabbit, then P = 0, K = 1 and the efficiency is 0. If you choose rabbit 0 and rabbit 1, then P = 7, K = 2 and the efficiency is 7/396. If you choose rabbit 0 and rabbit 2, then P = 1, K = 2 and the efficiency is 1/396. If you choose rabbit 1 and rabbit 2, then P = 2, K = 2 and the efficiency is 2/396. If you choose all three rabbits, then P = 10, K = 3 and the efficiency is 10/591. You should choose rabbit 0 and rabbit 1 to maximize the efficiency.

{ "061", 
  "602", 
  "120" }
Returns: 0.015228426395939087

You should choose all three rabbits here.

{ "0" }
Returns: 0.0

{ "013040", 
  "100010", 
  "300060", 
  "000008", 
  "416000", 
  "000800" }
Returns: 0.021996615905245348

{ "06390061", 
  "60960062", 
  "39090270", 
  "96900262", 
  "00000212", 
  "00222026", 
  "66761201", 
  "12022610" }
Returns: 0.06871794871794872

78)

{ "099900001", "909900000", "990900000", "999000000", "000009991", "000090990", "000099090", "000099900", "100010000" }
Returns: 0.0703125

kills greedy2

79)

{ "0090900", "0008080", "9000900", "0800083", "9090000", "0808000", "0003000" }
Returns: 0.04568527918781726

kills greedy1

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

Coding Area

Language: C++17 · define a public class RabbitWorking with a public method double getMaximum(vector<string> profit) · 114 test cases · 2 s / 256 MB per case