EqualPiles | Topcoder Archive

Problem Statement

It's Halloween. You have N bags of candy to hand out to trick-or-treating kids. The bags are numbered from 0 to N-1, inclusive.

Each bag contains some number of candies: bag number i contains (1 + (i*i modulo M)) candies.

It's best if all bags of candy you hand out are equally large - that way siblings won't argue that one of them got more than the other.

You have T minutes before the kids arrive. During each minute you can open one bag of candies, eat some of the candies in the bag (possibly all of them) and re-seal the bag.

You want to produce as many equal bags of candy as possible. (The number of candies in those bags does not matter.)

Calculate and return the largest number of equal bags you can obtain in T minutes.

Definition

Class:: EqualPiles
Method:: equalize
Parameters:: int, int, int
Returns:: int
Method signature:: int equalize(int N, int M, int T)
(be sure your method is public)

Notes

The formula for the number of candies in each bag is just to keep the input size small. The reference solution would work for any numbers of candies in bags.
Watch out for integer overflow when computing the initial number of candies in each bag. In particular, the value i*i will not always fit into a 32-bit integer.

Constraints

N will be between 1 and 300,000, inclusive.
M will be between 1 and 10^9, inclusive.
T will be between 0 and N, inclusive.

Examples

```
10
```
```
12345678
```
```
0
```
```
Returns: 1
```
You have ten bags of candy. They contain the following number of candies: {1, 2, 5, 10, 17, 26, 37, 50, 65, 82}. You don't have the time to eat any candy, so you can't even create two equal bags.
```
10
```
```
1
```
```
0
```
```
Returns: 10
```
Here you have ten bags containing one candy each. Even though you have no time left, you already have ten identical bags.
```
10
```
```
12345678
```
```
3
```
```
Returns: 4
```
This test case has the same ten bags as example #0, but now you have three minutes. In those three minutes you can create four identical bags. For example, you can eat 7 candies out of the bag with 17, then 16 candies out of the bag with 26, and finally 40 candies out of the bag with 50. In the end you will have four bags with 10 candies in each of them.
```
10
```
```
10
```
```
4
```
```
Returns: 6
```
Here the bag sizes are {1, 2, 5, 10, 7, 6, 7, 10, 5, 2}. You have four minutes to eat some candy, and the best you can do is to create six identical bags of candy.
```
100000
```
```
7
```
```
0
```
```
Returns: 28572
```
The most common bag size is 3, with 28,572 bags that have exactly 3 candies each.
```
100000
```
```
7
```
```
1
```
```
Returns: 28573
```
Here the optimal solution is to produce another bag with 3 candies out of one of the bigger bags.
```
100000
```
```
7
```
```
98765
```
```
Returns: 100000
```
You have more than enough time to make all bags identical (with exactly one candy in each of them).
```
5
```
```
5
```
```
5
```
```
Returns: 5
```
One of multiple optimal solutions is to simply eat everything. You will be left with five equal bags - all of them empty.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.