CKWLK - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Kasra Mazaheri

Tester: Arshia

Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Basic Math

PROBLEM:

You are playing game EVE online and Initially, you have 1 dollar. You have two cheat codes, the first one multiplies the amount of money you own by 10 and the second cheat code multiplies the amount of money you own by 20. Determine whether is it possible to own exactly N dollars through a sequence of cheat codes.

QUICK EXPLANATION

  • Let’s write N as 2^x*5^y. If it’s not possible to write in this way, we can see that we cannot obtain exactly N dollars, since No cheat code multiplies the number of dollars by any prime other than 2 or 5.
  • Now, if x < y or x > 2*y, then too there’s no way to obtain N dollars since we use cheat codes exactly y times and each cheat code increases x by either 1 or 2.

EXPLANATION

Let us analyze the cheat codes. Assuming the current number of dollars is K which is of the form 2^x*5^y

  • The first cheat code multiplies K by 10 which is the same as increasing both x and y by 1 each.
  • Second cheat code multiplies K by 20 which is same as increasing x by 2 and y by 1.

Hence, if the total number of operations applied is p, then y = p and p \leq x \leq 2*p which gives y \leq x \leq 2*y.

Hence, all N of the form 2^x*5^y can be obtained by a sequence of cheat codes where y \leq x \leq 2*y holds.

Also, if N contains any prime factor other than 2 and 5, then there’s no way to obtain exactly N dollars.

It is easy to check both cases and if the both cases are held, then we can obtain N dollars.

PS: a slightly different way to implement would be to write N in the form 2^x*10^y maximizing y first and then x and checking if the condition 0 \leq x \leq y holds.

Bonus Problem
Initially, you have X dollar and you have to apply cheat code at most N times, where each cheat code multiplies the number of dollars by any prime number in the range [1, K].

Determine whether you can obtain exactly M dollars.

TIME COMPLEXITY

Time complexity is O(log_2(N)) per test case.

SOLUTIONS:

Setter's Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	int q;
	scanf("%d", &q);
	for (; q; q --)
	{
	    ll n;
	    scanf("%lld", &n);
	    ll Pw10 = 0;
	    while (n % 10 == 0)
	        n /= 10, Pw10 ++;
	    if (__builtin_popcountll(n) != 1)
	        printf("No\n");
	    else if (__builtin_ctzll(n) > Pw10)
	        printf("No\n");
	    else
	        printf("Yes\n");
	}
}
Tester's Solution
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}

#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>

using namespace :: std;

const ll maxn=1e5+500;
const ll inf=1e9+800;
const ll mod=1e9+7;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t;
	cin>>t;
	while(t--){
	    ll n;
	    cin>>n;
	    ll a=0,b=0;
	    while(n%10==0){
	        n/=10;
	        a++;
	    }
	    while(n%2==0){
	        n/=2;
	        b++;
	    }
	    if(n!=1 || b>a){
	        cout<<"No"<<endl;
	    }else{
	        cout<<"Yes"<<endl;
	    }
	}
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class CKWLK{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    long n = nl();
	    int ten = 0, two = 0;
	    while(n%10 == 0){n /= 10;ten++;}
	    while(n%2 == 0){n /= 2;two++;}
	    if(n == 1 && two <= ten)pn("Yes");
	    else pn("No");
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new CKWLK().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

4 Likes

constraints for K in bonus problem?

What is wrong in this approach ?

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

bool recurse(ll n,ll original){
if(n==original){
return true;
}
if(n>original){
return false;
}

return (recurse(n*10,original) or recurse(n*20,original));

}

int main(){
ll t;
cin>>t;
while(t–){
ll n;
cin>>n;
ll original=n;
if(recurse(1,original)){
cout<<“Yes”<<endl;
}
else{
cout<<“No”<<endl;
}
}
}

Maybe solvable even for K = 10^{12} or 10^{18} but I intended K = 10^5

In the OR, if the first condition (n * 10) is true, the second is not evaluated. Compiler optimizations.

1 Like

so what is the problem, if first condition is true then we get some sequence for which we reach to N so at that time don’t need to check other condition.

Can u explain setter’s solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	int q;
	scanf("%d", &q);
	for (; q; q --)
	{
	    ll n;
	    scanf("%lld", &n);
	    ll Pw10 = 0;
	    while (n % 10 == 0)
	        n /= 10, Pw10 ++;
	    if (__builtin_popcountll(n) != 1)
	        printf("No\n");
	    else if (__builtin_ctzll(n) > Pw10)
	        printf("No\n");
	    else
	        printf("Yes\n");
	}
}

