April 28, 2020

Arpa's Problem of April, 2020

AmirReza PoorAkhavana.poorakhavan

DURATION

7 min

Tags

Constructive

Learn more

Topcoder Thrive

For this article I sought a problem that was straightforward yet interesting. What’s better for that than this nice ValueDivision problem by misof? Let’s see what we have here.

This is a division 1 easy problem. Don’t worry if you’re a beginner, the solution is easy to understand. If your member rating is red on TC or CF, this will probably not be interesting to you.

About the problem

In this problem, 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.

You’re asked to find the lexicographically smallest array you can obtain after performing any number of turns.

The length of the array is at most 1000.

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 }

Approach

What is the lexicographical order? It is alphabetical order, just as in the dictionary. For example, ab < ac, a < ab. We start from the first letter and find the first non-equal letter between the two words. The word with the smaller letter in this position goes before the other word. The same order is used when we have numbers rather than letters in sequences. <1, 3> < <2, 1>.

So we want to find the lexicographically smallest array.

In these types of problems the strategy is always the same. Try to minimize the first element, then minimize the second, and so on.

Let’s see how much we can decrease the first element. Consider the following case: {2, 3, 3}. At first, it seems impossible to decrease the first element, but that is not true. We can begin by decreasing the second element and then we can decrease the first.

So now the idea comes to mind: start from the maximum element and apply as many possible operations on it until the number of occurrences reaches 1 (such that it’s impossible to decrease it more).

Consider that we have 7 occurrences of maximum at the first. We convert it to 4 at first, then to 2, then to 1. It’s impossible to remove the remaining one, because 1 / 2 = 0. Therefore it’s impossible to remove the maximum completely. So, what is the best option? We keep the last occurrence of the maximum and decrease the remaining ones.

def getArray(self, A):
    A = list(A)
    last_max = 10**9 + 47
    while True:
       curr_max = 0
       curr_last = 1
       for i in range(len(A)):
          if A[i] < last_max and A[i] >= curr_max:
            curr_max = A[i]
            curr_last = i
       if curr_max == 1:
          break
       for i in range(curr_last):
         if A[i] == curr_max:
            A[i] -= 1
      last_max = curr_max
      return A

Each time we keep track of the number we removed the previous time (last_max). We find the maximum of the remaining numbers, decrease each occurrence of the maximum by 1 except the last (which we can’t remove).

For example, take the first sample test. We can’t decrease 7, because it appeared just once. We can decrease the first 5 to 4. Here is the summary:

{1, 5, 7, 4, 5, 4, 1}
{1, 4, 7, 4, 5, 4, 1}
{1, 3, 7, 3, 5, 4, 1}
{1, 2, 7, 3, 5, 4, 1}

Exercise

Solve the problem in O(n).

What’s Next?

These types of problems can be categorized under constructive problems. Constructive problems are those that ask us to come up with a novel approach for constructing an array, graph, etc. Thinking on paper and generating a lot of examples to solve them can be useful.

Here are several more problems to be solved in the same category.
1236C (Easy)
1202D (Easy-Medium)
1270E (Medium)
756E (Hard)

Chat on Discord