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.
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:
Now, if we subtract the Sum_R from the given array A, we will be left with the sequence:
Now let’s say:
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
Hence Q` is nothing but just
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;
}