Connection Status:
Competition Arena > IncrementingSequence

IncrementingSequence

SRM 625 · 2013-12-22 · by vexorian

SRM 625 · 2013-12-22 · by vexorian · Greedy, Sorting
Class Name: IncrementingSequence
Return Type: String
Method Name: canItBeDone
Arg Types: (int, vector<int>)
Problem Statement

Problem Statement

You have a int[] A with N elements.

Your goal is to change it into a int[] that contains each number from 1 to N exactly once. The change will consist of zero or more steps. In each step, you may pick an arbitrary element of A and increment its value by k. You may pick the same element multiple times. Note that you are not allowed to decrement the value of any element.

You are given the int k and the int[] A. Return "POSSIBLE" if it is possible to achieve your goal. Return "IMPOSSIBLE" otherwise.

Notes

  • Return value is case-sensitive. For example, you can't return "Possible" or "possible" instead of "POSSIBLE".

Constraints

  • k will be between 1 and 10, inclusive.
  • A will contain between 1 and 50 elements, inclusive.
  • Each element of A will be between 1 and 50, inclusive.
Examples
0)
3
{1,2,4,3}
Returns: "POSSIBLE"

This sequence of length 4 already contains all numbers from 1 to 4 exactly once. Note that their order does not matter.

1)
5
{2,2}
Returns: "IMPOSSIBLE"
2)
1
{1,1,1,1,1,1,1,1}
Returns: "POSSIBLE"

There are many ways to achieve the goal. For example, it is possible to obtain the sequence {1,2,3,4,5,6,7,8}. To do this, just increment the element at each position one by one until it reaches the required value.

3)
2
{5,3,3,2,1}
Returns: "IMPOSSIBLE"

We want to have the values {1,2,3,4,5}, in any order. Currently, we are missing the 4. As k=2, the only way to produce a 4 is by incrementing a 2. But if we increment our only 2, we will have no way of producing another 2.

4)
9
{1,2,3,1,4,5,6,7,9,8}
Returns: "POSSIBLE"

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

Coding Area

Language: C++17 · define a public class IncrementingSequence with a public method string canItBeDone(int k, vector<int> A) · 255 test cases · 2 s / 256 MB per case

Submitting as anonymous