# FIXWEIGHT - Editorial

Tester: Takuki Kurokawa
Editorialist: Kanhaiya Mohan

Easy

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:

1. X is divisible by L, so that M = \frac{X}{L} is an integer.
2. 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;
}

2 Likes

Edit : Got the error .

Same Code as Tester Still getting WA
Solution Link : Fixed Weight Code

Code

#include <bits/stdc++.h>
typedef int ll;
using namespace std;

int main()
{
//cout << fixed << setprecision(9);
ll t;
cin >> t;
while (t--)
{
ll n,x,f=0;
cin>>n>>x;
for(ll i=1;i<=n;i++)
{
if(x%i==0&&(x/i)<=(n-i+1))
{
cout<<"YES\n";
f=1;
break;
}
}
if(f==0)
cout<<"NO\n";

}
}



Can anybody tell me why WA .

2 Likes

In the following code, you have defined ll as int

typedef int ll


But the correct way should be

typedef long long ll

3 Likes

I am getting WA.Can anyone tell me whats wrong with this code.Thanks in advance

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;cin>>t;
while(t--)
{
int n,x;
cin>>n>>x;
vector<int> v;
for(int i=1;i<=n;i++)
{
if(x%i==0)
{
v.push_back(i);

}
}

int i;
for( i=0;i<v.size();i++)
{
int p;
p=x/v[i];
if(p>n-v[i]+1)
{
continue;
}
else
{

cout<<"YES"<<endl;
break;
}
}
if(i==v.size())
{
cout<<"NO"<<endl;
}

}
}


bro x can be 1e10 and u are storing in int ,change all int to long long int.

What’s the error here. I’m using the factorization approach but stopping as soon as I find a factor that satisfies the condition.

bool checkCondition(long long d, long long x, long long n) {
long long a = d, b = x / d;
if (a > n || b > n)
return false;
if (a - 1 <= n - b ) {
// cout << "a = " << a << " b = " << b << endl;
return true;
}
}

bool factorization(long long fact, long long n) {
long long x = fact;
for (long long d = 2; d * d <= x; ++d) {
while (x % d == 0) {
if (checkCondition(d, fact, n))
return true;
x /= d;
}
}
if (x > 1)
return (checkCondition(x, fact, n));
return false;
}

void solve() {
long long n, x;
cin >> n >> x;
if (x == 1) {
cout << "YES";
return;
}
if (factorization(x, n)) {
cout << "YES";
return;
}
cout << "NO";
}


@naman_agarwal Thanks
i checked it multiple times and not see this typedef . My bad

Can anyone please explain why my code is getting Wrong Answer?

try:
for _ in range(int(input())):
N, W = map(int,input().split())

if W <= N:
print("YES")
continue

k = W
while True:
if k <= N:
break
k = k//2

L = W//k
# print(L, k)

if L <= N and k*L == W:
print("YES")
else:
print("NO")
except:
pass


Hey, your code fails on many corner cases, lets take an example test case

1
50 600

Your code outputs NO, but it is clearly possible to make such permutation to satisfy the given conditions.