Problem solving paradigms

Problem solving paradigms

Four Common Problem Solving Paradigms

• Complete Search (Brute Force)
• Divide and Conquer
• Greedy
• Dynamic Programming

Given a simple task involving an array A with up to 200K positive integers whose value can be up to 1M.

• Find the largest and small values in A.
  • Complete Search: O(n)
• Find the k^th smallest element in A
  • Complete Search: O(n²)
  • Divide and Conquer: O(nlog(n)) or O(n)
• Find two numbers in A that have the largest absolute difference
  • Complete Search: O(n²)
  • Greedy (largest gap is the difference between max and min): O(n)
• Find the longest increasing subsequence of A
  • Complete Search: O(2ⁿ)
  • Greedy and D&C: O(nlog(k))
  • Dynamic Programming: O(n²)

Strategies

• Estimating expected run time.
• Complete Search if quick and bug-free solution development is a possibility
  • Will have TLE but no WA

Problem size	Worst accepted algorithm
≤ [10..11]	O(n!), O(n6)
≤ [17..19]	O(2n * n2)
≤ [18..22]	O(2n * n)
≤ [24..26]	O(2n)
≤ 100	O(n4)
≤ 450	O(n3)
≤ 1.5K	O(n2.5)
≤ 2.5K	O(n2log(n))
≤ 10K	O(n2)
≤ 200K	O(n1.5)
≤ 4.5M	O(nlog(n))
≤ 10M	O(nlog(log(n)))
≤ 100M	O(n), O(log(n)), O(1)

Improving Complete Search: Iterative Complete Search

• UVa Division
• Summary: Find all pairs of 5-digit numbers that use the digits 0 through 9 each such that the first number divided by the second number is equal to N with 2 ≤ N ≤ 79: abdef/fghij = N
• Naive Complete Search:
  • Both numbers are permuted from 10 digits (no replacement): 10! iterations ~ 3M
• Analysis:
  • Max possible value: 98,765
  • Denominator fghij: max value = 98,765 / N, which is at most 49,382
  • Instead of checking pairs, go through all possible values of fghij and check if fghij * N is a numbers whose digits combining with fghij’s digits match 0 through 9 (bit masking technique):
    • Recall: to set (turn on) the bit at position j, use bitwise OR: S = S | (1 << j)
  • Time complexity: ~ 49,382 * 10 ~ 500K (comparing to 3M)

Improving Complete Search: Looping and Pruning

• UVa Simple Equations
• Summary: Find distinct integers x, y, and z such that
  • x + y + z = A
  • x * y * z = B
  • x² + x² + x² = C
  • 1 ≤ A, B, C ≤ 10,000
  • Answer should prefer x with least value, then y.
• Naive Complete Search:
  • Worst case: 10000³
• Analysis:
  • With x² + x² + x² = C, we can deduce that x, y, z is between -100 and 100.
    • Worst case: 200³
  • Further deduction: x, y, z ≤ B^1/3, therefore one value is between -22 and 22.
    • Worst case: 45 * 200²

• Additional optimizations to scale loop size with input.

Iterative Complete Search: Permutations

• UVa 11742 Social Constraints
• Summary:
  • There are 0 ≤ n ≤ 8 movie goers, seating in n consecutive open seats.
  • There are 0 ≤ m ≤ 20 seating constraints, where each constraint specifies two movie goers a and b has to be at least c seats apart.
  • How many possible seating arrangements are there?
• Permutations:
• Have to search through all possible permutations and check if each permutation satisfies
• The problem of next_permutation.
• Example:
  • LeetCode’s Next Permutation
• Applying the technique:
  • ILeetCode’s Permutation Sequence

Recursive Complete Search: Backtracking

• UVa 00750 8 Queens Chess Problem
• Summary:
  • In chess it is possible to place eight queens on the board so that no one queen can be taken by any other.
  • Write a program that will determine all such possible arrangements for eight queens given the initial position of one of the queens.
• Naive complete search:
  • Enumerate all possible combinations of 8 different cells out of 8x8 = 64 possible cells on a chess board.
  • Runtime: C(64,8) = 64! / (8! * 56!) ~ 4B
  • Don’t even think about it.
