Final standings of SPC Round 69 is [here](https://toph.co/contests/training/n6dkdf6/standings)↵
↵
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](https://ideone.com/23yaq2)↵
↵
↵
### 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](https://ideone.com/36JBsr)↵
↵
↵
### 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](https://ideone.com/5zEbVb)↵
↵
↵
### D. The Magical Palindromic Potion:↵
For every integer, if It's palindrome then add it to the answer.↵
↵
Time complexity : o(nlog(1000))↵
↵
[Code](https://ideone.com/3PxfAB)↵
↵
↵
### 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](https://ideone.com/5SM0xt)↵
↵
### 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](https://ideone.com/JInlgJ)↵
↵
### 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).↵
↵
[Code](https://ideone.com/394DBj)↵
↵
Hope you find this round educational. Thanks for participating this round.↵
↵
↵
↵
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](https://ideone.com/23yaq2)↵
↵
↵
### 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](https://ideone.com/36JBsr)↵
↵
↵
### 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](https://ideone.com/5zEbVb)↵
↵
↵
### D. The Magical Palindromic Potion:↵
For every integer, if It's palindrome then add it to the answer.↵
↵
Time complexity : o(nlog(1000))↵
↵
[Code](https://ideone.com/3PxfAB)↵
↵
↵
### 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](https://ideone.com/5SM0xt)↵
↵
### 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](https://ideone.com/JInlgJ)↵
↵
### 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).↵
↵
[Code](https://ideone.com/394DBj)↵
↵
Hope you find this round educational. Thanks for participating this round.↵
↵
↵
