Table of Contents

ExplanationImplementation

Official Editorial

Explanation

The first thing we have to notice here is that we can get the minimum number of seconds by doing the bare minimum to make the sequence increasing. If we have a number that's less than its predecessor, there's no reason to make that number greater than what comes before it.

With that out of the way, we know how much we should add to each number. To get the overall minimum number of seconds to make the sequence nondecreasing, we can take the floors of the log base 2 of each number and add 1.

Implementation

Time Complexity: O(n)\mathcal{O}(n) for each test case.

C++

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


int main() {

Java

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


public class PoweredAddition {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int testNum = io.nextInt();
		for (int t = 0; t < testNum; t++) {
			int size = io.nextInt();
			int[] arr = new int[size];

Python

from math import log2


for _ in range(int(input())):
	size = int(input())
	arr = [int(i) for i in input().split()]
	assert len(arr) == size


	target = [arr[0]]
	to_add = []
	for i in range(1, size):

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum