Editorial of SPC Round 69

Revision en3, by FahimR, 2024-10-26 11:33:16

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)

Code

D. The Magical Palindromic Potion:

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

Time complexity : o(nlog(1000))

Code

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)

Code

F.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)

Code

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English FahimR 2024-10-26 14:21:22 37 Tiny change: 'logn).\n\nHope y' -> 'logn).\n\n[Code](https://ideone.com/394DBj)\n\nHope y' (published)
en3 English FahimR 2024-10-26 11:33:16 152 Tiny change: ' :O(T)\n\n### G' -> ' :O(T)\n\n[Code](https://ideone.com/JInlgJ)\n\n### G'
en2 English FahimR 2024-10-26 11:11:07 72 Tiny change: ' 20Q) \n\n\n### ' -> ' 20Q) \n\n[Code](https://ideone.com/36JBsr)\n\n\n### '
en1 English FahimR 2024-10-26 08:19:20 2586 Initial revision (saved to drafts)