Visiting Prime Relatives (CC021) - Editorial

editorial
1

CONTEST NAME:

CODICTION 2.0

PROBLEM LINK:

Practice
Contest

Author: Vibhore Jain,Harsh Parwal
Tester: Ishita Jain
Editorialist: Vibhore Jain

DIFFICULTY:

SIMPLE

PREREQUISITES:

Prime Numbers, Basic Observation.

PROBLEM:

Mangilaal wants to meet his close relatives, there are N colonies from 1 to N with each having house numbers in a particular range [li,ri] ( both inclusive).
Mangilaal wants to visit the houses which falls in the range [L,R] ( both inclusive) and decided that he will only visit the house numbers which are prime as he is fond of prime numbers.
Print the colony number which has the maximum number of houses visited by Mangilaal. If there are no colonies he can visit, print −1.

EXPLANATION:

We will take the intersection of each colony range [l,r] with [L,R] and for every number we will check whether it is prime or not, if it is prime then we will increment the count of that colony.The colony with the maximum count, will be the answer.
For every colony we take the intersection of [l,r] with [L,R] which will be [max(l,L),min(r,R)].

Code 
 for (int i = max(l,a); i <= min(r,b); ++i)
	{
		if(isPrime(i)){
			ans++;
		}
	}
	vec.push_back(ans);

After which we will push the count of each prime visit of every colony and will print index +1 of max element of vector as we have to print the colony number of Max prime houses. If no such colony is found print -1.

COMPLEXITY

Time Complexity: O(n^3/2): Where n is the range of L to R per test case

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h> 
#define ll long long int
using namespace std;
bool isPrime(int n) 
{ 
    if (n <= 1)  return false; 
    for (int i=2; i<=sqrt(n); i++) 
        if (n%i == 0) 
            return false; 
    return true; 
} 
int solve()
{
    ll n,l,r,a,b;
    vector<ll> vec;
    cin >> l >> r >> n;
    for (int i = 0; i < n; ++i)
    {
        ll ans=0;
        cin >> a >> b;
        for (int i = max(l,a); i <= min(r,b); ++i)
        {
            if(isPrime(i)){
                ans++;
            }
        }
        vec.push_back(ans);
    }
    for(int i=0;i<vec.size();i++)
    {
        if(vec[i]!=0)
        {
            cout << max_element(vec.begin(), vec.end())-vec.begin()+1<<"\n";
            return 0;
        }
    }
    cout<<"-1\n";
    return 0; 
} 
int main()
{	
    int t=1;
    while(t--)
    {
        solve();
        cout<<'\n';
    }
    return 0;
}
Tester'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 boolean isPrime(int n)
   {
       if(n<=1)
       {
           return false;
       }
       for(int i=2;i<=Math.sqrt(n);i++)
       {
           if(n%i==0)
           {
               return false;
           }
       }
       return true;
   }
   public static void main (String[] args) throws java.lang.Exception
   {
           try
           {
                Scanner sc=new Scanner(System.in);
                int L=sc.nextInt();
                int R=sc.nextInt();
                sc.nextLine();
                int n=sc.nextInt();
                int max[]=new int[n];
                for(int i=0;i<n;i++)
                {
                    sc.nextLine();
                    int count=0;
                    int a = sc.nextInt();
                    int b = sc.nextInt();
                    for(int j=Math.max(a,L);j<=Math.min(b,R);j++)
                    {
                        if(isPrime(j))
                        {
                            count++;
                        }
                    }
                   max[i]=count;
                }
                int maximum=0;
                int ans=-1;
                for(int i=0;i<n;i++)
                {
                    if(max[i]>maximum)
                    {
                        maximum=max[i];
                        ans=i+1;
                    }
                }
                System.out.println(ans);
        } 
	    catch(Exception e) {
	    }
    }
}
1 Like