CHFMOT18 - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: SHUBHAM KHANDELWAL
Tester: Trung Nguyen
Editorialist: Taranpreet Singh

DIFFICULTY

Cakewalk

PREREQUISITES

Basic Math

PROBLEM

You have currency coins for all even values up to N and coins valued 1, find the minimum number of coins required to pay price S.

QUICK EXPLANATION

  • If S is odd, then 1 value coin would be used.
  • While we have S > N, we can greedily use N-valued coin.
  • If there’s still some remaining price to pay, it must be even and up to N, so we can pay using 1 even-valued coin.

EXPLANATION

Firstly, since all coins except coin valued 1 are even-valued, so if S is odd, we have to use 1-value coin at least once.
Also, since we want to minimize the number of coins used, we can see that using 2 1-valued coins is worse than using one 2-value coin. So, we can see, we use 1-value coin if and only if S is odd.

So, now we can assume S is even. Now, let’s divide all even-valued coins and S by 2, The problem becomes
Find the minimum number of coins to pay price S/2, using coins with values between 1 to N/2.

It is not hard to see that we can repeatedly choose largest valued coin, till we have paid at least S. Then we can replace the last coin with an appropriately valued coin to make sum exactly S.

The minimum number of coins needed to pay at least S is given by X = \displaystyle \Big\lceil \frac{S}{N} \Big\rceil since X*N \geq S and (X-1)*N < S

So, the final answer is \displaystyle \Big\lceil \frac{S-(S \bmod 2)}{N} \Big\rceil + (S\bmod 2)

Also, during implementation, we actually do not need to divide by 2. It was just for the ease of understanding. S-(S \bmod 2) is basically subtracting 1 if S is odd.

Bonus:
What if we were given all odd valued coins and have to pay price S in minimum number of coins?

TIME COMPLEXITY

The time complexity is O(1) per test case.

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define test ll t; cin>>t; while(t--)
typedef long long int ll;
int main() {
	FIO;
	test{
	    ll s,n,ans=0,x;
	    cin>>s>>n;
	    if(s<=n){
	        if(s==1){
	            ans=1;
	        }
	        else if(s&1){
	            ans=2;
	        }
	        else{
	            ans=1;
	        }
	    }
	    else{
	        if(s&1){
	            ans++;
	            s--;
	        }
	        if(s%n==0){
	            ans+=(s/n);
	        }
	        else{
	            ans+=(s/n);
	            ans++;
	        }
	    }
	    printf("%lld\n",ans);
	}
	return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int) 1e9 + 23111992;
