PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Soumyadeep Pal
Tester: Takuki Kurokawa
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
A permutation of length N is an array of N integers (P_1,P_2, \dots,P_N) where every integer from 1 to N (inclusive) appears exactly once. The weight of a subsegment containing the elements (P_l,P_{l+1}, \dots,P_r) is defined as follows:
W(l, r) = (r-l+1)\cdot \min\limits_{l\le i \le r} (P_i)
where 1\le l \le r \le N and \min\limits_{l\le i \le r} (P_i) denotes the minimum element of the subsegment.
You are given two integers N and X. You need to determine if there exists a permutation of length N such that it contains at least one subsegment having weight X?
EXPLANATION:
Observation
We are given that the weight of a subsegment W(l, r) = (r-l+1)\cdot \min\limits_{l\le i \le r} (P_i).
Note that (r-l+1) is nothing but the length of the subsegment.
In simpler words, weight of a subsegment is equal to the length of the subsegment times the minimum element in the subsegment.
For a given N, let us consider a subsegment of length L (1 \leq L \leq N). To make the weight of this subsegment equal to X, we need to make sure:
- X is divisible by L, so that M = \frac{X}{L} is an integer.
- M is the minimum element among L elements in a permutation of length N.
Condition 1
To satisfy condition 1, we can simply check if X is divisible by L. If this is not the case, subsegment of length L can never be a possible candidate for the answer.
Condition 2
If X is divisible by L, let M = \frac{X}{L}.
In a permutation of length N, there are N - M + 1 elements greater than or equal to M. So, for M to be the minimum element of a subsegment of length L, (N - M + 1) >= L.
Example
Consider N = 3.
- Here, element 1 can be the minimum element in a subsegment of length 1, 2 or 3.
- Element 2 can be the minimum element in a subsegment of length 1 or 2. It can never be the minimum element in a subsegment of length 3 because element 1 would also exist in that subsegment.
- Element 3 can be the minimum element in a subsegment of length 1 only. It can never be the minimum element in a subsegment of length 2 or 3.
Thus, if M \leq (N-L+1), we have a possible subsegment of length L with minimum element M where the value (L \cdot M) = X.
We check all possible values of L from 1 to N and find whether the corresponding M can be the minimum element in a subsegment of length L.
Similar approach but TLE?
Instead of iterating on the length of subsegment, we can also iterate over all the factors of X and find a possible combination of L and M satisfying the conditions.
Although the approach is correct, it would result in TLE as the complexity of this approach is O(T \cdot \sqrt {X}).
Since there are no constraints on the sum of X over all cases, the solution does not pass for given time limits.
TIME COMPLEXITY:
The time complexity is O(N) per test case.
SOLUTION:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n;
long long x;
cin >> n >> x;
for (int i = 1; i <= n; i++) {
if (x % i == 0 && (n - i + 1) >= x / i) {
cout << "YES\n";
return;
}
}
cout << "NO\n";
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
long long x;
cin >> n >> x;
string ans = "NO";
for (int len = 1; len <= n; len++) {
if (x % len != 0 || x / len > n) {
continue;
}
int mn = (int) (x / len);
if (mn <= n - len + 1) {
ans = "YES";
break;
}
}
cout << ans << endl;
}
return 0;
}
Editorialist's Solution
#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n;
long long int x;
cin>>n>>x;
bool found = false;
for(int i = 1; i<=n; i++){
int len = i;
if(x%i == 0){
long long int min_ele = x/i;
if(min_ele <= n-len+1){
found = true;
break;
}
}
}
if(found) cout<<"yEs"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
,change all int to long long int.