Connection Status:
Competition Arena > ValueDivision

ValueDivision

SRM 784 · 2020-04-23 · by Witaliy

SRM 784 · 2020-04-23 · by Witaliy · Brute Force, Greedy, Simple Math
Class Name: ValueDivision
Return Type: int[]
Method Name: getArray
Arg Types: (vector<int>)
Problem Statement

Problem Statement

You are given an int[] A of positive integers. In a single turn, you can do the following: Choose any value X that is greater than 1. Let C be the number of occurrences of X in the array A. You then subtract 1 from exactly C/2 (rounded down) of those occurrences.

Find the lexicographically smallest array you can obtain after performing any number of turns.

Constraints

  • A will contain between 1 and 1,000 elements, inclusive.
  • Each element of A will be between 1 and 109, inclusive.
Examples
0)
{1, 5, 7, 4, 5, 4, 1}
Returns: {1, 2, 7, 3, 5, 4, 1 }
1)
{7}
Returns: {7 }
2)
{7, 4}
Returns: {7, 4 }
3)
{7, 7, 7, 7}
Returns: {4, 5, 6, 7 }
4)
{3, 2, 1}
Returns: {3, 2, 1 }

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

Coding Area

Language: C++17 · define a public class ValueDivision with a public method vector<int> getArray(vector<int> A) · 112 test cases · 2 s / 256 MB per case

Submitting as anonymous