CHFICRM - Editorial

PROBLEM LINK:

Contest Link

Author: Raja Vardhan Reddy
Tester: Felipe Mota
Editorialist: Rajarshi Basu

DIFFICULTY:

Cakewalk

PREREQUISITES:

Implementation

PROBLEM:

There exists 3 denominations, Rs 5, Rs 10 and Rs 15. Each ice-cream costs Rs 5. There are N customers. Each customer has a certain denomination with him. He buys an ice-cream from Chef only if Chef can give him change. Chef initially has no money. Can all the customers buy their ice-cream?

EXPLANATION:

Simulate the process!

Keep two counters, cnt_5 and cnt_{10}, both initially 0. When a customer comes, see if you can provide change using the two counters.

The best strategy here is to give a change of Rs 10 whenever possible, and if not possible, then give Rs 5. In some sense, Rs 5 is a more “flexible denomination” than Rs 10 – you can form both Rs 5 and 10 denominations from Rs 5, but you cannot give a change of Rs 5 if you only have Rs 10 denominations. Hence, you want to save them (i:e Rs 5) as much as possible.

If you can’t give the change using Rs 10 and Rs 5 then exit, if you can then continue processing the next customer. Don’t forget to increase the counter for whichever denomination you get after the transaction.

NOTE: We dont need a counter for Rs 15 since we cannot use it as change ever.

SOLUTIONS:

Setter's Code
//raja1999
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
 
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
 
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
 
//std::ios::sync_with_stdio(false);
 
main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t,t1;
	cin>>t;
	t1=t;
	while(t--){
		int n,c=0,c1=0,c2=0,i,x,a[1005];
		cin>>n;
		rep(i,n){
			cin>>a[i];
		}
		rep(i,n){
			x=a[i];
			if(x==5){
				c++;
			}
			else if(x==10){
				if(c==0){
					break;
				}
				else{
					c--;
				}
				c1++;
			}
			else{
				if(c1==0 &&c<=1){
					break;
				}
				else if(c1!=0){
					c1-=1;
				}
				else if(c>=2){
					c-=2;
				}
			}
		}
		if(i==n){
			cout<<"YES"<<endl;
		}
		else{
			cout<<"NO"<<endl;
		}
	}
	return 0;
} 
 
Tester's Code
t = int(raw_input())
while t > 0:
    n = int(raw_input())
 
    q5, q10 = 0, 0
    is_ok = True
    coins = map(int, raw_input().split())
    for coin in coins:
        if coin == 5:
            q5 += 1
        elif coin == 10:
            q10 += 1
            if q5 > 0:
                q5 -= 1
            else:
                is_ok = False
        else:
            if q10 > 0:
                q10 -= 1
            elif q5 >= 2:
                q5 -= 2
            else:
                is_ok = False
    
    print "YES" if is_ok else "NO"
 
    t -= 1 

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

4 Likes
#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        int n5=0,n10=0,n15=0,nG;
        string ans = "YES";
        
        while(n--){
            cin >> nG;
            if(nG==5)n5++;
            if(nG==10)n10++,n5--;
            if(nG==15){
                n15++;
                if(n10>0)n10--;
                else n5-=2;
            }
            if(n5<0 || n10<0)ans = "NO";
        }
        cout << ans << '\n';
    }
}
4 Likes

June long challenge editorial beginner friendly video explanation and code

Delicious cake (CONTAIN) : https://youtu.be/tXD2yEVA0pM
Tom and jerry (EOEO) : https://youtu.be/ZWI5n0Ogir0
Even matrix (EVENM) : https://youtu.be/KA8WoO7jCg8

oh…yeah

video explanation>>>

