S07E09 - Editorial

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;
}
1 Like

Was it mentioned in the question that the order can be changed? I assumed that the order of the neighbors is important.

30 Likes

It was nowhere mentioned that we can rearrange the array. I got 7 WA because of this.

23 Likes

Same here (exactly 7 WA for me too XD).

7 Likes

The question was poorly framed. I thought that only the starting point can be chosen. Got 8 WAs due to this ; )

11 Likes

This is what I sent in a comment to problem setters during the contest:

I solved the problem and don’t need any help myself. But I think that the problem statement is confusing and does not clearly differentiate between “the order of how neighbours are arranged in a row BEFORE the game starts” and the “order of how the ball is passed around AFTER the start of the game”. It’s the same word “order” with two possible meanings.

I had a hope that the contest admins could send a message to all participants with a clarification, but this didn’t happen.

This was one of the most confising problem statements that I have seen in a while. The provided examples don’t allow us to see the fact that the order of neighbours can be changed, because the answer for the fixed order of neigbors is exactly the same!

Additionally, the constraints allow N to be equal to 1. How can a person pass the bowl to himself and what happens in this case? I suspected that this could have been the possible cause for the WA too when I was troubleshooting.

18 Likes

You should have mentioned it clearly.
I thought that only the starting point can be chosen and not that the neighbours position can be changed.

4 Likes

Same here

1 Like

Still over 1200+ people got it idk how

3 Likes

Oii! how come the order is changing! I was banging my head for 2hrs 50 mins and ended up with idk how many WAs !

6 Likes

Solutions were on Youtube for the last hour or so of the contest. That solution involved sorting, which is in no way necessary to literally just find the minimum and its count as it could be done in linear time. But I saw many (almost all the solutions using sorting)

Highly poor problem statement, it doesn’t mention that order of the neighbors could be changed. Got 8 W.A. because of this

7 Likes

I was checking through some of the solutions to see my mistake, and found a lot of them to be using similar logic which was sort in descending manner, which wasn’t even necessary…
For the intended problem one could just count minm using an array

1 Like

the order doesn’t matter
if you arrange the array in any way the answer will still be the same

Even though this was unrated for me, which saved me from huge loss. I feel sorry for div 2 guys who were screwed by the contest hosts. I gave nearly 2+ hours wondering why my code is wrong.

U all went through the trouble of writing plots of friends episodes(which I enjoyed) but completely unnecessary and didn’t bother to make the problem statement clear for everyone. This was messed up I wasted so much time in an easy problem.

I don’t know if codechef has a feature like cf alerts because its not uncommon to miss something. Its important to rectify it asap!!
Now that it is over, I don’t expect u would make it unrated which again wouldn’t be fair, but own up to your mistake and apologize.

9 Likes

rip codechef :slight_smile:

6 Likes

The order DOES matter. If you can change it (like sort them, that matters in increasing the maximum). Consider an order with 2 or more “islands”, for example: 0 0 1 1 1 0 0 1 1 0 0 (Here we are not considering the minimum_value * n part). If you start in the first island, going to the second island wouldn’t be possible. So you should just consider one largest island.

2 Likes

The order does matter. In the case if we want to preserve the original order of neighbours as given in the input, then:

  • we need to find the minimum value among all array elements, let’s call it X
  • subtract X from all array elements
  • find the longest streak of consecutive non-zero elements in the resulting array, taking into account the possible wraparound, let’s call it Y
  • the answer is X * N + Y

If we are allowed to change the order of neighbours, then Y is just the total number of remaining non-zero elements rather than the longest streak.

3 Likes

It was clearly mentioned in the explanation of sample test case bro…

1 Like

It was clearly mentioned in the explanation of sample test case bro.