MAGICMOD - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: S.Manuj Nanthan
Tester: Harris Leung
Editorialist: Aman Dwivedi

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Observation, Factors

PROBLEM:

You are given an array A of N integers. You want to convert the array A into a permutation of N integers. To do this, you can apply the following operation on array AA exactly once.

  • Pick an integer X, where 1≤X≤2⋅10^7. For each i , 1 \le i \le N, replace A_i by A_i\%X.

Find out whether it is possible to convert A into a permutation of N integers. If it is possible, print YES (all uppercase alphabets) and any possible value of X for which it is possible. Otherwise, print NO (all uppercase alphabets).

EXPLANATION:

Let’s say there exists a value X such that it is possible to achieve the permutation of length N. Now, let’s do according to the problem and express A_i in terms of X.

A_1 = R_1 + Q_1*X \\ A_2= R_2+Q_2*X \\ ............................. \\ A_N = R_N + Q_N*X

Now in order to get the permutation from A_i it is quite clear that (R_1, R_2, \dots, R_N) should be a permutation. Let’s assume that the sequence R is a permutation. It means that:

\sum{S_R} = \frac{N*(N+1)}{2}

Now, if we subtract the Sum_R from the given array A, we will be left with the sequence:

(Q_1*X) , (Q_2*X), \dots , (Q_N*X)

Now let’s say:

Q' = Q_1*X+Q_2*X+\dots+Q_N*X
Q' = (Q_1+Q_2+,\dots,+Q_N)*X

Now we are left with Q`. Could you think what is Q` in terms of the given array?

Ok, so let’s say the summation of the given array be S, i.e

S = \sum{A}

Hence Q` is nothing but just

Q` = S - S_R

Now we can also see that X needs to be the factor of this Q`. Now you can simply find all the factors of Q` and check whether there is any X that satisfies the given conditions. It can be checked by simply using hashing, you can refer codes if you are stuck in the implementation part.

TIME COMPLEXITY:

O(N*F)

where F is the number of factors.

Thanks to Aryan Choudhary for this. You can look his comment below for more explanation of the time.

SOLUTIONS:

