What is wrong in my code ? COOK107B/SLUSH

help
1

Problem : CodeChef: Practical coding for everyone

#include <bits/stdc++.h>
using namespace std;
int main()
{
long long t;
cin >> t;
while(t–){
long long n, m;
cin >> n >> m;
long long *c = new long long[m+1];
long long d[1000005];
long long f[1000005];
long long b[1000005];

    map <long long, long long> drinksLeft;

    for(long long i = 1; i <= m; i++){
        long long j;
        cin >> j;
        c[i] = j;
        drinksLeft[i] = j;
    }

    for(long long i = 0; i < n; i++){
        cin >> d[i] >> f[i] >> b[i];
    }

    long long ans = 0;
    long long *v = new long long[n];

    for(long long i = 0; i < n; i++){
        if(drinksLeft[d[i]] > 0){
            ans += f[i];
            v[i] = d[i];
            drinksLeft[d[i]]--;
        }
    }

    // for(long long i = 0; i < n; i++)
    //     cout << v[i] << " ";
    // cout << "\n";

    map <long long, long long> drinksLeft2;
    map <long long, long long> :: iterator it;
    
    for(long long i = 1; i <= m; i++){
        if(drinksLeft[i] > 0)
            drinksLeft2[i] = drinksLeft[i];
    }

    it = drinksLeft2.begin();
    for(long long i = 0; i < n; i++){
        if(v[i] == 0){
            ans += b[i];
            v[i] = it->first;
            it->second--;
            if(it->second == 0)
                it++;
        }
    }

    cout << ans << "\n";
    for(long long i = 0; i < n; i++)
        cout << v[i] << " ";
    cout << "\n";
    
}

}

1 Like
2

You are giving all the customers their preferred flavor.
In optimal solution, its not necessary since one of the preferred flavor may get exhausted due to 2nd case for maximising profit.

3

I jave applied the same logic mentioned in the editorials still I am getting WA, anyways I will try to figure out something

4

You don’t really need long long here.

5

the logic is as simple as you need to give preferred flavor to the customer on the first come first go basis, until maximum of the customers get their preferred flavor and in the end assign remaining flavor to the remaining customers in any ways.:wink::wink:

7

I thought that maximum profit could reach higher than the limits of int. BTW using long long is not the issue

8

I have used the same logic but I am not able to figure out what’s the problem in my code.

9

Your code is correct. Just that, you have taken the length of d,f and b arrays as 1000005, if you take it as 100005, it will work (i.e. one zero less). It might be because taking larger length of the array might be exceeding the maximum size the array can have.
You can read more about it here: https://www.quora.com/How-can-we-create-an-array-of-size-1-million-Or-continous-memory-allocation-of-1-million-variables

10

I am still getting a wrong answer :pensive:

11

Here are a few points you need to understand.

  1. In a function maximum allocatable memory is about 1e5 (I am kind of sure that you have written 1e6 by mistake here as otherwise your normal compiler would have also shown error)

  2. Allocating Dynamic Memory to a variable doesn’t mean that you have a value initialised for it! That depends on memory.

  • So Initialise your “v” array!
  1. After this you are gonna get TLE. (I verified it too).
    You gotta understand STL before using it!
  • map uses RBT inside as data structure which implies that moving, finding, inserting, deleting in a map take O(logn) time complexity!
    How to solve the issue?
    Simple
  1. Instead of map use, vector, vectors are just dynamic array. So travelling/inserting on/in a vector just takes O(1) time.
    (OR) By doing this second step also solves the issue
  2. I just checked, since log(n) factor just leads to a border TLE, I used
    ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
    insert this line in your code just inside int main before starting anything. These lines actually make your i/o fast. As cin/cout are slow because of the many optimisations especially for large input.
1 Like
12

This solution has been accepted. Can’t figure out the difference between the two, logic is same but approach is different.
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long t;
cin >> t;
while(t–){
int n, m;
cin >> n >> m;
int c[1000005], d[1000005], f[1000005], b[1000005], v[1000005] = {0};
for(int i = 1; i <= m; i++)
cin >>c[i];
for(int i = 0; i < n; i++)
cin >> d[i] >> f[i] >> b[i];
long long ans = 0;
for(int i = 0; i < n; i++){
if(c[d[i]] > 0){
ans += f[i];
v[i] = d[i];
c[d[i]]–;
}
}
int j = 1;
for(int i = 0; i < n; i++){
if(v[i] == 0){
ans += b[i];
while(c[j] <= 0)
j++;
v[i] = j;
c[j]–;
}
}

    cout << ans << "\n";
    for(int i = 0; i < n; i++)
        cout << v[i] << " ";
    cout << "\n";
}

}

13

Check my reply!
You will know all your faults!

14

Thanks for your help. After initialising the v array to 0 and using fast input output commands my solution got accepted. Your reply saved my hours figuring out what’s the wrong with this solution