John Matthews

Rancher
+ Follow
since Jul 04, 2018
Merit badge: grant badges
Biography
Was writing 6502 (8 bit) assembler fixed point arithmetic code (to draw circles) back in the early 80s, on an Acorn Atom if that means anything to anyone. Usually write embedded C, with the odd excursion into Java and C++.
For More
Chippenham, UK
Cows and Likes
Cows
Total received
In last 30 days
0
Forums and Threads

Recent posts by John Matthews

Campbell Ritchie wrote:

John Matthews wrote:. . . this should help: . . .

That looks useful, but I don't understand the arithmetic; it looks as if that site had written > when they meant >=.


Not what the OP wants, but I just meant something like:
Output ( https://onlinegdb.com/oRdRrwzVm ):
4 weeks ago

Stephan van Hulst wrote:It would be helpful if you told us what the behavior is that you're not expecting.


Indeed, appears to work fine (hit 'Run'): https://onlinegdb.com/ip061XjBE

You mean it behaves unexpectedly with other inputs, and if so, what are those inputs?
1 year ago
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:
1 year ago
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).
1 year ago
Can you give an example of the inputs that result in an MLE?
1 year ago

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.
1 year ago
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/
1 year ago
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.
1 year ago
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
1 year ago
Good question - I don't know, but it can be demonstrated using the Online C++ Compiler:
https://onlinegdb.com/g-czg9Hfu

Click on 'Run' and you get a compiler error. But click on 'Fork this', click on the settings cog button (top right), add -O1 to 'Extra Compiler Flags' and 'Run' again - it builds/runs fine.

The fact it can be persuaded to compile ok is probably a gcc-specific idiosyncrasy; if it didn't compile when it should then it would be a gcc bug.
1 year ago
Also, what's the priority - time efficiency (speed), memory efficiency, a combination of the 2, and/or something else?
1 year ago
Hi Frank - I've yet to venture into the world of Pi, but I'm seriously considering it; I'm getting to the age when I'm starting to think of things I can do when I retire (I'm 58)

So can you tell me what sort of spec I would need to look for in a new Pi to develop Java apps, using a decent IDE, without running out of CPU/memory/etc.?

Cheers
John
1 year ago
Corrected the indentation of the original post:
1 year ago