PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Kanhaiya Mohan
Tester: Nishant Shah
Editorialist: Bhavya Mittal
DIFFICULTY
Easy
PREREQUISITES
None
PROBLEM
Given an array A of length N. You need to rearrange the elements of A such that:
- the value of the element decreases by 1 upon visiting.
- the number of elements visited is maximum
- elements are visited in circular order until 0 is encountered
EXPLANATION
Observation 1
The first zero will be encountered at one of the minimum values of the array.
Proof
Since each element decreases by 1 upon visiting and we are traversing the array in a circular fashion, the first element where we will encounter 0 will be one of the minimums.
Since we can rearrange the elements in any order, we sort the array in increasing order, so that all the minimum elements come together in one place.
Observation 2
If we complete one loop on the whole array then the value of every element decreases exactly by 1.
Observation 3
We can traverse through the array at a[0] (of the sorted array) times, i.e. we can visit at least a[0] * N elements.
Proof
Let’s take an example to understand this point:
Let the sorted array be [2, 2, 3, 5, 6]
After 1 traversal: [1, 1, 2, 4, 5] Elements visited = 5
After 2 traversals: [0, 0, 1, 3, 4] Elements visited = 5
Total elements visited = 5 + 5 = 2 * 5
Since the first element has become$ 0$, we can’t traverse the array any more.
Now, to maximize the number of elements visited we can start our traversal from the element next to the element with the minimum value, which isn’t equal to it.
Let’s say that value is at index i, then our final answer = a[0] * N + (N - i).
To understand this let’s take the above example again.
The sorted array: [2, 2, 3, 5, 6]
We start our traversal from 3.
After 1 traversal: [2, 2, 2, 4, 5]. Elements visited = 3.
The remaining 2 traversals are the same.
Total elements visited = 2 * 5 + 3.
SOLUTIONS
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int n;
void solve()
{
cin >> n;
long long int a[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
sort(a, a + n);
int ans = 0;
int mn = a[0];
for (int i = 0; i < n; i++)
{
if (a[i] > mn)
{
cout << a[0] * n + n - i;
return;
}
}
cout << a[0] * n;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
cout << "\n";
}
return 0;
}
