Final standings of SPC Round 69 is here

Editorial :

A. Minimize Maximum Pair Sum:

To minimize the maximum pair sum you can pick maximum + minimum, 2nd max + 2nd min, 3rd max + 3rd min..... Among all such pairs, the maximum pair sum is the answer. You can do this using two pointer after sorting the array.

Time complexity : O(nlogn)

Code

B. The Ancient Tree of Fahimland.

In this problem, the tree will not remain tree anymore if vertex u is an ancestor of vertex v. Because it will create a cycle containing u and v. So now the problem has been simplified as finding u is an ancestor of v or not. if LCA(u, v) is u, u is an ancestor of v and you can answer NO.otherwise YES. To find LCA you can use binary lifting. Tree can have maximum depth 2^20. Too many good blogs / tutorials are available in google YouTube. You can check the topic.

Time complexity : O(20N + 20Q)

Code

C. Colorful Puzzle:

Imagine Fahim's luck is worse than the worst. If he pick 2N balls where was N red balls, N green balls. (shit) Okay Let's pick one more ball, now it’s confirmly he will pick the blue ball because all remaining balls was blue. So, 2N+1 balls he should pick to get all colors of balls at least one.

Time complexity :o(1)

D. The Magical Palindromic Potion:

For every integer, if It's palindrome then add it to the answer.

Time complexity : o(nlog(1000))

E. Fahim's Binary Sorting Puzzle:

The greedy part is : for every 0, you need to do p operations where p is count of 1's left of that 0. Go from left to right, keep a counter of 1. For every 0 you found add counter to your answer.

Time complexity : O(n)

H.The garden Fence :

You are given the perimeter n. Let say two side is a and b. 2(a+b)=n, a+b=n/2. To maximize your area, you need to maximize the minimum among a and b. So if a+b is even then a = b = (a+b)/2, otherwise a = (a+b)/2 and b = (a+b)/2+1. Then a*b is the answer.

Time complexity :O(T)

G. Evenly Digitized:

You can see that only first position can have 4 digits and other positions can have 5 digits. As leading zero is not acceptable. For length x, the answer will be 4x5^(x-1). Using larg exponentiations, you can find for every digit in logarithmic time. Then use prefixsum technique Precomputation to find every segments sum in query with o(1) complexity.

Time complexity : O(10^6 logn).

Hope you find this round educational. Thanks for participating this round.