PERMGCD - Editorial

editorial
,
1

PROBLEM LINK:

Contest
Practice

Setter: tejas_adm
Testers: utkarsh_25dec, iceknight1093

DIFFICULTY:

1328

PREREQUISITES:

None

PROBLEM:

Find a permutation of [1, N], so that the sum of prefix-GCDs is exactly X.

EXPLANATION:

GCD of positive numbers is always \ge 1. So the sum of N of the prefix-GCDs is going to be \ge N. So, if X < N, there is no answer, and hence output -1.

For all other cases, we can construct a permutation. We see from the input constraints that X is guaranteed to be \le 2*N - 1. So, we can place a suitable element at the first, and then a 1, and the rest in any order. In such a case, the GCD of all prefixes except the very first is 1. So, the first element has to be X-(N-1). So the permutation is [X-(N-1), 1, 2, 3, \dots, N], taking care that the first element isn’t repeated twice.

TIME COMPLEXITY:

Time complexity is O(N).

SOLUTION:

Editorialist's Solution 
#include <iostream>
using namespace std;

int T, n, x;

int main() {
	
	cin>>T;
	
	while(T--)
	{
	    cin>>n>>x;
	    if(x<n)
	    {
	        cout<<-1<<"\n";
	        continue;
	    }
	    x -= (n-1);
	    cout<<x<<" ";
	    for(int i=1;i<=n;i++)
	    {
	        if(i==x)
	            continue;
	        cout<<i<<" ";
	    }
	    cout<<"\n";
	}

	return 0;
}
Setter's Solution 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n, x;
        cin >> n >> x;
        if(x < n) {
            cout << "-1\n";
            continue;
        }
        int now = 1, done = x - n + 1;
        cout << done << " ";
        for(int i = 1; i < n; i++) {
            if(now == done) now++;
            cout << now << " ";
            now++;
        }
        cout << "\n";
    }
}
Tester's Solution 
for _ in range(int(input())):
	n, k = map(int, input().split())
	if k < n:
		print(-1)
	else:
		print(k-n+1, *range(1, k-n+1), *range(k-n+2, n+1))
1 Like
2

Hello I am very curious about what can we do if the following constraint was not given:-

1 <= X <= 2.N - 1

Example :- N = 4, X = 8 —> 4, 2, 3 , 1.

(I was thinking maybe we have to map the gcd or something.)
Hope somebody can clear it up.
Thank you for your attention.

2 Likes
3

Editorialist’s solution say the max sum will be (2 *n ) - 1.
i cant see that for example:-
n = 12, x = 32
s = [12, 8, 4, 2, 6, 10, 1, 3, 5, 7, 9, 11]
sum = 12 + 4 + 4 + 2 + 2 + 2 + 1 + 1 + 1 +1 + 1 + 1 = 32
now if i checked for (32 - 12 + 1) = 21 > 12 solution will give answer = -1.
please @admin check it

1 Like
5

It’s not claimed that that is the maximum possible sum. But it is given in the input constraints of the problem statement that X will not be more than that. Hence we need to worry only about those inputs.

6 
#include<iostream>
#include<vector>
#include<climits>
#include<string>
#include<algorithm>
#define ll long long 
using namespace std;

int main(){
      ll int t=0;
      cin>>t;
      while(t--){
      	 int n=0,s=0;
      	cin>>n>>s;
      	 int original =n;
         vector<int>perm;
         if(n%2==0){
         	int temp = INT_MIN;
        if(s%2==0)
        {
         perm.push_back(s-n);
          temp=0;
         temp=s-n;}
         for(int i=n;i>1;i=i-2)
         if(i!=temp)
         perm.push_back(i);
         n=n-1;
         for(int i=n;i>1;i=i-2)
         perm.push_back(i);
         perm.push_back(1);
		}
		else{  //n is odd;
			for(int i=n;i>1;i=i-2)
			perm.push_back(i);
			n=n-1;
			for(int i=n;i>1;i=i-2)
			perm.push_back(i);
			perm.push_back(1);
		}
		ll int sum=0;
		int ans=0;
		 int result = perm[0];
		 int idx=0;
		 vector<int>gcds;
		 gcds.push_back(result);
      for(int i=1;i<perm.size();i++)
      {
        sum = __gcd(gcds[idx],perm[i]);
        gcds.push_back(sum);
        idx++;
        sum=0;
        
	  }
	   ans=0;
	  for(int i=0;i<gcds.size();i++)
	  ans = ans+gcds[i];
	  
	  
     

       	if(original==s and original!=1)
       	{
       		for(int i=1;i<=original;i++)
       		cout<<i<<" ";
		   }
       else if(ans==s)
       {
       	for(int i=0;i<perm.size();i++)
       	cout<<perm[i]<<" ";
		}
		
		else if(original>s)
		cout<<-1;
		else
		cout<<-1;
       	cout<<endl;
       	perm.clear();
       	gcds.clear();
       	original=0;
      
	
	 
}
	  

}

Can anyone tell on what test case it is failing ?

7

@admin

9

That is not 2 raised to the power n, but 2 multiplied by n
then according to this, the max value of x is 23.