First If condition checks whether c is a power of 2. Second condition checks whether x-y > y

1 Like
__builtin_popcountll(n)

@taran_1407 this function checks for number of set bits, how is this checking power of 2?

1 Like

Nevermind my previous comment, I thought your recursion was going from N to 1.
I guess it overflows when your recursion goes from 10 \cdot 20^{13} = 8 \cdot 10^{17} to 10 \cdot 20^{14} = 1 \cdot 10^{19} and goes negative.

It gives number of set bits. All powers of 2 have only 1 bit set.

1 Like

Look at my solution in Python. I believe it’s extremely efficient and intuitive.

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

Why i am getting runtime error NZEC?

solution link:

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

Why it’s showing WRONG ANSWER?

#include
using namespace std;
int find(long int n)
{
if(n==10 || n==20)
return 1;
else if(n%10!=0)
return 0;
find(n/20);
find(n/10);
}
int main()
{
int t;
cin>>t;
while(t–)
{
long int n;
cin>>n;
int a=find(n);
if(a==1)
cout<<“YES”<<endl;
else
cout<<“NO”<<endl;
}
}

your find(n/20);
and find(n/10);
will never be called.
Your code will only show YES for n=10 or n=20.

Suppose there is n=30,40,50,60…
Then find(n/20) and find(n/10) is being called.
And in my editor also it’s showing correct output for almost all test cases.But codechef submission gives WA.

Change your base case to this-
if(n==original||original==1)
it will work

very nice setter solution

Hey I have a similar solution. We multiply the number with either 10 or 20 . If we keep multiplying with 10 then we can easily check by dividing the number with 10 until we get 1.
If we multiplied the no with 20 then then after removing all the zeroes from the right of the number must be a power of two. So keep dividing the number by 2 until we get 1. If we dont get one the answer is NO.

Here’s my solution

#include<bits/stdc++.h>
#define vll vector
#define ll long long
#define mp make_pair
#define pb push_back
#define mod 1000000007
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); //fast I/O
ll t;cin>>t;
while(t–)
{
ll n;cin>>n;
ll flag=1;
if(n==1)
{
cout<<“Yes\n”;
flag=0;
continue;
}
else if(n%10!=0)
{
cout<<“No\n”;
continue;
}
else
{
ll zero_cnt=0,power_cnt=0;
while(n%10==0)
{
n/=10;
zero_cnt++;
}
if(n==1)
{
cout<<“Yes\n”;
flag=0;
continue;
}
else
{
while(n%2==0)
{
n/=2;
power_cnt++;
}
if(n==1 && zero_cnt>=power_cnt)
{
cout<<“Yes\n”;
flag=0;
continue;
}
else
{
cout<<“No\n”;
continue;
}
}
}
}
return 0;
}

@taran_1407 For bonus problem, I feel 1st condition is N%X==0 and then prime factorisation of N/X should only contain primes in range [1,K].
If N/X ~ 10^12, we can prime factorise it in sqrt(N) and give answer in O((N/X)0.5) irrespective of K.
If N/X ~ 10^18, we can check all values in range [1,K], and keep on dividing it. It we have number 1, answer is yes, No other wise. complexity is O( K *or+ log(N) ) this time.
Is there any other solution i am missing?