1 Like
#include <iostream>
#include<string>
#include<cmath>
#include<bits/stdc++.h>
#define ll long long
#define PI 3.14
#define pb push_back
#define pob pop_back
#define sv(a) sort(a.begin(),a.end())//sorting for vector//
#define sa(a,n) sort(a,a+n)//sorting for array//
#define MOD 1000000007
#define fi first
#define se second
using namespace std;

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
ll t,n;
cin>>t;
while(t--)
{
   cin>>n;
   int v[n];
  int change;
 for(int i=0;i<n;i++)cin>>v[i];
 int coins[3]={0};
   for(int i=0;i<n;i++)
   {
       change=v[i]-5;
       
    if(change==0 )
    {
        coins[0]++;
       
    }
    else   if(change==5 )
    {
        coins[1]++;
        if(coins[0]*5>=change)
        {
            coins[0]--;
        }
        else
        {
        cout<<"NO"<<endl;
    coins[1]--;
        break;
       }
    }
     else  if(change==10)
    {
        coins[2]++;
        if(coins[1]*10>=change )
        {
            coins[1]--;
        }
        else
        {
        cout<<"NO"<<endl;
         coins[2]--;
        break;
       }
    }
    
      
      
   }
       
  int d=coins[0]*5+coins[1]*10+coins[2]*15;
   if(d==(n*5))
   {
       cout<<"YES"<<endl;
   }
      
        
       
    
}

 return 0;
}
``` this is partially correct and my seocnd constraint goes wrong but how?pls help whats wrong?
t = int(input())
for i in range(t):
    n = int(input())
    l = [int(i) for i in input().split()][:n]
    five_count = 0
    ten_count = 0
    result = True
    for j in range(n):
        if l[j] == 5:
            five_count += 1
        elif l[j] == 10:
            ten_count += 1
            if five_count > 0:
                five_count -= 1
            else:
                result = False
        else:
            if five_count >= 2:
                five_count -= 2
            elif ten_count > 0:
                ten_count -= 1
            else:
                result = False

    if not result:
        print("NO")
    else:
        print("YES")

Can anyone help what is wrong in this code? Subtask 2 is not working correctly.
Solution: https://www.codechef.com/viewsolution/34465806

pls see what is wrong in this? @sebastian

You can see this

Code
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define lld long long int 

int main() {
	// your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int arr[n];
        for(int i=0;i<n;i++)
        cin>>arr[i];
        
        int i,cnt5=0,cnt10=0;
        for(i=0;i<n;i++)
        {
            if(arr[i]==5)
            cnt5++;
            
            if(arr[i]==10)
            {
                if(cnt5>0)
                {
                    cnt10++;
                    cnt5--;
                }
                else
                break;
            }
            
            if(arr[i]==15)
            {
                if(cnt10>0)
                cnt10--;
                
                else if(cnt5>1)
                cnt5-=2;
                
                else
                break;
            }
        }
        if(i==n)
        cout<<"YES\n";
        else
        cout<<"NO\n";
    }
}

If you didn’t understood then ask. You are not considering the case when you can give 2 five coins when user gives 15.

1 Like

Why is my subtask 2 wrong? I have considered the case of two five-rupee coins when buyer givers Rs 15. Please help me out

@sebastian

At least send submission link.

I think you should first take condition of giving single coin of 10 in case of 15.

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

Okay let me try.

correct answer now! Oh yes! i should save more of 5 as it is flexible. Thank you so much for helping me out!

1 Like

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
long int n;
cin>>n;
long int arr[3]={0},temp,cash[n]={0},flag=1;
for(long int i=0;i<n;i++)
{
cin>>cash[i];
if(cash[i]==5)
{
arr[0]++;
}
if(cash[i]==10)
{
if(arr[0]>0)
{
arr[0]–;
arr[1]++;
}
else
{
flag=-1;
break;
}
}
else if(cash[i]==15)
{
if(arr[1]>0)
{
arr[1]–;
arr[2]++;
}
else if(arr[0]>=2)
{
arr[0]=arr[0]-2;
arr[2]++;
}
else
{
flag=-1;
break;
}
}
}

    if(flag==1)
    {
        cout<<"YES\n";
    }
    else
    {
        cout<<"NO\n";
    }
}

}

Can someone help me to find why i am getting wrong answer ?

why we taking rs 10 variable extra if we can pay rs 15 exchange from total or from rs 5??

there are two mistakes:
first, the decrement operator should be like - - instead of -

second, your code does not takes all necessary inputs i.e. breaking loop without taking all inputs
I had the same problem so I made a loop for taking pseudo input

see this : https://www.codechef.com/viewsolution/33699739

although your logic is correct

see the second loop

https://www.codechef.com/viewsolution/34086655
my first subtask is giving wrong answer while second runs just fine.
what did i do wrong. please help.
@sebastian @devdatta2512