GRNDS - Editorial

editorial
,
1

PROBLEM LINK:

Author: Akshit Panday
Tester: Rutuja Deshmukh
Editorialist: Sarthak Chafle

DIFFICULTY:

CAKEWALK

PREREQUISITES:

NONE

PROBLEM:

We need to print the position of all the magical planets in the galaxy.

QUICK EXPLANATION:

You are given a number that represents the number of planets in the galaxy and an array consisting of threat level of each planet, you have to print the position of all magical planets .

EXPLANATION:

As per the given question a planet is stated as a magical planet if

  1. its threat level is greater than that of the next planet
  2. if the threat level of a planet and the threat level of the next planet has no common divisor than 1, i.e. their threat levels are coprime numbers or have GCD(Greatest Common Divisor) = 1.

we need to print the positions of all such planets, assuming that the planets are in a straight line and the galaxy has atleast 2 planets.
If no such planets exists we need to print “Wrong Signal”.

after following all the given conditions we can conclude that the last planet can never be magical.

COPRIME NUMBERS:
two integers a and b are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides one of a or b does not divide the other. This is equivalent to their greatest common divisor being 1

SOLUTIONS:

Setter's Solution 
   /* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef {
    
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCases = sc.nextInt();
        while( testCases --> 0) {
            int N = sc.nextInt();
            long[] arr = new long[N];
            for(int i=0; i<arr.length; i++) {
                arr[i] = sc.nextLong();
            }
            
            StringBuilder str = new StringBuilder();
            
            boolean isExist = false;
            for(int i=0; i<arr.length-1; i++) {
                if(arr[i] > arr[i+1] && gcd(arr[i],arr[i+1]) == 1 ) {
                    //System.out.print(i+1 + " ");
                    int res = i+1;
                    str.append(res + " ");
                    isExist = true;
                }
            }
            if(!isExist) System.out.println("Wrong Signal");
            else System.out.println(String.valueOf(str));
        }
        sc.close();
    }
    
    static long gcd(long n1, long n2) {
    if (n2 == 0) {
        return n1;
    }
    return gcd(n2, n1 % n2);
    }
}
Tester's Solution 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
    int main(){
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        bool flg=0;
        vector<ll>v(n),ans;
        for(ll i=0;i<n;i++) cin>>v[i];
        for(ll i=1;i<n;i++){
            if(v[i-1]>v[i] and __gcd(v[i],v[i-1])==1 ){
                cout<<i<<" ";
                flg=1;
            }
        }
        if(flg) cout<<"\n";
        else cout<<"Wrong Signal\n";

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

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

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t;
    cin >> t;
    while (t--) {
        ll n;
        cin >> n;
        vector<ll> arr(n);
        for (ll i = 0; i < n; i++) {
            cin >> arr[i];
        }
        bool isExits = false;
        for (ll i = 0; i < n - 1; i++) {
            if (arr[i] > arr[i + 1] && __gcd(arr[i], arr[i + 1]) == 1) {
                cout << i + 1 << " ";
                isExits = true;
            }
        }
        if (isExits == false) cout << "Wrong Signal";
        cout << "\n";
    }
    return 0;
}
3 Likes