Connection Status:
Competition Arena > RepeatedHalving

RepeatedHalving

SRM 840 · 2022-10-24 · by misof

SRM 840 · 2022-10-24 · by misof · Simulation, Sorting
Class Name: RepeatedHalving
Return Type: int[]
Method Name: simulate
Arg Types: (vector<int>, int)
Problem Statement

Problem Statement

You have a collection of bags, each containing some marbles. You are given the int[] bags that describes this collection: each element of bags is the number of marbles in one of the bags.

Consider the following process:

  1. Find the bag that currently contains the most marbles. (If there are several bags tied for having the maximum number of marbles, pick any one of them.)
  2. Remove half of the marbles from that bag. Round the number of removed marbles up if necessary. (E.g., if there are 21 marbles in the bag, you remove 11 and leave 10 in the bag.)
  3. Throw away the removed marbles.

You are going to repeat the above process steps times.

Determine the final numbers of marbles in the bags. Return a int[] containing these numbers sorted in non-descending order.

Constraints

  • bags will contain between 1 and 100 elements, inclusive.
  • Each element of bags will be between 0 and 10^9, inclusive.
  • steps will be between 1 and 10^9, inclusive.
Examples
0)
{1, 2, 3, 21, 5, 4}
4
Returns: {1, 2, 2, 2, 3, 4 }

We select the bag with 21 marbles and remove 11 of them, leaving 10. We select the bag with 10 marbles and remove 5 of them, leaving 5. We select either one of the two bags with 5 marbles and remove 3 of them, leaving 2 in that bag. We select the other bag with 5 marbles (which is now the only bag with that many marbles) and we remove 3 of them, leaving 2. Remember that the return value must be sorted. E.g., the array {1, 2, 3, 2, 2, 4} has the correct pile sizes but not in the correct order, and thus it would not be accepted as an answer.

1)
{1, 1, 1, 1, 1}
5
Returns: {0, 0, 0, 0, 0 }

In each step we select a different bag and we remove the one marble it contains.

2)
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
1000000000
Returns: {0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

In each step we select an arbitrary bag and we remove half of the marbles it contains. (I.e., we remove zero marbles and keep zero marbles in the bag.) Keep in mind that a straightforward simulation of 10^9 steps, one at a time, will take quite a lot of time to complete.

3)
{123, 4568, 89123, 45, 678901234}
27
Returns: {45, 123, 1142, 1294, 1392 }
4)
{1000000000}
29
Returns: {1 }

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

Coding Area

Language: C++17 · define a public class RepeatedHalving with a public method vector<int> simulate(vector<int> bags, int steps) · 73 test cases · 2 s / 256 MB per case

Submitting as anonymous