Hello everyone!!
Consider the Fitting Shelves Problem
The solution : We can consider all multiples of “m” less than equal to “w” to find the minimum remaining space.
My claim : We only have to consider the highest or second highest multiple of “m” to find the minimum remaining space.
P.S. : I have considered m to be the larger one
Actually I have not been able to prove this but it works correctly on most of the inputs. So, any prove as to why this will work correctly or any contradictory test case that fails with this approach will be highly appreciated.
@ssjgz @taran_1407
Thanks in advance 
Your test case is also right. @sayan_000 the first integer is the width of the wall, second is m, third is n.
1 Like
Is there any way to solve this problem without iterating all the multiples of m ? I mean a solution less than linear time ? @ssjgz @taran_1407
Yes, it depends on the value of w though. If the value of w is around 10^8 it should work if there is no strict time limit. You can implement the following code.
int w, m, n, f = 0; //w, m, n as input given, f is basically a flag whether m is smaller than n or not
cin >> w >> m >> n;
if(m < n) {
swap(m, n);
f = 1; //useful in outputting the correct sequence
}
int temp = w / m, ans = INF; //INF is a really large value, say INT_MAX
//cntm stores how many m we have taken
//cntn stores how many n we have taken
//ans is the minimum section of wall which is left
//temp is the maximum m we can take
for(int cntm = temp; cntm >= 0; cntm--) {
int x = cntm * m; //this stores the section of the wall used
int tempw = w - x; //this is the section of the wall which is left
int cntn = tempw / n;
//Note: we should take maximum n for a fixed m so that the section of wall left can be minimized
tempw -= (cntn * n); //the section of wall left
if(tempw < ans) {
ans = tempw;
pos1 = cntm;
pos2 = cntn;
}
if(f == 1) {
cout << pos2 << " " << pos1 << " " << ans << endl; //outputting the correct sequence
}
else {
cout << pos1 << " " << pos2 << " " << ans << endl;
}
}
Any other solution better than O(w) I doubt exists.
Let’s assume m is larger without loss of generality
I see an O(min(w/m, n)) = O(\sqrt{w}) solution. For case 1, just iterate through all multiples of m that are less than w, and find w-im \mod n. For algorithm 2, it’s common knowledge that there are only n possible remainders when dividing by n, so iterating more will only result in a cycle, so there’s no reason to continue.