Author's
def check_valid(a,x):
    visit=set()
    for i in a:
        ok=i%x
        if(ok>n or ok==0 or ok in visit):
            return 0
        visit.add(ok)
    return 1
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    total=sum(a)
    total-=((n*(n+1))//2)
    flag=0
    for i in range(1,int(total**0.5)+1):
        if(total%i==0):
            if(check_valid(a,i)):
                flag=1
                result=i
                break
            if(check_valid(a,total//i)):
                flag=1
                result=total//i
                break
    visit=set()
    for i in a:
        if(i>=1 and i<=n):
            visit.add(i)
    if(len(visit)==n):
        flag=1
        result=n+1
    if(flag):
        print("YES",result)
    else:
        print("NO")

Tester
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=1e5+1;
int n;
ll a[N];
ll pf[N];
ll s,t;
bool vis[N];
bool check(ll x){
	if(s%x!=0) return false;
	for(int i=1; i<=n ;i++) vis[i]=false;
	for(int i=1; i<=n ;i++){
		if(a[i]%x==0 || a[i]%x>n || vis[a[i]%x]) return false;
		vis[a[i]%x]=true;
	}
	return true;
}
ll f(ll x){
	while(x<=n) x*=2;
	return x;
}
void solve(){
	cin >> n;
	s=0;
	for(int i=1; i<=n ;i++){
		cin >> a[i];
		s+=a[i]-i;
	}
	sort(a+1,a+n+1);
	for(int i=2; i<=n ;i++){
		if(a[i]==a[i-1]){cout << "NO\n";return;}
	}
	if(s<0){cout << "NO\n";return;}
	if(s==0){cout << "YES\n";return;}
	t=s;
	while(t%2==0) t/=2;
	for(ll i=1; i*i<=s ;i++){
		if(s%i!=0) continue;
		ll x=f(i),y=f(s/i);
		if(check(x)){cout << "YES " << x << '\n';return;}
		if(check(y)){cout << "YES " << y << '\n';return;}
	}
	cout << "NO\n";
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int t;cin >> t;
	while(t--) solve();
	//solve();
}
Editorialist
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e5+5;
bool vis[N];
int a[N];
int n;
int s;

bool check(int x){
	if(s%x!=0) return false;
	for(int i=1; i<=n ;i++) vis[i]=false;
	for(int i=1; i<=n ;i++){
		if(a[i]%x==0 || a[i]%x>n || vis[a[i]%x]) return false;
		vis[a[i]%x]=true;
	}
	return true;
}

void solve()
{
  cin>>n;
  s = 0;

  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
    s += (a[i]-i);
  }


  if(s == 0) {
    cout<<"YES "<<n+1<<"\n";
  } else if(s < 0) {
    cout<<"NO"<<"\n";
  } else {
    for (int i = 1; i * i <= s ; i++) {
      if (s % i == 0) {
        if(check(i) && i <= 2e7) {cout << "YES " << i << '\n';return;}
        if(check(s/i) && (s/i) <= 2e7) {cout << "YES " << s/i << '\n';return;}
      }
    }
    cout << "NO" << '\n';return;
  }
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}

5 Likes

S = sum of array can go till 10^12 and maximum factors of number till 10^12 is 6720
SO TC: O(n root(S)) indicates 10^5 * 6720 → 10^9 ? How is the solution passing 1s limit?

12 Likes

At first sight it seems like,
Sum of the array S can go up to 10^12.
So N * sqrt(S) can go upto (10^5 * 10^6) = 10^11, which should lead to TLE.

How to prove the that the function to check if a permutation is formed does not take O(N) each time and gets amortized? Probably because the A[ i ] % x repeats soon enough?

1 Like

TIME COMPLEXITY:

O(N∗sqrt(S))
where S is the sum of the given array.

S can be of order 10^12 so how complexity is justified for given time constraints ?

3 Likes

Very poor test cases

11 Likes

We have to check factors X such that
N<X<=2e7

3 Likes

I think there should be average of S^1/3 divisors of S so the time complexity should be O(sqrt(S) + N*S^1/3). However this still goes up to 10^9. Maybe codechef did upgrade its judge

Did not get you. Why do we need to check factors of X

The maximum no of factors is 4096 for 802241960520. We can also ignore all divisors <= n and we have to ignore factors more than 2e7. Time complexity is O(N*F) where F is no of factors instead of O(N*sqrt(S)) as quoted by the editorialist. N*F is 4*10^8. TL is 1s. These operations are fast enough. Looks good to me.

7 Likes

no,sorry

number of factors of 963761198400 (<10^12) is 6720 count divisors(963761198400) - Wolfram|Alpha.

So TC: goes 10^5 * 6720 → 6.7 * 10^8 . Also % operator is no joke with 10^8 operations, i think it should have got TLE with 1 sec.

1 Like

With T=1, n=100000, choose a[i] such that sum(a[i]) - sum(i). comes out to be “963761198400” which is possible.
It’s tricky to generate array A with given sum and hoping to miss on every 6720 factors but it’s difficult to prove reverse too that worst case won’t happen, so assuming worst case Author’s solution give 5sec TLE

With T=1, n=100000, choose a[i] such that sum(a[i]) - sum(i). comes out to be “963761198400” which is possible.
It’s tricky to generate array A with given sum and hoping to miss on every 6720 factors but it’s difficult to prove reverse too that worst case won’t happen, so assuming worst case Author’s solution give 5sec TLE. Kindly have a look

Expecting TLE, I didn’t even try to attempt such approaches.
I thought the solution would be ‘elegant’, with some key observation that would somehow reduce the overall complexity to O(N) or O(NLogN).

6 Likes

Also a very nice observation is the following:

  • X should be greater than N => otherwise you cannot obtain N from a % operation
  • X should be lower than the minimum number greater than N => otherwise you will obtain a 0 or a number greater than N after the operation

So in conclusion X must be N < X < Min(Ai) where Ai > N

3 Likes

Here is a testcase which you’re trying to achieve.

Imo, it is kind of useless because restricting the number to N < X < Min(All) still only restricts it to 100,000 < N < 20,000,000, which reduces the original range by just 0.5% lol.
I too was not able to do anything further after discovering this and decided to call it a day.

Can anyone help Why am i getting TLE , i tried to do exact same thing as the editorialist did in his solution,

Code

Submission Link

#include <bits/stdc++.h>

#define ll long long int
#define pb push_back
#define PI acos(-1.0)
#define pll pair<ll,ll>
#define V vector
#define F first
#define S second

using namespace std;

const ll N = 1e5+100;
V<ll> v(N);
V<bool> used(N);
ll n, sum;
bool check(ll x){
    for(int i = 1; i <= n; i++) used[i] = 0;
    for(int i = 1; i <= n; i++){
        if(v[i]%x == 0 || v[i]%x > n || used[v[i]%x])   return false;
        used[v[i]%x] = 1;
    }
    return true;
}
void solve(){
    cin >> n;
    sum = 0;
    for(int i = 1; i <= n; i++){
        cin >> v[i];
        sum += v[i]-i;
    }
    if(sum == 0){
        cout << "YES " << n+1 << endl;
        return;
    }
    if(sum < 0){
        cout << "NO " << endl;
        return;
    }
    //cout << "SUM : "<< sum << endl;
    for(int i = 1; i*i <= sum ; i++){
        if(sum%i == 0){
            //cout << i << endl;
            if(check(i) && i <= 2e7){
                cout << "YES " << i << endl;
                return;
            }
            if(check(sum/i) && (sum/i) <= 2e7){
                cout << "YES " << sum/i << endl;
                return;
            }
        }
    }
    cout << "NO" << endl;
}

int main(){
    cin.tie(0)->sync_with_stdio(0); cout.tie(0);
    int T = 1;
    cin >> T;
    for(int i = 1; i <= T; i++){
        //cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}
for(int i = 1; i*i <= sum ; i++){
        if(sum%i == 0){
            //cout << i << endl;
            if(check(i) && i <= 2e7){
                cout << "YES " << i << endl;
                return;
            }
            if(check(sum/i) && (sum/i) <= 2e7){
                cout << "YES " << sum/i << endl;
                return;
            }
        }
    }

change int to ll in this loop . integer overflow in loop gives tle

1 Like

aur u talking about i*i <= sum portion which would be greater than 2^31-1?
just wanted to make sure that i got it.

UPD : got Accepted Thanks!!!