AngCPC Problem Set

Tutorial and Discussion

A - Loyalty
• The key idea here is that we want to maximize the size of each group while still
ensuring that every member of the group is comfortable with the group size.
• We will sort the friends in non-increasing order depending on their loyalty values.
Then, we will iterate through the sorted list of friends, and for each friend, we will try
to add him to the last created group or create a new group for him.
• To add a friend to the last created group, we simply check if the current size of the
last created group is less than the minimum between the minimum loyalty value in
the last created group and loyalty value of this friend. If it is, we add the friend to the
last created group. Otherwise, we need to create a new group.

• Time Complexity : O(N)

• Tag : ad-hoc
B - Play with Koko
• Each cat ID is the product of its parent's IDs. So, a common ancestor is a common divisor.
• we only need to know if there is a common divisor (except 1) between them or not.
• Simply, we can know that if the greatest common divisor of two cats' ID is greater than 1.
• Time Complexity : O(log(min(a , b))).
• Tag : ad-hoc.
C - Parking Area
• Simply we will declare a priority queue and add $n$ distinct numbers from 1 to n
representing the empty slots in the parking area and we will declare a map to store in it
the car’s id with its slot number.
• for each query, if the letter is "E" we will pop an element from the priority queue which
will be the smallest number in it, and print the sentence containing the slot number
and then we will store the car’s id with its slot number in the map.
• if the letter is "L" we will get the slot number using the car’s id from the map and then
push the slot number into the priority queue and remove the car’s id from the map.
• if the size of the priority queue is 0 that means there are no available slots and the
employee will leave.
• Time Complexity : O(q*log(n))
• Tag : data structure
D - median check
• We can solve this problem with a greedy algorithm if we want number x to be the median in
an array of length n if n = 5 and we need at least n/2 numbers to be >= x call this half i and at
least $n/2$ to be <= x call this half j.
• So, if we search in the array and count how many numbers in the array a (because the min )
are greater than x so these numbers must be in the half i .
• If these numbers are greater than n/2 this means this number can't be the median for array
p.
• Otherwise, this means we want some numbers equal to x to complete the half i so search for
these numbers if you find them and find a number to put it in the median this means you
complete the half i and the median can be equal to x and for half j you want to minimize
prices which you put in array p to make the sum of array p not greater than m the dollars you
have.
• Time Complexity : O(n*log(n))
• Tag : greedy, binary search
 E - Tug of War
 Find a way to formulate the array which describes the optimal way to arrange a team and then
compare each value of team A to its corresponding value in the array and find out how many
players are standing in their right position and do the same for team B to know which team will win
or it would end up with a tie.
• Time Complexity : O(n*log(n)).
• Tag : ad-hoc.
F - Phoney Company
• First, we will do a DFS (depth-first search) to compute the sub-tree size for
each node (excluding the node itself).
• Then for each node v, we will include all possible non-empty combinations
from its subtree which is 2^(size of subtree) - 1, but this will include wrong
combinations, so we will exclude them from our calculations.
• But what are the wrong combinations which may be included?
• The wrong combinations will be the combinations in which all nodes in it
appeared in the subtree of only one child of v and this child didn't appear.
• So we can iterate over all children and subtract from the answer 2^(size of
subtree of child) – 1.
• Time Complexity : O(n)
• Tag : Graph and number theory
G - Awesome Segments
• First, we will get for each index i, the maximum index j, such that the sub-array [i : j] is in non-
decreasing order, then we get the same but for the sub-array that is in non-increasing order, we
can get both by some data structure or by dynamic programming.
• Then we can do another dynamic programming to get the answer, where dp[i] represents the
number of ways to split the sub-array [i: n-1] into non-empty contiguous valid segments, the
transition will be the sum of dp[j] till the sub-array [i+1: j-1] is a valid segment, from the initial
preprocessing we can get the index j by this way, first, we will get the furthest index k such that
the subarray [i : k] is in non-decreasing order.
• Then we will get the furthest index j such that the subarray [k : j] is in non-increasing order,
then we can get the sum without a loop by using any data structure (Range sum query), ordinary
suffix sum will be useful.
• At last, the answer will be at dp[0].
• Time Complexity : O(n).
• Tag : dynamic programming
 H - The Music Game
• The only two numbers which have the maximum difference will be the
minimum and maximum power in the powers vector.
• So, we are going to use deque to push the powers in it and then sort it.
• We used deque because we will check the maximum difference between
the front and back elements only so we can pop from the front and back
only.
• Another solution, we can use a two pointers algorithm instead of a deque
on a sorted vector.
• After n - 1 operations we will print the only element in the deque or vector..
• Time complexity: O(n * log(n)).
• Tag : greedy.
I - Change permutation
• We can solve this problem using dp[i], dp[i] = what is the longest length of the
common subsequence contain number i.
• Before that, we need to store in some array what is the index for every number for
every permutation in array arr, arr[i][j] = x.
• Means the number j in permutation i in index x.
• So, we can using this array for solving dp, and transition clear in the code.
• How many elements in the array dp = length of the longest common subsequence
-1.
• Because in my dp, I return the value after I check this element valid or not.
• Time Complexity for: O(N * k ^ 2).
• Tag : Dynamic Programming.
J - The Whole Nine Chars

• He can jump up to 9 rocks each time, so we get the ceil of the

difference between the current character and the destination
character z divided by 9.
• Time Complexity : O(1)
• Tag : ad-hoc
K - Bouncing Ball
• For every possible start i, let's define j as the maximum number of bounces if we start with
power p at block i. We can use binary search to find such j then we can derive a formula to
calculate the number of points.
• There is a special case we can handle to make the solution more efficient, when p >= n, the
answer will always be equal to n since there won't be any bounces.
• The complexity would be O(n*log(min(n, p))).
• This solution can be optimized further with a key observation, the maximum number of points
will always result from the maximum number of jumps ending at $n$, with this observation we
can calculate the maximum number of jumps starting from $1$ using binary search then shift the
start until we end at $n$ with the same maximum number of jumps using the derived formulas.
• The complexity would be O(log(min(n, p))).
• Time Complexity : O(log (min (X, Y))
• Tag : number theory
L - Hajar's Game
• The idea of the problem is to use the biggest element from at most k
numbers on the left and right of each element. So, if you get the biggest
one of this set of elements, you will add it the minimum number of times
to rich 10^6 or bigger.
• You can simply use two sets to keep the right and left elements for each
number and get the biggest of them. Then with the small equation, you can
get the number of the operations:
• numOfOpertions = (maxElement - currElement) / maxElement, and if there
is a reminder add one more operation.
• Time Complexity: O(n * log(n))
• Tag : ad-hoc
M - Meow-san XORing
• To solve this problem, we need to count the number of pairs (i, j) such that
i<j and A[i] XOR A[j] is even. We can do this by counting the number of pairs
(i, j) such that A[i] and A[j] have the same parity (both even or both odd).
• To count the number of even and odd integers in the array A, we can iterate
through the array and keep track of the count of even and odd integers
using two variables. Let's call these variables even and odd.
• Once we have the even and odd counts, we can compute the number of
pairs (i,j) such that A[i] and A[j] are both even or both odd using the
formula: (even choose 2) + (odd choose 2) = even*(even-1)/2 + odd*(odd-
1)/2
• Time Complexity : O(n)
• Tag : ad-hoc