STUPMACH Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Tester: Roman Bilyi
Editorialist: Hussain Kara Fallah

PROBLEM EXPLANATION

There are N boxes in a line (numbered 1 through N). Initially, the boxes are empty, and I need to use the machine to put tokens in them. For each valid i, the i_{th} box has a maximum capacity S_i tokens. I can perform the following operation any number of times: choose an integer L (1≤L≤N) and put one token in each of the boxes 1,2,…,L.

You must put as many tokens as possible into the boxes in total (the distribution of tokens in the boxes does not matter). Of course, it is not allowed to perform an operation that would result in a number of tokens in any box exceeding its capacity. Can you help to calculate the maximum number of tokens that can be put in these boxes?

DIFFICULTY:

Easy

CONSTRAINTS

1 \leq |N| \leq 10^6

EXPLANATION:

In the optimal solution, the maximum number of tokens that will be put in the i_{th} box would be \{min\, S_j\} among all j (1 \leq j \leq i).

The operation that we can perform is very limited, in order to put some token in i_{th} box you must put a token in every box behind it. So the number of tokens inside it mustn’t ever exceed the capacity of any box behind it.

After determining the maximum number of tokens we can put in each box, our answer is simply the sum.

Check the implementation for more details.

Editorialist solution 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        long long n , x , ans;
        cin>>n>>x;
        ans = x;
        for(int j = 1 ; j < n ; j++){
            long long q;
            cin>>q;
            x = min(q , x);
            ans += x;
        }
        cout<<ans<<endl;
    }
}
Tester Solution 
#include <bits/stdc++.h>
#define ll  int64_t
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sc second
#define fr first
 
using namespace std;
 
const int N = 2e6+100;
 
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        scanf("%d",&n);
        int a;
        ll res =0;
        int mn = 2e9;
        for(int i=0 ;i <n ;i ++){
            scanf("%d",&a);
            mn = min(mn,a);
            res += mn;
        }
        printf("%lld\n",res);
    }
    return 0;
}
2

pretty weak test cases for STUPMACH…

For test case:
7
2 5 3 1 5 3 2
answer = 10.

https://www.codechef.com/viewsolution/28550108
gives 14 as result but got AC…

4 Likes
5

@arsenic_atg
Can you tell me what’s wrong with my code? The partial answer is correct but for the other one it’s showing WA. I didn’t read the solution above but pretty sure the concept is correct. Please have a look.

Solution link-Soln

1 Like
6

your method is absolutely correct. but in some of the statements like

> int sum=min*v.size();

your value of sum is going out of integers range, thats why it was not giving correct answer.

a simple fix is to use long long int instead of int.
corrected solution

7

@arsenic_atg How could you say its answer is 14? could be please explain?
According to me its answer is coming 10.

1 Like
8

you*

9

@sneha_277 i think you are right the altered array is [2 2 2 1 1 1 1], instead of [2 3 5 1 1 1 1]. which yields correct answer as 10 not 14. my bad :sweat_smile:

1 Like
10

hi , i m absolutely new to coding platforms.
i tried to solve this question , and i think my solution is passing test cases , but the platform says wrong answer , can you please check my code and tell me whats wrong i m unable to find the mistake .

https://www.codechef.com/viewsolution/35263716

11

@disturb3d your program fails when array size is 1:
try this test case for example

1
12

here, your program should output 12, but it outputs 1.

also your algorithm is not efficient and will exceed given time limit for larger inputs.

13

Don’t know where i am doing it wrong. If somebody could help please…

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int tcs=0;
Scanner sc=new Scanner(System.in);
if(sc.hasNext())
{
tcs=sc.nextInt();
}

	while(tcs>0){
	    int nbox=sc.nextInt();
	    ArrayList<Long> alist=new ArrayList();
	    while(nbox>0){
	        alist.add(sc.nextLong());
	        nbox--;
	    }
	    int ans=0;
	    int m=1;
	   for(int j=0;;j++){
	       for(int i=0;i<alist.size();i++){
	           if(alist.get(0)==j){
	               m=2;
	               break;
	           }
	           else if(alist.get(i)==j){
	               ans=ans+i;
	               m=1;
	               break;
	           }
	           
	           else{
	               m=0;
	           }
	           
	       }
	       if(m==0){
	           ans=ans+alist.size();
	       }
	       else if(m==2){
	           break;
	       }
	   }
	   System.out.println(ans);
	    tcs--;
	}
}

}

14

What is wrong with my solution here.

void solve(int t) {
    while (t--) {    
        ll int n;
        cin >> n;
        vector<ll int> S(n);
        ll int temp;
        FOR(n) {
            cin >> temp;
            // Not taking anything beyond 0
            if (temp) 
                S[i] = temp;
            else break;
        }

        ll total = 0;
        while (not S.empty()) {
            // Find the index of the minimum element
            ll int min_value = *min_element(S.begin(), S.end());
            // You can decrease the array that many times
            total += min_value * S.size();
            // Find the index of the minimum element
            ll int minIndex = index<ll int>(S, min_value);
            // Strip the array off
            S.resize(minIndex);
            // Decrese all the elements by `min_value`
            FOR(S.size()) {
                S[i] -= min_value;
            }
        }

        cout << total;
    }
}