RESETZ - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

Sorting

PROBLEM:

There are N stoves.
At the start of each minute, at most one stove can be reset to a temperature of 0.
At the end of each minute, all of the stoves’ temperatures increase by exactly 1.

Is it possible to reach a state where the i-th stove has a temperature of B_i?

EXPLANATION:

Let A_i denote the current temperature of the i-th stove.
Every minute, we can set (at most) one A_i to 0, and then every A_i increases by 1.

Suppose we reset stove i at some point of time (other than the very first minute).
Then, observe that for any j \ne i, we can never have A_i = A_j in the future!

To see why, observe that at the end of every minute, we’ll definitely have A_i \ge 1 for all i.
So, if we choose to reset a stove to 0, it will become the unique stove with value 0 - every other stove will remain \ge 1.
After everything increments by 1, the reset stove will have a temperature of 1, while every other stove will have value \ge 2.
This difference will continue to be maintained in the future as well.

Thus, we see that:

  1. All stoves that are reset at least once must have distinct temperatures.
  2. All stoves that are never reset will have the same temperature (obviously).
  3. The temperature of the never-reset stoves must be strictly higher than the temperature of the stoves that were reset at least once.

Together, these three observations tell us that one necessary condition for a solution to exist is the following.
Let M denote the maximum element present in B.
Then, all elements smaller than M in B must be distinct.

It’s not hard to see that this condition is also sufficient for a solution to exist.
To attain a construction: use exactly M minutes, and for each i such that B_i \lt M, reset the i-th stove at the start of the (M - B_i + 1)-th minute (so that it will then proceed to increase exactly B_i times till the end of minute M.)
Because all the B_i smaller than M are distinct, this results in at most one stove being reset every minute, as desired.

One simple way to check the desired condition quickly is to use sorting.

Sort the array B first, so that B_1 \le B_2 \le\ldots\le B_N.
Now, if there exists some index i such that B_i = B_{i+1} but B_i \ne B_N, the answer is No.
Otherwise the answer is Yes.
This gives a check in \mathcal{O}(N) after sorting.

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector b(n, 0);
        for (int &x : b) cin >> x;

        ranges::sort(a);
        string ans = "Yes";
        for (int i = 0; i+1 < n; ++i) {
            if (b[i] == b[i+1] and b[i] != b[n-1]) ans = "No";
        }
        cout << ans << '\n';
    }
}
1 Like