Can't understand the implementation of MAGICMOD solution

help
, ,
#1

i am having a hard time in understanding the below code

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

Things i didn’t understood

  1. why are we cheching the condition for s<0
    doesn’t it means that Q’<0 (considering here s represents Q’) which is not possible?

  2. why answer is n+1 when s=0

  3. why we have to check again in check function for the condition s%x!=0? isn’t it already handled in the for loop of solve function?

  4. the following part of check function

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

  1. s < 0 implies there is no suitable X > 0 and hence we print “NO”

  2. I think test cases were weak. We should first check that there are no duplicates in the array. And if there aren’t any, then s = 0 implies that array is already a permutation and hence any number > n works well as our X. I was surprised and sad that above code passed. @munch_01 please do point out if I am mistaken, but following is the case where mentioned code gives wrong answer :

   1
   3
   1 1 4

   Answer should be a "NO" but because $s = 0$ above code outputs a "YES".

  1. Yes, you are right. We didn’t have to. People don’t usually improve code after an AC.

  2. We have to check if the given x can be our X or not. for that we have to check \forall i\ 0 < (a[i] \ \% \ x) \le n and vis[a[i]\ \% x] = false. Mentioned code is the negation of this logic and when it is true we return false.

#3

thanks
it was a very good explanation

1 Like