 # CHFICRM - Editorial

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

Cakewalk

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 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;
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 8 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';
}
}``````
6 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

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={0};
for(int i=0;i<n;i++)
{
change=v[i]-5;

if(change==0 )
{
coins++;

}
else   if(change==5 )
{
coins++;
if(coins*5>=change)
{
coins--;
}
else
{
cout<<"NO"<<endl;
coins--;
break;
}
}
else  if(change==10)
{
coins++;
if(coins*10>=change )
{
coins--;
}
else
{
cout<<"NO"<<endl;
coins--;
break;
}
}

}

int d=coins*5+coins*10+coins*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() {
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

@sebastian

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

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={0},temp,cash[n]={0},flag=1;
for(long int i=0;i<n;i++)
{
cin>>cash[i];
if(cash[i]==5)
{
arr++;
}
if(cash[i]==10)
{
if(arr>0)
{
arr–;
arr++;
}
else
{
flag=-1;
break;
}
}
else if(cash[i]==15)
{
if(arr>0)
{
arr–;
arr++;
}
else if(arr>=2)
{
arr=arr-2;
arr++;
}
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