RED1 Editorial

PROBLEM LINK:

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

Setter: Arun Sharma
Tester: Felipe Mota, Aryan
Editorialist: Pratiyush Mishra

DIFFICULTY:

2050

PREREQUISITES:

None

PROBLEM:

Arun has an integer N. His friend Sucksum likes the number 1, so Arun wants to reduce N to 1.

To do so, he can perform the following move several times (possibly, zero):

  • Pick two integers X and Y such that X+Y is even and X^Y is a divisor of N. Then, replace N by \dfrac{N}{X^Y}

Note that at each step, X^Y only needs to be a divisor of the current value of N, and not necessarily a divisor of the integer Arun initially started with.

Find the minimum number of moves Arun needs to reduce N to 1. If it is not possible to reduce N to 1 using the given operation, print -1 instead.

EXPLANATION:

Let us tackle this problem case-wise for N, but before that we define another variable count which stores the count of power of 2 for N.

  • N = 1: Answer would be 0, since we already are at 1.
  • count = 0. Answer would be 1 since then N would be odd so we can take X = N and Y = 1. Then X+Y would be even and X^Y would be N, that is a divisor of N which would reduce it to 1.
  • count \;is\; odd: We cannot reach 1. Taking 2 here, we would observe that it cannot be reduced to 1. Similarly for any other number, we would at best reduce it to 2 and then get stuck.
  • N\;is\;a\;perfect\;square: Here we take X = \sqrt{N} and Y=2. Since X would also have a power of 2 so it would be even, thus X+Y would be even and X^Y would be N, that is a divisor of N which would reduce it to 1 so answer would be 1
  • Otherwise: We are talking about cases where N is not a perfect square and count is even. Here we would first take X = 2^{count/2} and Y=2. This would reduce N to N' that does not contain any power of 2. This would then be the same case as above so we would require one more move. Overall answer would be 2.

TIME COMPLEXITY:

O(log(N)) for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester-1’s Solution
Tester-2’s Solution

2 Likes

4^2 is 16 not 8

1 Like

4^2 = 16 and lets say you try to convert 2^X into (2^Y)^Z and you claim 2^Y + Z is even. We know 2^Y will be even so Z also needs to be even but Y*Z = X and as X is odd both Y and Z are necessarily odd, hence your claim is rejected.

1 Like

Forgive me! I miscalculated 4^2 = 8 in hurry orally and now realising my silly mistake.

3 Likes

In Explanation Section at point 2, x+y would be odd , right ??
N = odd , if x = n-1 and y = 1 so , x+y = n only which is odd.

I think x should be N and y should be 1 in this case. So x+y is even ( odd + odd = even )
and also N/x^y where x ^ y = N . So answer should be 1 only

Yes you are right. It has been corrected in the editorial.

Solution: 63810603 | CodeChef

can anyone say what is the mistake in my code??

Consider this Input:

1
36

Expected Output:

1

Your Output

2

Operation: X = 6, Y = 2. X^Y = 36 which divides 36 and X+Y = 8 which is even.

Why am I getting WA in my code ```#include
using namespace std;

pair<int, long long> largestPowOf2(long long n){
pair<int, int> p;
long long two = 2;
int ans = 0;
while(n % 2 == 0){
n /= two;
ans++;
}

p.first = ans;
p.second = n;

return p;

}

int main() {
int t;
cin>>t;

while(t--){
    long long n;
    cin>>n;
    
    if(n==1){
        cout<<"0\n";
    } else{
       if(n%2==1){
        cout<<"1\n";
       }else{
          if(largestPowOf2(n).first % 2 == 1){
            cout << "-1 \n";
          } else{
               cout << "2 \n";
            }
    }
    }
    
    
}
return 0;

}

Oh right. Thanks for the answer :slight_smile:

https://www.codechef.com/viewsolution/63856732

Can someone provide a testcase where this gives WA

Hello

I observed something in this question
If I use binary search to find square root of number , then I get WA , but when I use inbuilt sqrt to solve this problem I get AC ,

AC using inbuilt sqrt : Solution: 63859035 | CodeChef
WA using binary search : Solution: 63858803 | CodeChef

Did I do something wrong in binary search ? But the binary search code passes on leetcode problem 69. Sqrt(x)

In BInary Search, you have written

long low = 1 , high = n;

It should have been

long low = 1, high = (long)1e9;

instead.

For large N, there will be overflows. Since you are already aware that the maximum value of N is 10^{18}, you can simply take high = 10^{9}.

Accepted Submission: Solution: 63863003 | CodeChef

1 Like

Thanks a lot !

You haven’t considered the case when N is a perfect square.

can anyone please tell the mistake in my code with relevant examples

#include
#include
using namespace std;
int main(){
long long int t;
cin>>t;
for(long long int i=0;i<t;i++){
long long int n,c=0;
cin>>n;
if(n==1){
cout<<0<<endl;
}
else if(n%2!=0){
cout<<1<<endl;
}
else{
while(n%2==0){
n=n/2;
c++;
}
if(c%2==0){
if(n==1){
cout<<1<<endl;
}
else{
cout<<2<<endl;
}
}
else{
cout<<-1<<endl;
}
}
}
return 0;
}

i am getting WA in three test cases .Can anyone please tell me where I am doing mistake.
https://www.codechef.com/viewsolution/63892488

ur sollution is correct but instead of int use long long for variable m while taking sqrt