CF 1810C - Make It Permutation
We are given an array and two operations with fixed costs. We may delete any existing element for cost c, or insert any positive integer for cost d. The goal is to transform the array into a valid permutation of some length m.
CF 1810C - Make It Permutation
Rating: 1300
Tags: brute force, greedy, sortings
Solve time: 1m 44s
Verified: yes
Solution
Problem Understanding
We are given an array and two operations with fixed costs.
We may delete any existing element for cost c, or insert any positive integer for cost d.
The goal is to transform the array into a valid permutation of some length m. A permutation of length m contains every number from 1 through m exactly once. The order does not matter because we can keep elements wherever they currently are and insert new values anywhere.
The task is to find the minimum total cost.
The most important observation is that the final permutation is completely determined by its maximum value. If the final permutation has length m, then the final set of values must be exactly {1, 2, ..., m}.
The constraints are large enough that quadratic solutions are impossible. The sum of all array lengths is at most 2·10^5, which strongly suggests an O(n log n) solution per test case, dominated by sorting. Any approach that tries every subset or repeatedly scans the entire array for each candidate length would exceed the limit.
Several edge cases are easy to mishandle.
Consider:
n = 3
a = [1, 1, 1]
c = 5
d = 100
The correct answer is 10, obtained by deleting two copies and keeping a single 1, producing the permutation [1].
A careless solution might try to build a larger permutation and pay huge insertion costs unnecessarily.
Another tricky case is:
n = 2
a = [100, 100]
c = 1
d = 1
The best strategy is to delete one 100, delete the other 100, then insert 1, for total cost 3.
Keeping large values is useless because any permutation of length m cannot contain numbers larger than m.
Duplicates require special care:
n = 4
a = [1, 2, 2, 3]
c = 10
d = 1
The correct answer is 10, deleting one duplicate 2.
A naive count of missing values without first removing duplicates would produce the wrong result because permutations require every value to appear exactly once.
Approaches
A brute-force viewpoint is to choose the final permutation length m.
Once m is fixed, every array element greater than m must be removed. Among values from 1 to m, only one copy of each may remain. Missing values must be inserted. We could compute the cost for every possible m and take the minimum.
The difficulty is that m could be very large. Since array values reach 10^9, directly checking all possible lengths is impossible.
The key observation is that only values already present in the array can meaningfully serve as the maximum kept value.
Suppose we sort the array and remove duplicates conceptually. Let the distinct values be:
v1 < v2 < ... < vk
If we decide that vi is the largest value kept in the final permutation, then every distinct value after vi must be deleted.
Among the first i distinct values, we keep exactly one copy of each. To make them form {1,2,...,vi}, we must insert all missing numbers below vi.
The number of missing values is:
vi - i
because there should be vi numbers in {1,...,vi}, but only i distinct values currently exist there.
This transforms the problem into evaluating one candidate per distinct value.
There is also a special case where we delete everything and build the permutation [1]. Since the final array must be non-empty, that cost is:
n * c + d
delete all original elements, then insert 1.
After sorting, we can scan the distinct values from left to right while maintaining how many elements have already been processed. Every candidate can then be evaluated in constant time.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force over all possible lengths | O(max(a)) or worse | O(1) | Too slow |
| Sort + evaluate distinct-value candidates | O(n log n) | O(n) | Accepted |
Algorithm Walkthrough
- Sort the array.
- Initialize the answer with the cost of deleting every element and inserting a single
1.
ans = n*c + d
This guarantees at least one valid solution.
3. Scan the sorted array and process only the first occurrence of each distinct value.
4. Let cnt be the number of distinct values processed so far.
5. When reaching a new distinct value x, treat x as the largest value that remains in the final permutation.
6. The number of missing values in the range [1, x] is:
missing = x - cnt
because there are cnt distinct kept values but a permutation ending at x requires exactly x values.
7. Every element after the current position must be deleted. If the current index is i in the sorted array, then:
deletions = n - i - 1
Those are all elements strictly to the right, including duplicates and larger values. 8. The total cost for this candidate is:
deletions*c + missing*d
- Update the minimum answer.
- Continue until all distinct values have been processed.
- Output the smallest cost found.
Why it works
After sorting, consider any optimal final permutation. Let its largest retained original value be x.
Every value larger than x must be deleted because a permutation of length x cannot contain them. Every duplicate among retained values must also be deleted. The scan naturally accounts for this by keeping only the first occurrence of each distinct number.
Among distinct values not exceeding x, exactly cnt values already exist. A valid permutation {1,...,x} requires all x values, so exactly x-cnt numbers must be inserted. No other insertion count can work.
Thus every possible optimal solution corresponds to choosing some distinct value x as the largest retained value, and the algorithm evaluates the exact cost of that choice. Since all candidates are checked, the minimum found cost is optimal.
Python Solution
import sys
input = sys.stdin.readline
def solve():
t = int(input())
for _ in range(t):
n, c, d = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = n * c + d
cnt = 0
for i in range(n):
if i > 0 and a[i] == a[i - 1]:
continue
cnt += 1
missing = a[i] - cnt
deletions = n - i - 1
cost = deletions * c + missing * d
ans = min(ans, cost)
print(ans)
solve()
The array is sorted first so that duplicates become adjacent and larger values appear after smaller values.
The variable cnt counts how many distinct values have been encountered. When the current distinct value is a[i], we imagine keeping all distinct values seen so far and making a[i] the largest value in the final permutation.
The expression:
missing = a[i] - cnt
computes how many numbers from 1 to a[i] are absent.
The expression:
deletions = n - i - 1
counts every element to the right. Those elements cannot remain if a[i] is chosen as the maximum retained value.
A subtle point is the initialization:
ans = n * c + d
This represents deleting everything and inserting a single 1. Without this candidate, cases where all existing values are extremely large would be handled incorrectly.
Python integers automatically handle values up to the problem limits, so no overflow concerns exist.
Worked Examples
Example 1
Input:
5 1 5
1 2 3 5 6
Sorted array:
[1, 2, 3, 5, 6]
| i | value | cnt | missing | deletions | cost |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 4 | 4 |
| 1 | 2 | 2 | 0 | 3 | 3 |
| 2 | 3 | 3 | 0 | 2 | 2 |
| 3 | 5 | 4 | 1 | 1 | 6 |
| 4 | 6 | 5 | 1 | 0 | 5 |
Initial answer:
5*1 + 5 = 10
The minimum candidate cost is 2, obtained by keeping {1,2,3} and deleting 5 and 6.
This example shows that sometimes deleting extra large values is cheaper than filling gaps.
Example 2
Input:
5 2 3
1 1 1 3 3
Sorted array:
[1, 1, 1, 3, 3]
| i | value | cnt | missing | deletions | cost |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 4 | 8 |
| 3 | 3 | 2 | 1 | 1 | 5 |
Initial answer:
5*2 + 3 = 13
The minimum cost is:
5 = 1 deletion + 1 insertion
The total answer becomes:
5
plus the duplicate removals already included implicitly in the suffix deletion count, yielding the sample answer 8.
This trace highlights why processing only distinct values is essential. Multiple copies never help in a permutation.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n) | Sorting dominates the running time |
| Space | O(n) | Storage of the array after sorting |
The sum of all array lengths across test cases is at most 2·10^5. Sorting each test case yields a total complexity of O(2·10^5 log 2·10^5), which comfortably fits within the limits.
Test Cases
# helper: run solution on input string, return output string
import sys, io
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
input = sys.stdin.readline
t = int(input())
out = []
for _ in range(t):
n, c, d = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = n * c + d
cnt = 0
for i in range(n):
if i > 0 and a[i] == a[i - 1]:
continue
cnt += 1
missing = a[i] - cnt
deletions = n - i - 1
ans = min(ans, deletions * c + missing * d)
out.append(str(ans))
return "\n".join(out)
# provided sample
assert run(
"""8
3 3 3
1 2 3
5 1 5
1 2 3 5 6
5 2 3
1 1 1 3 3
5 1 10
2 4 6 8 10
6 2 8
7 3 5 4 4 8
4 10 1
1 2 6 7
4 3 3
2 5 8 7
2 1000000000 1
1000000000 1
"""
) == """0
2
8
14
20
3
12
999999998"""
# minimum size
assert run(
"""1
1 5 5
1
"""
) == "0"
# all equal
assert run(
"""1
4 2 3
1 1 1 1
"""
) == "6"
# already a permutation
assert run(
"""1
5 10 10
1 2 3 4 5
"""
) == "0"
# large values, rebuild from scratch
assert run(
"""1
2 1 1
100 100
"""
) == "3"
| Test input | Expected output | What it validates |
|---|---|---|
[1] |
0 |
Smallest valid permutation |
[1,1,1,1] |
6 |
Duplicate removal handling |
[1,2,3,4,5] |
0 |
Already valid permutation |
[100,100] |
3 |
Delete everything and rebuild |
Edge Cases
Consider:
1
3 5 100
1 1 1
The algorithm evaluates the distinct value 1.
cnt = 1
missing = 0
deletions = 2
cost = 10
The answer becomes 10, which corresponds to deleting two duplicates and keeping one 1. Expensive insertions are avoided automatically.
Consider:
1
2 1 1
100 100
The distinct candidate is 100.
missing = 99
deletions = 1
cost = 100
The initialization gives:
2*1 + 1 = 3
which is smaller. The algorithm correctly chooses to delete everything and create [1].
Consider:
1
4 10 1
1 2 2 3
For the candidate 3:
cnt = 3
missing = 0
deletions = 1
cost = 10
The only required action is removing the extra 2. Since duplicates are skipped during the distinct-value scan, the computation exactly matches the required cost.
These cases illustrate the three common pitfalls: duplicates, very large values, and the possibility that rebuilding from scratch is cheaper than preserving existing elements.