DSA sheet / Introductory
Increasing Array
Do these first: Repetitions
The problem in brief
You get an array of n integers (n up to 200 000, values up to 10^9). In one move you may add 1 to any element. Print the minimum number of moves needed so that no element is smaller than the one before it.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1094.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
Moves only ever increase values. So if a later element is smaller than an earlier one, which of the two can you afford to change?
-
Process left to right. What is the lowest value the current element is allowed to take once everything to its left is already fixed?
-
Raising an element more than necessary never helps the elements to its right, it only makes them harder. So how far should you raise it?
-
Add up the costs. Then ask how big that total can get, and pick the integer type accordingly.
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
Start with an exchange argument. Suppose the array is 5, 2. You can only add, so the 2 must rise to at least 5, and raising it to exactly 5 is enough. Raising the 5 would be pointless because it would only make the second element need even more. The generalisation: the first element never needs to change, and each later element only needs to be lifted to the current running maximum.
That is the shape of a greedy solution: a local choice (lift to the minimum allowed) that you can prove never hurts the future. The proof habit is worth learning: “if I chose something bigger, could I always shrink it back down without breaking anything?”. Here yes.
Intuition
Picture a staircase you are only allowed to build up, never dig down. Walking left to right, the staircase height is the tallest step so far; any step that is lower gets padded with bricks up to that height. Count the bricks.
Approach
- Keep
top, the largest value seen so far, starting with the first element. - For each next element x: if x < top, add top - x to the answer (lift x to top); otherwise set top = x.
- Print the total.
Pitfalls: the total can reach about 200 000 * 10^9 = 2 * 10^14, far over 32 bits, so use 64-bit. An array with one element needs zero moves.
Complexity
O(n) time, O(1) extra memory (you can even avoid storing the array).
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
long long top = 0, moves = 0;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
if (i == 0 || x >= top) top = x;
else moves += top - x;
}
cout << moves << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n = int(data[0])
top = 0
moves = 0
for i in range(n):
x = int(data[1 + i])
if i == 0 or x >= top:
top = x
else:
moves += top - x
print(moves)
main()import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
st.nextToken();
int n = (int) st.nval;
long top = 0, moves = 0;
for (int i = 0; i < n; i++) {
st.nextToken();
long x = (long) st.nval;
if (i == 0 || x >= top) top = x;
else moves += top - x;
}
System.out.println(moves);
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
let top = 0;
let moves = 0;
for (let i = 0; i < n; i++) {
const x = data[1 + i];
if (i === 0 || x >= top) top = x;
else moves += top - x;
}
console.log(moves);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).