@satwik_bhv1 : No, it is not the problem. There will be no two consecutive elements with count = 0 as he has already removed all elements with count 0 in lines 37-41. After that if count becomes 0 he moves onto next element. Problem is not in logic but in the way he implemented his logic in lines 37-41.
1 Like
try this test case
1
8 4
2 2 2 2
1 5 2
1 6 3
1 9 5
1 8 2
1 4 2
1 6 2
1 7 5
2 6 5
It gives index out of range.
4th piece becomes 0 after being assigned to the customer at index 6. Line 58 increases the index. Results in error in line 59, in while loop condition.
1 Like
can anyone have a look why this code is not working
thanks in advance
import java.util.;
import java.lang.;
import java.io.*;
class cdoff
{
public static void main(String args[])throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
ArrayList<Integer> arr = new ArrayList<>();
int T;
T = Integer.parseInt(br.readLine());
int i,j;
int sum=0;
while(T>0)
{
String input3 = br.readLine();
String[] strs3 = input3.trim().split("\\s+");
int values3[] = new int[strs3.length];
for (i = 0;i< strs3.length; i++)
{
values3[i] = Integer.parseInt(strs3[i]);
}
int N = values3[0],M=values3[1];
String input = br.readLine();
String[] strs = input.trim().split("\\s+");
int values[] = new int[strs.length];
for (i = 0;i< strs.length; i++)
{
values[i] = Integer.parseInt(strs[i]);
}
for(j=1;j<=N;j++)
{
String input2 = br.readLine();
String[] strs2 = input2.trim().split("\\s+");
int values2[] = new int[strs2.length];
for (i = 0;i< strs2.length; i++)
{
values2[i] = Integer.parseInt(strs2[i]);
}
if(values[values2[0]]!=0)
{
arr.add(values2[2]);
}else
{
sum = sum + values2[1];
values[values2[0]]--;
}
}
int count = 0;
for(i=0;i<values.length;i++)
{
count+=values[i];
}
for(i=1;i<=count;i++)
{
sum = sum + arr.remove(0);
}
System.out.println(sum);
T--;
}
}
}
Yes, found it. Thanks.
Does anyone have an idea how to solve the same problem if the constraint F > B not present?
@teja349 @taran_1407 please share your ideas
2 Likes
I also have made the same error as you in the contest, plz look into the constraints of the question, you should have taken a long or long long data type var to store the total cost in your solution.
1 Like
But sum is given less than 10^6
Edit: Sad that I misinterpreted this data 
I misread the problem statement, and for an hour, I was trying to solve a more difficult problem. I thought that the chef has liberty to decide which flavor to give to a person. In that case, he may decide whether a person gets his desired flavor or not.
My greedy solution to the problem was this: Since the total profit is ( the sum of f_i's - the total loss ). Here, the total loss is the sum of (f_i - b_i) over all i. So, we can iterate over all people in order of decreasing losses. When, we reach a person, if we can give him the desired drink, we’ll do so. Otherwise, we’ll give him a different drink at the end of iteration.
Is this a correct solution for the problem ?
what if we have last cup of Flavour i.
We give it to some person j who contributes Fj to the profit.
What if some person k (k>j) comes and asks for same flavour i,and Fk>Fj.
Will greedy solution work?
As u said i tried storing in long long but still it says WA.
You can see here:CodeChef: Practical coding for everyone
https://www.codechef.com/viewsolution/24934000
Can someone see where my solution is wrong?
I have first alloted people their favourite flavour if possible. Then I allotted all remaining flavours to the people who miss their favourite flavour.
I am getting WA.
I am getting WA, pls check this out!!!
#include
using namespace std;
int maxa(int ar[],int m)
{
int i;
for(i=0;i<m;i++)
{
if(ar[i]>0)
return i;
}
}
int main()
{
int t,i,j;
cin>>t;
while (t–)
{
int n,m;
long long prof=0;
cin>>n>>m;
int c[m],ch[m]={0},d[n],f[n],b[n],ans[n]={0},ch1[m]={0};
for(i=0;i<m;i++)
cin>>c[i];
for(i=0;i<n;i++)
{
cin>>d[i]>>f[i]>>b[i];
ch[d[i]-1]++;
}
for(i=0;i<m;i++)
{
ch1[i]=c[i]-ch[i]; //array containing extras(left) after giving maximal favourite flavours
}
for(i=0;i<n;i++)
{
int cha=c[d[i]-1];
if(cha>0)
{
c[d[i]-1]–;
prof+=f[i];
ans[i]=d[i];
// cout<<prof<<"*"<<endl;
}
else
{
ch1[maxa(ch1,m)]–;
c[maxa(ch1,m)]–;
prof+=b[i];
ans[i]=maxa(ch1,m)+1;
// cout<<prof<<"^"<<endl;
}
}
cout<<prof<<endl;
for(i=0;i<n;i++)
cout<<ans[i]<<" ";
cout<<endl;
}
}
I have written java code for the problem and it is giving TLE. Please help me out.
Here is the link to my solution.
https://www.codechef.com/viewsolution/24934001
firstly store the values to be printed in a STringBuffer and print the stringBuffer variable that will help you to avoid TLE
here is my solution in JAVA
https://www.codechef.com/viewsolution/24934017
2 Likes
I saw your solution ,try optimise it further ,found unnecessarily use of memory.
You can simply take an arrray (let say " a “) to store the drinks given to the customer.
As said earlier ,
1.In first iteration distribute fav. drinks as much as possible and store it at the same time the ones who didn’t get fav. mark them with 0.
2. In second iteration those with 0 mark pick any of the drink left and store it.
At the end print sum and this array " a” .
Simple…
In this problem order of print flavor is important?
because my one code for given input it’s gives output:
33
2 2 1 3 3
and it gets WA //https://www.codechef.com/viewsolution/24934589
and my other code gives output:
33
2 2 3 1 3
and it gets AC //https://www.codechef.com/viewsolution/24934877
I created a set of pairs which stores current quantity available and flavor number in pairs.
Whenever a flavor is given to a customer, I need to decrement the quantity of that flavor by one. Hence I am deleting the old pair and inserting the new edited pair. But on printing this modified set, some random numbers are inserted into the set.
PS. I know this approach is bad but I need to understand this behaviour of set. Can’t we modify a set like this?
//snippet of the code
if(quant[d]>0){
set<pair<int,int>>::iterator it;
it = st.find(make_pair(quant[d],d));
st.erase(it);
st.insert(make_pair(quant[d]-1,d));
flav.push_back(d);
profit +=f;
quant[d]-=1;
}
PS- here st is a set of pairs