0

Problem Description: There are N jugs on a table and each jug has a capacity C[i]. Each jug will be filled with water such that the amount of water from Jug 1 to Jug N will be in non-increasing order. i.e. if Jug i has A[i] amount of water in it the A[i] >= A[i+1] for 1 <= i < N. What is the maximum amount of water in total that can be poured in all the jugs?

Input format: The first line contains T, number of test cases. For each test case, First line contains N, number of Jugs. Second line contains N space separated integers, C[i].

Output format: For each test case print the maximum amount of water that can be poured in the jugs in a new line.

My Code:

#include<bits/stdc++.h>
using namespace std;

int main() 

{
    int testCases;
    cin>>testCases;

    while(testCases--)
    {
        int jugs, answer = 0, minCapacity = 0, inputCapacity;
        cin >> jugs;
        
        cin >> inputCapacity;
        minCapacity = inputCapacity;
        answer = inputCapacity;

        for(int i = 1; i < jugs; i++)
        {
            cin >> inputCapacity;
            if(inputCapacity < minCapacity )
            {
                minCapacity = inputCapacity;
            }
            answer = answer + minCapacity;            
        }
        
        cout << answer << "\n";
    }
    
    return  0;
}
Shridhar R Kulkarni
  • 6,653
  • 3
  • 37
  • 57
Smit Thakkar
  • 17
  • 1
  • Sample Input: 2 4 10 4 7 3 5 1 2 3 4 5 Sample Output: 21 5 – Smit Thakkar Sep 09 '20 at 13:14
  • 1
    What are the inputs that are causing you to fail this "performance test"? It looks like you're using an `O(n)` implementation here, so I can't imagine this being "slow" without some extremely large `N`. – scohe001 Sep 09 '20 at 13:15
  • 1
    It's okay for a quick thing you do on your own, but if you show code to other people, please consider using variable names, and standard headers. We'd prefer a [mcve] which means a failing case, but I assume you don't have it. Are you getting incorrect or timeout? – Kenny Ostrom Sep 09 '20 at 13:16
  • @KennyOstrom: Coding in competitive programming is not the same as production code. So variable naming doesn't matter here. Why do you think the inputs are not being read correctly? – Shridhar R Kulkarni Sep 09 '20 at 13:26
  • 1
    *So variable naming doesn't matter here.* -- Is SO a competitive programming site? So we now have to endure trying to decipher crazy macros, non-standard header files, etc? – PaulMcKenzie Sep 09 '20 at 13:27
  • I think it was a simple loop easy enough to understand. So, variable naming didn't really matter. YMMV. – Shridhar R Kulkarni Sep 09 '20 at 13:34
  • 1
    It looks correct to me, and produces the right answer. It's the optimal algorithm. Can you link the problem so I can try it there? – Kenny Ostrom Sep 09 '20 at 13:37
  • @PaulMcKenzie: By `here` I meant "for this problem", not "on stack overflow". – Shridhar R Kulkarni Sep 09 '20 at 14:35

2 Answers2

0

The algorithm can't be better than O(N) as you will have to at least take the complete input. N is the number of elements in the input array. So, no way to further optimize the algorithm.

Now, try optimizing the code. Make the I/O faster by adding the two lines as shown below:

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ... //rest of the code as is

You can read more about the significance of the two lines here.

Shridhar R Kulkarni
  • 6,653
  • 3
  • 37
  • 57
  • What does "So, no scope in algorithmic optimization." mean? – scohe001 Sep 09 '20 at 13:47
  • OP has given `O(N)` solution which I think is algorithmically the most optimal solution. What I meant is, for this problem, we can't have any kind of algorithmic solution with sublinear complexity e.g. `O(sqrt(N))` or `O(log(N))`. If `algorithmic optimization` term is confusing here, what I meant is `time complexity`. – Shridhar R Kulkarni Sep 09 '20 at 13:51
  • My confusion is with the wording, what does "So, no scope in [thing]" mean? Are you saying there's no way to further optimize the algorithm? That turn of phrase is not one I've ever heard before. – scohe001 Sep 09 '20 at 15:20
  • "algorithmic optimization" isn't a standard term, I agree. To keep it simple, I've edited the phrase with your suggestion. One can get to hear that term more in context of "Mathematical Algorithmic Optimization" but nothing to do with it in this post. – Shridhar R Kulkarni Sep 09 '20 at 15:27
0

Here's a simple solution in Javascript,

function fillingJugs(n, arr) {
  if (arr.length === 1) {
    return arr[0]
  }
  // console.log(n, arr)
  let maxSum = 0
  let maxValue = arr[0]
//   console.log(maxSum)
  for (let i in arr) {
    // console.log('index', i)
    if (arr[i] < maxValue)
      maxValue = arr[i]
    if (arr[i] <= maxValue) {
      maxSum += arr[i]
    } else {
      maxSum += maxValue
    }
    // console.log('maxSum', maxSum)
  }

return maxSum
}

Hope this helps someone out there!

Hasan Samplewala
  • 1
  • 1
    Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Mar 07 '23 at 15:47