Codeforces 546B Soldier and Badges Solution & Explanation

Difficulty : 1200

Problem Description

Colonel has n badges. He wants to give one badge to every of his n soldiers. Each badge has a coolness factor, which shows how much it’s owner reached. Coolness factor can be increased by one for the cost of one coin.

For every pair of soldiers one of them should get a badge with strictly higher factor than the second one. Exact values of their factors aren’t important, they just need to have distinct factors.

Colonel knows, which soldier is supposed to get which badge initially, but there is a problem. Some of badges may have the same factor of coolness. Help him and calculate how much money has to be paid for making all badges have different factors of coolness.

Input

First line of input consists of one integer n (1 ≤ n ≤ 3000).

Next line consists of n integers a_i (1 ≤ a_i ≤ n), which stand for coolness factor of each badge.

Output

Output single integer — minimum amount of coins the colonel has to pay.

Examples

Note

In first sample test we can increase factor of first badge by 1.

In second sample test we can increase factors of the second and the third badge by 1.

Understand this problem in 3 seconds

Given an array, you need to make all the elements unique by adding a certain amount to any duplicates until every element in the array is distinct.

Solution

The program is divided into two steps:

1. Sorting the Array: Start by sorting the array arr in ascending order.
2. Iterative Check for Increasing Sequence:
   Initialize cur as the first element of the sorted array (arr[0]) and cnt as 0.
   Traverse through the array using a loop starting from the second element (i=1).
   For each element arr[i]:
   • If arr[i] is less than or equal to cur, calculate the necessary increase to make it greater than cur, add this to cnt, and update cur accordingly.
   • If arr[i] is greater than cur, update cur to arr[i] directly.

This approach ensures that all elements in the array form an increasing sequence, with cnt representing the minimal cost needed to make all elements unique in the sequence.

C# Solution

Solution1

int n = int.Parse(Console.ReadLine());
int[] arr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

Array.Sort(arr);

int cur = arr[0];
int cnt = 0;

for(int i=1; i<n; i++){
    if(arr[i]<=cur){
        cnt+= cur-arr[i]+1;
        cur+=1;
    }
    else{
        cur = arr[i];
    }
}

Console.WriteLine(cnt);

The time complexity of the entire code is O(n log n) + O(n). In Big O notation, we ignore constant factors, so the overall time complexity is approximately O(n log n).

Conclusion

This is the second problem from codeforces contest – Dashboard – Codeforces Round 304 (Div. 2) – Codeforces

You can find the solution for the first problem here – Codeforces 546A Soldier and Bananas

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks you~~

✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know !!

The problem link : Problem – 546B – Codeforces

Some Random Codeforces Posts