Scribd
Upload
8 views10 pages

Computer Programming 2 Lab

The document outlines a midterm review for a Computer Programming 2 Lab, covering key techniques such as enumeration, greedy algorithms, binary search, and divide and conquer. It introduces the 'Subarashii technique' for problem-solving, emphasizing pruning, naive solutions, and assumptions for optimization. Additionally, it includes reminders for input/output optimization and encourages independent problem-solving without reliance on ChatGPT.

Uploaded by

kuo2004731
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views10 pages

Computer Programming 2 Lab

The document outlines a midterm review for a Computer Programming 2 Lab, covering key techniques such as enumeration, greedy algorithms, binary search, and divide and conquer. It introduces the 'Subarashii technique' for problem-solving, emphasizing pruning, naive solutions, and assumptions for optimization. Additionally, it includes reminders for input/output optimization and encourages independent problem-solving without reliance on ChatGPT.

Uploaded by

kuo2004731
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 10

Computer Programming 2 Lab

2025-04-08

1
Outline
Midterm review
Subarashii technique
Reminder before the midterm

2
Midterm review
Something may help you

Vector
Sort

3
Midterm review
Enumeration

Always think about how to use enumeration to solve problem.


Analyze the time complexity carefully.
What exactly are you trying to enumerate? Does that really help you solve the
problem?

// if you want to find the j-th bit on i


i >> j & 1
// if you want to enumerate every number within [0, 2^n]
for (int i = 0; i < (1 << n): ++i) {
for (int j = 0; j < n; ++j) {
if (i >> j & 1) // todo
}
}
4
Midterm review
Greedy

Considering local optimum, we can conclude that the global optimum can be
composed of multiple local optima.
Try to observate the greedy properties and reduce the number of enumerations.

5
Midterm review
Binary Search

When sth is monotonicity(very important!).


How to check the answer?

6
Midterm review
Divide and Conquer

Divide : keep dividing the problem into subproblems which can be easily solved.
Conquer : Solve each subproblems.
Combine : Merge the sub-solutions.
It would be helpful to clearly understand which steps in merge sort correspond
to divide, conquer, and combine.

7
Subarashii technique
Which is also called "騙分".

8
Subarashii technique
Pruning: Avoid the unnecessary computations. (ex: dfs)
Enumeration: Just write the naive solution first, then prune as much as you can.
Guess the solutions: Especially for greedy problems, just assume that the local
optimum can lead to the global optimum, and prove it by getting AC (Accepted).
For binary search, assume there's some kind of monotonicity.

9
Reminder before the midterm
IO Optimization(important!!): ios::sync_with_stdio(false); cin.tie(nullptr);
Template: pre-written code.
Try to solve every HWs and examples without ChatGPT.

10

You might also like