Connection Status:
Competition Arena > Subsets

Subsets

SRM 622 · 2013-12-22 · by ltaravilse

SRM 622 · 2013-12-22 · by ltaravilse · Simple Math
Class Name: Subsets
Return Type: int
Method Name: findSubset
Arg Types: (vector<int>)
Problem Statement

Problem Statement

You have a bag with some balls. There is a positive integer written on each of the balls. Balls with the same integer are identical.

A bag with balls is nice if the sum of numbers on all balls is strictly greater than the product of those numbers. For example, if the numbers on balls are {1,1,2,3}, the bag is nice because 1+1+2+3 > 1*1*2*3.

You are given a int[] numbers. Each element of numbers is a number written on one of the balls in your bag. You are going to remove some (possibly none, but not all) balls from the bag. After you do so, the bag must be nice.

Return the number of different nice bags you can obtain.

Notes

  • You may assume that the return value always fits into a signed 32-bit integer variable.

Constraints

  • numbers will contain between 1 and 1000 elements, inclusive.
  • Each element of numbers will be between 1 and 1000, inclusive.
Examples
0)
{1,1,1}
Returns: 2

The bag contains three identical balls, each with the number 1. We can produce a nice bag in two ways: Keep all three balls. The bag is nice because 1+1+1 > 1*1*1. Throw away one ball. The bag is nice because 1+1 > 1*1.

1)
{1,1,1,1,2,2,2,2}
Returns: 13

Our bag contains 8 balls: four with a 1 and four with a 2. All possible nice bags that can be produced by removing some of these balls are listed below, one per row. 1,1 1,1,1 1,1,1,1 1,2 1,1,2 1,1,1,2 1,1,1,1,2 1,2,2 1,1,2,2 1,1,1,2,2 1,1,1,1,2,2 1,1,1,2,2,2 1,1,1,1,2,2,2

2)
{1,2,3,4}
Returns: 3
3)
{1,1,1,1,1,1,1,1,1,1,1,1,1,10,20,30,40,50}
Returns: 77
4)
{1,1,1,1,1,1,1,1,1,1,1,2,3,4,2,2,2}
Returns: 100

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

Coding Area

Language: C++17 · define a public class Subsets with a public method int findSubset(vector<int> numbers) · 63 test cases · 2 s / 256 MB per case

Submitting as anonymous