Mini-project Part 3: One Problem, Three Approaches

This project takes one problem and solves it three times: with brute force (Chapter 11), with greedy (Chapter 12), and with dynamic programming (Chapter 13). The goal is to see directly how the three differ — in speed and in correctness.

The problem

Picking mangoes. Along a fence stand n mango trees in a row. Tree i bears a[i] mangoes. Pak Dengklek may pick from any tree he likes, but not from two adjacent trees (he would get caught). What is the largest number of mangoes he can pick?

Input. The first line is n. The second line is n integers a[1..n].

Output. One number: the largest number of mangoes.

Constraints. Subtask 1 (30 points): n ≤ 20. Subtask 2 (30 points): n ≤ 5,000. Subtask 3 (40 points): n ≤ 1,000,000. All 0 ≤ a[i] ≤ 10⁹.

Sample input:

6
5 1 8 2 9 3

Sample output:

22

Explanation: pick trees 1, 3, and 5 → 5 + 8 + 9 = 22.

What to build

Three functions in one file, plus measurement and comparison.

  1. brute(n) — go through all 2ⁿ ways of choosing trees, discard those that are adjacent, take the largest sum. Used only for n ≤ 20.
  2. greedy(n) — repeatedly take the tree with the most fruit that may still be picked, then mark both of its neighbors as forbidden. This approach is wrong. Your task is to find a test case that proves it.
  3. dp(n) — dynamic programming, O(n).

Then, in main:

  • Read the input, print the answer of the dp version (this is the answer submitted to the judge).
  • Add a tester section: generate random arrays of size n ≤ 12, compare all three, and print the first test case that makes greedy differ from brute.
  • Measure the time of brute and dp for n = 22, then the time of dp for n = 1,000,000.

DP hints

Answer the five questions from Chapter 13 before writing code:

  1. State. dp[i] = the largest number of mangoes when considering only the first i trees.
  2. Base case. dp[0] = 0, dp[1] = a[1].
  3. Transition. For tree i there are two choices — not picked (dp[i-1]) or picked (dp[i-2] + a[i]). Take the larger.
  4. Order. From small to large.
  5. Answer. dp[n].

Other hints

  • The number of mangoes can reach 10⁶ × 10⁹ = 10¹⁵. Use long long.
  • For n = 1,000,000, the array must be global.
  • brute with n = 22 goes through 4 million subsets. If the "are there two adjacent bits" check is done first (mask & (mask >> 1)), most of them are discarded immediately and the time is still under a tenth of a second. Raise it to n = 30 and feel the difference: the number of masks becomes 256 times larger.

What to report

Write these as a comment at the top of your file:

  • the smallest test case that makes greedy wrong, together with both answers;
  • the time of brute and dp for n = 22;
  • the time of dp for n = 1,000,000;
  • how many points you would get if only brute were submitted, and how many if only dp.

Files

Compile and run:

g++ -std=c++17 -O2 -o mangga projects/03-tiga-pendekatan/starter.cpp
./mangga < projects/03-tiga-pendekatan/contoh-masukan.txt

Done?

If all three functions run, you have a test case that makes greedy wrong, and you can explain why DP is not affected by the same problem — this project is finished.

Continue to Chapter 14 — Modulo and its theorems, where the mathematics of OSN problems starts to be covered on its own.