UVA - 11890 - Calculus Simplified

This article will explain my thought process to solve a problem called Calculus Simplified (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Greedy, Algebra

Objective

Given:

A math expression.
List of numbers.
Rules of the expression.
1. x to express the number.
2. + and - to express the addition and the subtraction operator.
3. ( and ) to express the grouping.

We want to:

Find the maximum possible value of the math expression.

Glossary

Greedy — A strategy to choose the locally optimal option at each step, in assumption that it will eventually lead to a globally optimal solution.
Algebra — A branch of mathematics in which arithmetical operations and formal manipulations are applied to abstract symbols rather than specific numbers.

Observation

The math expression given on this problem can also be seen as an algebraic equation. The + and - operator, when it is followed by ( grouping, behave like multiplication. The + operator won’t affect anything inside the group, but contrary to that, the - operator will flip every operator inside the group + become - and - become +). By propagating the flip effect of - operator into the grouping, we can flatten the structure of the initial algebraic equation into a variable sum formula, i.e. turning x0 - (x1 - (x2 + x3)) into x0 - x1 + x2 + x3.

After we have discovered the variable sum formula, the next part is to find the assignment of numbers that can produce the maximum amount of result. Based on the sum formula, we have 2 types of variables: positive and negative. We can use greedy approach to maximize the result, which is by assigning the greatest numbers into the positive variables and assigning the lowest numbers into the negative variables.

Algorithm

To evaluate the math expression, we can iteratively scan each letter. To propagate the effect of an operator (+ and -) inside a grouping (( and )), we could keep track of relevant operators using a stack. Every time - operator is added or removed from the stack, it will flip the state of the following operators.

After we have discovered the positive and negative state of each variables, the next part is to assign the numbers into it. This can be done effectively by sorting the numbers and storing the result in a dequeue. The head part of the dequeue contains the lowest unused number and the tail part of the dequeue will contains the greatest unused number. As we evaluate the math expression, assign the lowest number into the negative variable and the greatest number into the positive variable.

The time complexity of this solution is O({total numbers} * log2({total numbers})) or O(10^6).

Implementation

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;

/**
 * 11890 - Calculus Simplified
 * Time limit: 2.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2990
 */
public class Main {
    public static void main(final String... args) {
        final Scanner in = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        final Process process = new Process();

        final int totalTests = in.nextInt();
        for (int i = 0; i < totalTests; i++) {
            final Input input = new Input();
            input.expression = in.next();
            input.totalNumbers = in.nextInt();
            input.numbers = new int[input.totalNumbers];
            for (int j = 0; j < input.totalNumbers; j++) {
                input.numbers[j] = in.nextInt();
            }

            final Output output = process.process(input);
            out.println(output.maximumValue);
        }

        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public String expression;
    public int totalNumbers;
    public int[] numbers;
}

class Output {
    public int maximumValue;
}

class Process {
    public Output process(final Input input) {
        final Output output = new Output();
        output.maximumValue = 0;

        final Deque<Integer> numbers = new LinkedList<>();
        final Stack<Character> letters = new Stack<>();
        boolean negative = false;

        Arrays.sort(input.numbers);
        for (final int number : input.numbers) {
            numbers.addLast(number);
        }

        for (final char letter : input.expression.toCharArray()) {
            switch (letter) {
                case '(':
                case '+':
                    letters.add(letter);
                    break;

                case ')':
                    letters.pop();

                    if (letters.empty()) {
                    } else if (letters.peek() == '+') {
                        letters.pop();
                    } else if (letters.peek() == '-') {
                        letters.pop();
                        negative = !negative;
                    }
                    break;

                case 'x':
                    if (negative) output.maximumValue -= numbers.removeFirst();
                    else output.maximumValue += numbers.removeLast();

                    if (letters.empty()) {
                    } else if (letters.peek() == '+') {
                        letters.pop();
                    } else if (letters.peek() == '-') {
                        letters.pop();
                        negative = !negative;
                    }
                    break;

                case '-':
                    letters.add(letter);
                    negative = !negative;
                    break;
            }
        }

        return output;
    }
}