# 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;
}
```