PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Hrishikesh
Tester: Satyam, Utkarsh Gupta
Editorialist: Devendra Singh
DIFFICULTY:
To be calculated
PREREQUISITES:
None
PROBLEM:
CodeCheffers are aware that after a contest, all problems are moved into the platform’s practice section. Based on user submissions during the contest, the system calculates and assigns a difficulty rating to each problem. Ideally, it is recommended that users practice problems in increasing order of difficulty.
Our Chef has some students in his coding class who are practicing problems. Given the difficulty of the problems that the students have solved in order, help the Chef identify if they are solving them in non-decreasing order of difficulty. That is, the students should not solve a problem with difficulty d_1, and then later a problem with difficulty d_2, where d_1>d_2.
Output “Yes” if the problems are attempted in non-decreasing order of difficulty rating and “No” if not.
EXPLANATION:
Attempting the problem in non-decreasing order implies that there does not exist an index i from 1 to N-1 such that A_{i+1}<A_i. If there exists such an index the answer is NO
else the answer is YES
.
TIME COMPLEXITY:
O(N) or for each test case.
SOLUTION:
Setter's solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int tc;
cin>>tc;
while(tc--)
{
int n;
cin>>n;
vector<int> a(n);
for(auto &x : a)
cin>>x;
vector<int> b(a);
sort(a.begin() , a.end());
bool sorted = true;
for(int i = 0; i < n; i++)
{
if(a[i]!=b[i])
sorted = false;
}
cout<<(sorted ? "Yes" : "No")<<endl;
}
return 0;
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
int n;
cin >> n;
vll v(n + 1, 0);
bool flag = true;
for (int i = 1; i <= n; i++)
{
cin >> v[i];
if (v[i] < v[i - 1])
flag = false;
}
if (flag)
cout << "YES\n";
else
cout << "NO\n";
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}