const ll LINF = (ll) 1e18 + 23111992;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ull isqrt(ull k) {ull r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int mrand() {return abs((int) mt());}
inline int mrand(int k) {return abs((int) mt()) % k;}
#define db(x) cerr << "[" << #x << ": " << (x) << "] ";
#define endln cerr << "\n";

void chemthan() {
	int test; cin >> test;
	assert(1 <= test && test <= 1e4);
	while (test--) {
	    int s, n; cin >> s >> n;
	    assert(1 <= s && s <= 1e9);
	    assert(2 <= n && n <= 1e9 && n % 2 == 0);
	    int res = 0;
	    if (s & 1) {
	        res++;
	        s--;
	    }
	    if (s) {
	        res += s / min(n, s);
	        if (s % min(n, s)) {
	            res++;
	        }
	    }
	    cout << res << "\n";
	}
}

int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0), cin.tie(0);
	if (argc > 1) {
	    assert(freopen(argv[1], "r", stdin));
	}
	if (argc > 2) {
	    assert(freopen(argv[2], "wb", stdout));
	}
	chemthan();
	cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class CHFMOT18{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    long S = nl(), N = nl();
	    long ans = 0;
	    
	    ans += S/N;
	    S %= N;
	    //Check 1
	    if(S%2 == 1){
	        S--;
	        ans++;
	    }
	    //Check 2
	    if(S > 0)ans++;
	    //Make sure this check 2 doesn't come before check 1, or you'll fail at cases like S = N+1
	    pn(ans);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	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 CHFMOT18().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:

2 Likes

Hi guys try this video ,
Hope it helps​:raised_hands::raised_hands:

2 Likes

Can anyone help what is wring with my code, getting correct answers for all test cases.

import java.util.Scanner;

public class Test {

public static void main(String[] args)throws Exception {
	Scanner sc =new Scanner(System.in);
	int r=sc.nextInt();
	for(int i=0;i<r;i++)
	{
		int s,n,count=0,coin1=0;
		
		s=sc.nextInt();
		n=sc.nextInt();
		
		coin1=n/2;
		
		if(s>=n)
		{
			
				count=count+(s/n);
				s=s%n;
				if(s==1 && s!=0)
				{
					count+=1;
				}
				else if(s!=0)
				{
					count+=2;
				}
		}
		else
		{
			if(s==1 || (s%2==0))
			{
				count+=1;
			}
			else
			{
				count+=2;
			}
		}
		System.out.println(count);
	}
}

}

Check My Solution :

#include<bits/stdc++.h>
using namespace std;
int main()
{
   ios_base::sync_with_stdio(NULL),cin.tie(NULL),cout.tie(NULL);
   long t;
   cin>>t;
   while(t--)
   {
      long n,s;
      cin>>s>>n;
      long ans = s/n, rem=s%n;
      if(rem==0)
         cout<<ans<<"\n";
      else if(rem%2==0 || rem==1)
         cout<<ans+1<<"\n";
      else cout<<ans+2<<"\n";
   }
	return 0;
}

Can anybody tell me what is wrong with this code getting TLE even after testing on upper bound of the constraints… Thanks in advance…
.
.
.
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define setbits(x) __builtin_popcountll(x)
#define mod 1000000007
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define inf 1e18
#define ps(x,y) fixed<<setprecision(y)<<x
using namespace std;

int main()
{
FIO;
ll t; cin>>t;
while(t–)
{
ll n,s; cin>>s>>n;
ll ans=0,flag=1;
for(int i=n;;){

	ans = s/n;
	s %= n;
	if(s==0){
	flag = 0; break;
    }
    if(i-s==1){
    	++ans; break;
	}
	
	if( (i-s)%2==1)     i = i-s-1;
	else  i -= s;
	
	
	
}
if(flag == 0) cout<<ans<<endl;
else          cout<<++ans<<endl;

}

return 0;
}

I think that’s because , the expected time complexity is O(1) and you are using some loop i guess.
Check my comment to do it in one step.
@rum3r

why else part is going to be true can u tell??

#include<bits/stdc++.h>

using namespace std;
int main()
{
long long int n,s,COUNT,T,i;
cin>>T;
while(T–)
{
cin>>s>>n;
COUNT=0;
for(i=n;i>=2;i=i-2)
{
COUNT+=s/i;
s=s%i;
if(s==0)
break;
if(s==1)
{
COUNT+=1;s-=1;
}
}
cout<<COUNT<<"\n";
}
}

whats wrong with my code it is giving TLE

`#include<bits/stdc++.h>
using namespace std;
int denomination(long long int S,long long int N,long long int COUNT)
{
if(S==1)
return COUNT+1;
if(S==0)
return COUNT;
return denomination(S%N,N-2,COUNT+S/N);

}
int main()
{
long long int s,n,t;
cin>>t;
while(t–)
{
cin>>s>>n;
cout<<denomination(s,n,0)<<"\n";
}}
`
i have tried using recursion but it is also giving TLE

You are checking for every even value from n to 2 which is not necessary , for example s=42 n=20 then you can use two 20 coins and one 2 coin ,but you are also iterating for 18,16,14,… and so on
which is not necessary,
my solution

1 Like

https://www.codechef.com/viewsolution/34831881
can any one tell me why this is giving tle and i think the logic is correct?

thanks.
I was also doing the same mistake

thank you for the reply and help but can you tell me why you r doing x=s/2

in case s is odd , in order to find greatest even integer less than s,
for example s=43 n=20 initially , new s=3 and x=s/2 => x=1 and then n=2*x(1)=>n=2

1 Like

thank you for the help now i m able to solve the question

Can anyone tell what is wrong with my code… All the testcases are correct…

n = int(input())
lst2 = []
for i in range(n):
    s, m = [int(x) for x in input().split()]
    for j in range(m, 0, -1):
        if j % 2 == 0:
            c = p = 0
            if s == 1:
                lst2.append(1)
                break
            elif s % 2 == 1:
                c += 1
                p = int(s/m)
                c = c + p + 1
                lst2.append(c)
                break
            else:
                p = int(s/m)
                c = c + p
                p = s-(p*m)
                if p > 0:
                    c = c + 1
                lst2.append(c)
                break
for i in lst2:
    print(i)

Hello,
As far as I can see, you can eliminate some variables from your code. First is the variable ‘i’ and then ‘flag’. We can eliminate ‘i’ and make use of ‘s’ for modification.
Below is a modified implementation of your code which I believe is now working. I have added comments for your understanding.
Feel free to ask if you have any questions.

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define setbits(x) __builtin_popcountll(x)
#define mod 1000000007
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define inf 1e18
#define ps(x,y) fixed<<setprecision(y)<<x
using namespace std;

int main()
{
FIO;
ll t; cin>>t;
while(t--)
{
ll n,s; cin>>s>>n;
ll ans=0;           //We don't need flag since for any number, there will be an answer available
/*for(int i=n;;){*/
while(s!=0){
    if(s==1){       //Since we are directly updating on s, we don't need i
    	s -= 1;
    	++ans; break;
	}
	ans += s/n;     //We got to try all possible even values <=n and add the result to ans
	s %= n;
	/*if(s==0){     //We have added condition inside while loop so no need of this condition
	flag = 0; break;
    }*/
    
	//check if remainder is even. 
	if(s%2==0)     n = s;   //If it is even we directly assign it to n
	else  n = s-1;          //If it is odd, we assign s-1 to n
	
	
	
}
cout<<ans<<"\n";
}

return 0;
}

One more thing, if you check your current implementation, it fails for the following test case: s = 1, n = 14.
The answer should be 1 but your code returns output as 2. Hence, I made some changes to your code.

The formula given in the explanation s - (s % 2) / n + ( s % 2) does not work for s = 31 and n = 4, as it results in the answer 8 instead of 9.

Is this correct or am I understanding it all wrong?

Thanks for your help bro… completely understood it!!
Those who are still lurking for simple solution… Here it is in its simplest form…
.
.
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define setbits(x) __builtin_popcountll(x)
#define mod 1000000007
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define inf 1e18
#define ps(x,y) fixed<<setprecision(y)<<x
using namespace std;

int main()
{
FIO;
ll t; cin>>t;
while(t–)
{
ll s,n; cin>>s>>n;
ll ans=0;
if(s&1){
++ans;
–s; // if s is odd then make it even…
}
while(s!=0){ // if even already then directly to this step
ans += s/n; //first adding quotient to the answer…
s %= n;
n = s; //as s is even its remainder will always be even and just assign it to the n
}
cout<<ans<<endl;
}

return 0;
}

Those who are still lurking for a simple solution implementation… Here it is…
.
.
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define setbits(x) __builtin_popcountll(x)
#define mod 1000000007
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define inf 1e18
#define ps(x,y) fixed<<setprecision(y)<<x
using namespace std;

int main()
{
FIO;
ll t; cin>>t;
while(t–)
{
ll s,n; cin>>s>>n;
ll ans=0;
if(s&1){
++ans;
–s; // if s is odd then make it even…
}
while(s!=0){ // if even already then directly to this step
ans += s/n; //first adding quotient to the answer…
s %= n;
n = s; //as s is even its remainder will always be even and just assign it to the n
}
cout<<ans<<endl;
}

return 0;
}