INC Practice for LA08

Coding practice for Algorithm Design and Analysis (COMP6049001). The problems are solved on vjudge.

How to join the contest

Open the contest link: https://vjudge.net/contest/858200
Log in to vjudge. If you do not have an account yet, register one (free) at https://vjudge.net.
If you are asked for a password or access code, enter:

LA08-ADA
Once you are in, open the Problem tab and choose a problem (A to L).
Click Submit, choose the language C++ (pick C++17 if available), paste your code, and submit.
Check your result in the Status tab. A problem is solved when the verdict is Accepted.

Read the input from the keyboard (cin) and write the output to the screen (cout). Do not read or write files.
Check the input limits in each problem. If the numbers are large, use long long.
Start from problem A. The problems go from easiest to hardest, and K and L are bonus problems.
If you get Wrong Answer, try a small input of your own and compare it with a manual calculation.
If you get Time Limit Exceeded, your algorithm is probably too slow. Think about a faster approach.

#	Problem	Short description	Topic
A	Watermelon	Can a watermelon of weight w be split into two positive even parts?	Basic conditions
B	Wrong Subtraction	Apply a "wrong" subtraction rule k times, then print the result.	Simulation
C	Hit the Lottery	What is the minimum number of bills (1, 5, 10, 20, 100) needed to pay n?	Greedy
D	Array Rearrangement	Can array b be rearranged so that a[i] + b[i] ≤ x for every i?	Sorting, greedy
E	Payment Without Change	With a coins of value n and b coins of value 1, can you pay exactly S?	Greedy
F	Honest Coach	Split the athletes into two teams so that the difference between max(A) and min(B) is as small as possible.	Sorting
G	Same Differences	Count pairs i < j with a[j] − a[i] = j − i.	Hash table
H	Books	How many books in a row can be read within time t, at most?	Two pointers
I	Add All	Add all numbers together; each addition costs its result. Find the minimum total cost.	Greedy, priority queue
J	Movie Festival	Choose as many movies as possible with no overlapping schedules.	Greedy
K	Largest Rectangle in a Histogram (bonus)	Find the area of the largest rectangle inside a histogram.	Stack
L	Inversion Count (bonus)	Count pairs i < j with a[i] > a[j].	Divide and conquer

Good luck and happy coding!