• Naive row pruning:
  • Each Queen can only occupy one column.
  • Runtime: 8⁸ ~ 17M
  • Likely to be TLE
• Faster row/column pruning:
  • Each Queen control one row and one column.
  • Runtime: 8! ~ 40K
  • Fast enough but could be better.
• Row/column/diagonal:
  • Queen cannot share diagonal lines.
  • Runtime: sub (8!)

Challenges

• Kattis: Eight Queens
  • Simpler problem that focuses on data input and checking.
• Kattis: Queens
  • A variety of both UVA and the Kattis’ 8queens problem.
• LeetCode: N-Queens.

Complete Search Tips:

• Filtering versus Generating:
  • Filtering:
    • examine a lot (if not all) candidate solutions and choose the ones that are correct.
    • written iteratively.
  • Generating:
    • gradually build the solutions and immediately prune invalid partial solutions.
    • written recursively.
  • Filtering is easier to code but run slower.
• Prune infeasible/inferior search space early.
• Utilize symmetries.
• Pre-computation: generate lookup tables (data structures)
• Solve the problem backwards.
• Data compression (bit masking).
• Optimize source code.
• Use better data structures/algorithms.

Divide and Conquer (D&C):

• Divide the original problem into sub-problems, usually by half or nearly half.
• Find (sub-)solutions for each of these sub-problems, which are now easier.
• If needed, combine the sub-solutions to get a complete solution for the main problem.
• Most well-known: Binary Search

D&C Binary Search: Uncommon Data Structures

• Common usage of Binary Search: to search a static sorted array.
• Problem (Thailand ICPC National Contest 2009)
  • Given a weighted tree of up to N vertices with one condition: vertex values are increasing from root to leaves.
    • The tree is not necessarily binary
  • For each of Q starting vertex, find an ancestor vertex closest to root who value is at least P.
  • Input constraints:
    • 1 ≤ N ≤ 200000
    • 1 ≤ Q ≤ 100000
    • 1 ≤ P ≤ 2³¹ - 1
• Naive solution:
  • Starting from each given vertex v, move up the tree until we find the first vertex whose direct parent has value less then P or until we reach root.
  • Runtime (TLE): O(NQ)
• Better solution:
  • Traverse the tree once (preorder-traversal) and store the paths (node index and value).
  • Within each path, the nodes are always sorted (special tree condition).
  • If encountered node in query (query as array so node index is array index), binary research previous path to find answer.
  • Runtime: O(N + Olog(N))

D&C Binary Search: Binary Search the Answer

• UVA: Through the Desert
  • Analysis:
    • Range of possible answer is between 0.000 and 1000.000 (10M possibilities).
  • Binary Search the Answer
    • If x is the correct answer, then any value between 0.000 and x will not get the jeep to goal.
    • On the other hand, the value between x and 1000.000 will possibly get you there.
    • This is the monotone property that we need to find.
• Problem (LeetCode Contest 275 Maximum Running Time of N Computers)
  • Analysis:
    • Maximum possible simultaneous run time for all: n/sum of all battery charges.
    • Minimum possible simultaneous run time for all: 0.
    • If the computers can run simultaneously for X minutes, then they may run simultaneously for more than X minutes.
    • If the computers cannot run simultaneously for X minutes, then they definitely cannot run simultaneously for more than X minutes.
    • Possible choices for minutes are limited/round numbers.
    • Binary Search the Answer.

Challenges

• Kattis: Need for Speed

Greedy

• Make locally optimal choice at each step with the hope of eventually reaching the globally optimal solution.
  • Sliding windows is an example of greedy technique.
• Works for some cases, not for many others.
• Required characteristics
  • Optimal solution to the problem contains optimal solutions to the sub-problem
  • Has greedy property: if we make the choice that seems like best at the moment and proceed to the sub-problem, eventually we will reach the optimal solution.
• Problem (LeetCode Contest 275 Maximum Running Time of N Computers)

Challenges

• Kattis: Inflation
• Kattis: The Dragon of Loowater

Dynamic Programming (DP)

• The most challenging problem-solving techniques among the four paradigms.
  • It is best to be well-versed in the previous three techniques (Complete Search, D&C, Greedy) before trying out DP.
