• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

How to solve the MLE in this question?

 
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I lately came through this quesiton:

Farmer John's cows have quite the sweet tooth, and they especially enjoy eating candy canes! FJ has N total cows, each with a certain initial height and he wants to feed them M candy canes, each also of varying height (1≤N,M≤2⋅10^5).
FJ plans to feed the candy canes one by one to the cows, in the order they are given in the input. To feed a candy cane to his cows, he will hang the candy cane so that initially the candy cane is just touching the ground. The cows will then line up one by one, in the order given by the input, and go up to the candy cane, each eating up to their height (since they cannot reach any higher). The candy cane stays suspended in place where it is initially set up and is not lowered to the ground, even after cows eat the bottom of the candy cane. It is possible a cow may eat nothing during her turn, if the base of the candy cane is already above that cow's height. After every cow has had their turn, the cows grow in height by how many units of candy cane they ate, and Farmer John hangs the next candy cane and the cows repeat the process again (with cow 1 again being the first to start eating the next candy cane).
Special Note: The Candy Cane floats in the air, for example when a cow with a height of 2 reaches a candy cane with a height of 3, it eats the 2 units (1 and 2), and the 3rd unit of the candy cane still floats in the air, so only cows that have a height ≥ 2 can reach and eat it.

INPUT FORMAT:
The first line contains N and M.
The next line contains the initial heights of the Ncows, each in the range [1,10^9].
The next line contains the heights of the M candy canes, each in the range [1,10^9].

OUTPUT FORMAT:
The final heights of each of the N cows on separate lines.
Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

SAMPLE INPUT:
3 2
3 2 5
6 1
SAMPLE OUTPUT:
7
2
7

Explanation:
The first candy cane is 6units tall.
1. The first cow eats the portion of the first candy cane up to height 3, after which the remaining portion of the first candy cane occupies heights [3,6].
2. The second cow is not tall enough to eat any of the remaining portion of the first candy cane.
3. The third cow eats two additional units of the first candy cane. The remaining portion of the first candy cane, occupying heights [5,6], is not eaten.

Next, each cow grows by the amount she ate, so the heights of the cows become [3+3,2+0,5+2]=[6,2,7].

The second candy cane is 1 unit tall, and the first cow eats all of it.

SCORING:

* Inputs 2-10: N,M≤10^3

* Inputs 11-14: No additional constraints.

And I came out with this solution:


Which had one Accepted and the rest were MLE. Please help! I'm a beginner
 
Rancher
Posts: 508
15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Marvin

First - apologies if this is a daft question, but what does MLE stand for?

Also, you mention inputs 2-14 - are those something you've been given that your code gives the wrong answer for? If so, it would be useful if we could see them to help work out where the code is going wrong.

Anyway, without fully understanding the problem, I can see bugs. In C++, array indices start from 0. So if you have an array defined as heightcow[n], then the valid indices are 0..n-1, not 1..n as it looks like the code assumes. I think that applies to all your arrays.

Also, your bool statcane[] array - it looks like you are only setting certain elements of the array to true in the initial loop after the statcane[] definition. Then you test statcane[] elements inside the nested loops. Might there be some statcane[] elements that are tested which haven't been set to true in the initial loop? If so, those elements that weren't set to true will have undefined values - they won't necessarily be false (and might not be true either). If you want to ensure that all statcane[] elements are false unless set to true, you could define statcane[] using:
which initialises all elements to binary 0, which is bool value false.

You can use the same = {} mechanism to initialise any numeric arrays whose elements need initialising to 0; they are undefined otherwise.

These might not be the real issues, but try fixing them and let us know if it helps.

Cheers
John
 
John Matthews
Rancher
Posts: 508
15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
One other minor suggestion - if you want a 64 bit integer type then it's best to use int64_t, defined in the cstdint header file:
https://en.cppreference.com/w/cpp/types/integer

That might be defined as a long long, but it might not; you don't have to worry about that.
 
John Matthews
Rancher
Posts: 508
15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
One more

I've never seen an include for bits/stdc++.h before, and this suggests why - it's non-standard:
https://www.geeksforgeeks.org/bitsstdc-h-c/

You can Just include standard header iostream instead.
https://cplusplus.com/reference/iostream/
 
Marshal
Posts: 4514
572
VSCode Eclipse IDE TypeScript Redhat MicroProfile Quarkus Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

John Matthews wrote:... what does MLE stand for?


Maximum Likelihood Estimation ?
 
Marvin Claw
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Ron McLeod wrote:

John Matthews wrote:... what does MLE stand for?


