PROBLEM LINK:
Author: Pritish Priyatosh Nayak
Tester: Saytabrat Panda
Editorialist: Pritish Priyatosh Nayak
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
The problem is basically :
Given N and K, check if N^N \geq K.
QUICK EXPLANATION:
To avoid overflow while calculating we can print “Yes” for all cases where N \geq 16 otherwise calculate N^N manually and check the condition.
EXPLANATION:
From the constraints its clear that we need either O(1) solution or O(logN) solution.
But we cannot calculate N^N for any N \geq 16 because 16^{16} turns out to be 2^{64} and even the maximum positive number which can be stored in unsigned long long data type of C/C++ is 2^64-1.
If we actually try to calculate N^N we will run into overflow error.
Even with languages like Python it’s still not possible to calculate N^N for such large N because it will be very slow.
But K is at max 10^{18} which is less than 16^{16} , so we need to only check for N less than 16 manually and compare it with K.
If N is greater than or equal to 16, the answer is obviously “Yes”.
Alternate approach:
You could have used the fact that if N^N \geq K then Nlog(N) \geq log(K).
Using the inbuilt log functions , it could have been solved easily without having to use any short-cut tricks.
SOLUTIONS:
Setter's/Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
long long pow(long long x,long long y)
{
long long res=1;
for(long long i=1;i<=y;i++)
res*=x;
return res;
}
int main()
{
int t;
cin>>t;
while(t--)
{
long long n,k;
cin>>n>>k;
if(n>=16)
cout<<"Yes\n";
else if(pow(n,n)>=k)
cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}
Tester's Solution
import java.util.*;import java.io.*;import java.math.*;
public class Main
{
public static void process()throws IOException
{
long n=nl(),k=nl();
assert (n>1e18 || k>1e18):"N or K > 1e18";
pn((n*Math.log(n)>=Math.log(k))?"Yes":"No");
}
static AnotherReader sc;
static PrintWriter out;
public static void main(String[]args)throws IOException
{
out = new PrintWriter(System.out);
sc=new AnotherReader();
boolean oj = true;
//oj = System.getProperty("ONLINE_JUDGE") != null;
if(!oj) sc=new AnotherReader(100);
long s = System.currentTimeMillis();
int t=1;
t=ni();
while(t-->0)
process();
out.flush();
if(!oj)
System.out.println(System.currentTimeMillis()-s+"ms");
System.out.close();
}
static void pn(Object o){out.println(o);}
static void p(Object o){out.print(o);}
static void pni(Object o){out.println(o);System.out.flush();}
static int ni()throws IOException{return sc.nextInt();}
static long nl()throws IOException{return sc.nextLong();}
static double nd()throws IOException{return sc.nextDouble();}
static String nln()throws IOException{return sc.nextLine();}
static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
static boolean multipleTC=false;
static long mod=(long)1e9+7l;
static void r_sort(int arr[],int n){
Random r = new Random();
for (int i = n-1; i > 0; i--){
int j = r.nextInt(i+1);
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Arrays.sort(arr);
}
static long mpow(long x, long n) {
if(n == 0)
return 1;
if(n % 2 == 0) {
long root = mpow(x, n / 2);
return root * root % mod;
}else {
return x * mpow(x, n - 1) % mod;
}
}
static long mcomb(long a, long b) {
if(b > a - b)
return mcomb(a, a - b);
long m = 1;
long d = 1;
long i;
for(i = 0; i < b; i++) {
m *= (a - i);
m %= mod;
d *= (i + 1);
d %= mod;
}
long ans = m * mpow(d, mod - 2) % mod;
return ans;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
static class AnotherReader{BufferedReader br; StringTokenizer st;
AnotherReader()throws FileNotFoundException{
br=new BufferedReader(new InputStreamReader(System.in));}
AnotherReader(int a)throws FileNotFoundException{
br = new BufferedReader(new FileReader("input.txt"));}
String next()throws IOException{
while (st == null || !st.hasMoreElements()) {try{
st = new StringTokenizer(br.readLine());}
catch (IOException e){ e.printStackTrace(); }}
return st.nextToken(); } int nextInt() throws IOException{
return Integer.parseInt(next());}
long nextLong() throws IOException
{return Long.parseLong(next());}
double nextDouble()throws IOException { return Double.parseDouble(next()); }
String nextLine() throws IOException{ String str = ""; try{
str = br.readLine();} catch (IOException e){
e.printStackTrace();} return str;}}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}