• Key skills:
  • Able to determin the problem states/
  • Able to determine the relationship/transitions between the states.
• These are the same skills used in recursive backtracking for complete search.
  • Small DP problems can be solved with recursive backtracking.
• Naive interpretation of DP:
  • Top-down DP is intelligen/smart recursive back tracking.
• Problem types:
  • maximize this, minimize that, or count the ways to do that.
• Conditions:
  • Has optimal sub-structure: optimal solutions for sub-problems are guaranteed to be part of the final solution.
  • Has overlapping sub-problems: sub-problems share partial states.

Dynamic Programming (DP): Example

• UVA: Wedding Shopping
  • Sypnosis:
    • Given different pricing options for each garment.
    • Given a limited budget.
    • Buy one model of each garment.
  • Input:
    • Budget: 1 ≤ M ≤ 200
    • Number of garments: 1 ≤ C ≤ 20
    • For each garment g:
      • Number of models for each garment, 1 ≤ K ≤ 20 , followed by price for each model (1 ≤ p ≤ K).
  • Output:
    • Either a single number or no solution.
  • Example test case 1:
    • M = 20, C = 3
    • g₀: 3 6 4 8
    • g₁: 2 5 10
    • g₂: 4 1 5 3 5
    • Answer: 19 (8, 10, 1) or (6, 10, 3) or (4, 10, 5)
  • Example test case 2:
    • M = 9, C = 3
    • g₀: 3 6 4 8
    • g₁: 2 5 10
    • g₂: 4 1 5 3 5
    • Answer: no solution

Non DP Approaches

• Greedy Approach: Wrong Answer
  • Example test case 3:
    • M = 12, C = 3
    • g₀: 3 6 4 8
    • g₁: 2 5 10
    • g₂: 4 1 5 3 5
  • Greedy principle: a optimal solution also contains a local solution for a sub-problem. Therefore we should pick the most expensive model for each garment.
    • Case (0,8): no budget for anything in g₁lead to no solution.
    • Case (1,10): no budget for anything in g₀ lead to no solution.
    • Case (2, 5): no budget for the third garment piece lead to no solution.
    • Correct answer: (4, 5, 3).
• D&C approach: does not work because sub-problems are dependent on one another.
• Complete Search:
  • 20 possible garments, each has up to 20 possible models
  • C(20,20) ~ 10²⁶
  • TLE

Top-down DP:

• Does have the optimal sub-structure as a Greedy problem.
  • If we select model i for garment g = 0, for the final selection to be optimal, our choice for garment g = 1 and above must also be the optimal choice for a reduce budget M (minus cost of i).
• Lack the greedy characteristics:
  • The costliest model i for g = 0 is not guaranteed to be the best selection.
• Distinction between Greedy and DP: find counter-example.
• Does have over-lapping sub-problem.
  • If there are two models in a certain garment g with the same price p.
  • A complete search will move to the same sub-problem (garment + 1, budget - p) after picking either model.
  • Similar scenario if some combination of budget and models’ prices lead to: b₁ - p₁ = b₂ - p₂
  • Overlapping: Pricing of each model can not exceed 20, and the maximum value for budget is 201.
    • Problem state: The current budget when a garment is selected.
    • Maximum possible search space: 20 * 201 = 4020 (comparing to 10²⁶ of Complete Search)
• Implementation
  • Add an efficient data structure (memo table) to map state to value. Initialize the table with dummy values.
  • At the start of the recursive function, check if the state has been computed.
    • If it has, return the value of the memo table.
    • If it has not, perform the computation as normal and store the computed value in the memo table.

Bottom-up DP:

• True form of DP
• DP is original known as tabular method.
• Basic steps:
  • Determine the required set of parameters that uniquely describe the problem (the state).
  • If there are N parameters required to represent the states, prepare an N dimensional array with one entry per state.
    • Only initialize some cells (base cases).
  • With the base cases filled out, determine the cells/states that can be filled next.
  • Repeat the process until the DP table is complete.

LeetCode example

• LeetCode Contest 275 Solving questions with brainpower
  • Greedy does not work due to the lack of greedy properties
  • Top down
  • Bottom up