Maximum Likelihood Estimation ?



It meant Memory Limit Exceeded, sorry for the inconvenience.
 
Marvin Claw
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

John Matthews wrote:Hi Marvin

First - apologies if this is a daft question, but what does MLE stand for?

Also, you mention inputs 2-14 - are those something you've been given that your code gives the wrong answer for? If so, it would be useful if we could see them to help work out where the code is going wrong.

Anyway, without fully understanding the problem, I can see bugs. In C++, array indices start from 0. So if you have an array defined as heightcow[n], then the valid indices are 0..n-1, not 1..n as it looks like the code assumes. I think that applies to all your arrays.

Also, your bool statcane[] array - it looks like you are only setting certain elements of the array to true in the initial loop after the statcane[] definition. Then you test statcane[] elements inside the nested loops. Might there be some statcane[] elements that are tested which haven't been set to true in the initial loop? If so, those elements that weren't set to true will have undefined values - they won't necessarily be false (and might not be true either). If you want to ensure that all statcane[] elements are false unless set to true, you could define statcane[] using:
which initialises all elements to binary 0, which is bool value false.

You can use the same = {} mechanism to initialise any numeric arrays whose elements need initialising to 0; they are undefined otherwise.

These might not be the real issues, but try fixing them and let us know if it helps.

Cheers
John



Hello John

First of all, thank you so much for actually taking time on helping me! That's rare for me. And sorry for the inconvenience, but MLE meant Memory Limit Exceeded in this occasion. When I submitted the answer, only 1 test point was Accepted the rest were MLE. So I did not know how to optimize the code, since the triple for loops can create a 10^9 * 10^9 * 10^3 (check the question for the limits), which probably caused the MLE. I read all your comments, and surprisingly other people also said that. I'm sorry for the offense maybe, but like right now I'm aiming onto solving this question. Thank you for your help, if you know how to optimize the code can you please help me on that? On your reply, yes, inputs 2-14 has MLE. (theres only 14 test points). Also, on the arrays, I'll just leave the [0] as it is, since I think it doesn't affect the answer.

Thank you! Hope you can help me!
 
Marshal
Posts: 79255
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Never write ==true and ==false. Just if (statcane[i]) ... or if (!statcane[i]) ... please. We see lots of people who mistaken hit the equals key once only and then they don't know where their nasty bug comes from.
Please insert spaces around your binary operators; they days when code had to be squashed together to save space are a distant memory from 40 years ago.
 
John Matthews
Rancher
Posts: 508
15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Marvin Claw wrote:So I did not know how to optimize the code, since the triple for loops can create a 10^9 * 10^9 * 10^3 (check the question for the limits), which probably caused the MLE.


Ah right - thanks for the explanation. Will have a think when I get chance.
 
Campbell Ritchie
Marshal
Posts: 79255
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Maybe the problem has to do with all those nested loops.
 
John Matthews
Rancher
Posts: 508
15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Can you give an example of the inputs that result in an MLE?
 
John Matthews
Rancher
Posts: 508
15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Nested loops shouldn't cause an MLE, unless memory is being allocated within the loops and not freed, or something like that. And that's not happening here.

It might be the size of your arrays - the maximum number of cows and canes is given as 2.10^5, or 200,000. The array items are 64 bit values so each array could be 1.6MB. That might be bigger than your compiler allows for local variables, in which case you can try making them static. For example, instead of:
try:
This moves the array out of relatively limited stack memory - it has other effects too, but you don't need to worry about that for now.

Regarding optimisation (won't affect MLE), you don't need 3 levels of nested loop - the inner loop, and statcane[], can be removed. Instead, for each cane keep a record of the height of its top and bottom off the ground. The top's height is read in from the file and is fixed, but the bottom moves up as the cane is eaten.

For each cow eating a cane, work out how much of the cane will be eaten this time. If the bottom of the cane is above the cow, then none will be eaten - the cow can't reach it. But if the cow is above the bottom of the cane, it will either eat all of the cane if the cow is also above the top of the cane, or as much of the cane as it can reach if the top of the cane is above the cow.

After working out how much will be eaten, just move the bottom of the cane up by that amount, and increase the cow's height by the same amount (increase heightcow[], you don't need finalcow[]).

Let us know if that helps (and correct the bugs mentioned earlier).
 
John Matthews
Rancher
Posts: 508
15
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Perhaps a better option than making the arrays static, which as I mentioned has side effects, is to use vectors. They don't use stack memory (apart from a very small fixed amount).

For example, instead of:
use:
 
Evil is afoot. But this tiny ad is just an ad:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic