PROBLEM LINK:
Author: Sunny Agarwal
Tester 1: Minako Kojima
Tester 2: Shiplu Hawlader
Editorialist: Pawel Kacprzak
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Adhoc
PROBLEM:
You are given a multiset S of N numbers. Your task is to erase all elements from S. If all elements in S have the same value, you can erase all of them in one move. In the other case, you are allowed to make one specific action: pick any subset A of S such that all elements in A have the same value x, and change values of all elements in A to some y, such that y < x and there is at least one element in S with a value y. Your task is to return the minimum possible number of moves after which S is empty.
QUICK EXPLANATION:
The answer for this question is the number of distinct values in S.
EXPLANATION:
The first observation is that in order to erase all elements of S you have to reduce S to another multiset in which all elements have the same value.
Let d be the number of distinct elements in S.
The second observation is that you have to make at least d moves, because if you made k < d moves, then there exists a move and a value x in S such that you didn’t pick x in that move, so you cannot erase it.
The third observation is that you can erase all elements of S in exactly d moves. For example, we can do the following:
Let x_1 < x_2 < … < x_{d-1} < x_d be the values of elements in S.
In first move we pick all elements with value x_d and we reduce their values to x_{d-1}. In the second move, we pick all elements with value x_{d-1} and we reduce their values to x_{d-2} and so on. After d-1 steps all elements in S have value x_1 and in one move we can erase them.
Based on the second and the third observation we conclude that the minimum number of moves to do the task is d.
Time Complexity:
O(N) time complexity per one testcase. Since all values are small (up to 10^5) you can count the number of distinct elements using a simple look-up array.
AUTHOR’S AND TESTER’S SOLUTIONS:
To be uploaded soon.
RELATED PROBLEMS:
To be uploaded soon.