Defective jugs C++ solution question . Don't understand the condition being checked


#1

Hi,
I have questions on the c++ solution part of the defective jugs. I understand the main idea but I don’t understand why checking 1) L<H (highlighted in bold fonts) and also 2) L <= j.low && j.high <= H :

bool CheckFeasibleHelper(const vector& jugs, int L, int H,
unordered_set<VolumeRange, HashVolumeRange>* c) {
if (L > H || c->find({L, H}) != cend(*c) || (L < 0 && H < 0)) {
return false;
}

// Checks the volume for each jug to see if it is possible.
if (any_of(begin(jugs), end(jugs), [&](const Jug& j) {
std::cout<<"checking jug: “<<j.high<<”, "<< j.low <<std::endl; // I added code here to trace
return (L <= j.low && j.high <= H) ||
CheckFeasibleHelper**(jugs, L - j.low, H - j.high,** c);
})) {
return true;
}
c->emplace(VolumeRange{L, H}); // Marks this as impossible.
return false;
}

For the 1st condition, If I call the function with:
int new_L = min(jugs, L - j.low, H - j.high);
int new_H = max(jugs, L - j.low, H - j.high);
…CheckFeasibleHelper(jugs, new_L, new_H,c);

So I force the range value here and L<=H alway is satisfied. Will this approach equal to the correct solution?

For the 2nd condition, I thought it is to check if the volume falls into one jug measuring range.But why j.high <= H ?

There is a 3rd problem. The test framework reads Jug data struture from test_data as [low,high] and the real data seems to be [high,low]
The test case:
array(tuple(int[low], int[high])[jug]) int[L] int[H] bool
[[27, 23], [52, 39]] 1892 1900 true TODO

The print out from the line shows :checking jug: 23, 27. lldb also confirms that:
p jugs
(const std::__1::vector<Jug, std::__1::allocator >) $0 = size=2 {
[0] = (low = 27, high = 23)
[1] = (low = 52, high = 39)
}

So from this point, L <= j.low && j.high <= H is really checking ( from the real data input)
L <= j.high && j.low <= H? I’m pretty confused here…

Thank you.


#2

L > H is just an impossibility check (also boundary condition in this DP problem).

For your question about making L <= H always satisfied, you can use framework to verify that, and I think it is not work.

And you are right about the test data problem, it definitely is broken, and I will fix it and push it in the next release.


#3

Yea…I checked the framework with test data. If I make the L< H condition always satisfied as I mentioned in the message, the judge data also passes. So it looks like L<H is not a hard constraint.

But maybe it also has something to do with the fact that readout from the test data file for jug volume capability is wrong.


#4

I think there is some problem of the test data and I am fixing that test data.