SPC Round 68 has been finished. Congratulations to all of the winners of this round.↵
↵
The standings of this round is :[here](https://toph.co/contests/training/j86aezg/standings)↵
↵
The problem set of this round is:[here](https://toph.co/contests/training/j86aezg)↵
↵
Editorial:↵
----------↵
↵
### A.Programmer Homecoming : ↵
Imagine three straight lines a, b, c. a = distance of (0,0) to pillar, b = distance of pillar to home, c = distance of (0,0) to home. These distances are euclidean. If the pillar is on the way to line c, then can't go home. If a + b = c then the pillar must belong to line c otherwise not.↵
↵
Time complexity :O(1)↵
↵
[code](https://ideone.com/NiKKUF)↵
↵
### B.Love palindrome :↵
According to the palindromic character we need to make equals of A[i] and A[n-i+1], (1 <= i <= n/2). All such pairs are unique. For, every n/2 pairs the cost will be minimum of their distance and x. Sum up all n/2 costs for final answer.↵
↵
Time complexity :O(n)↵
↵
[code](https://ideone.com/Nh2WZ9)↵
↵
### C.Nice Pairs:↵
It can be proved that two numbers p and q can be Nice Pair if there is an integer x that satisfies x^3 = p and x^2= q. Because p^2 = x^6, and q^3 = x^6 so, p^2 = q^3.↵
↵
Instead of going for p or q we will go for x. So, it's enough to iterate x from 1 to 10^6 because our element limit is 10^18. If x > 10^6 then p will cross 10^18 which doesn’t exist in our array, we don't need to go beyond 10^6. for every x we add frequency(x^3) * frequency(x^2) to our answer. As combining them for every p with every q.↵
↵
Time complexity : O(10^6)↵
↵
[code](https://ideone.com/VixZ6Q)↵
↵
### D.HUNGKY MUNGKY:↵
We need to count the number of such elements which is either dividable by A or dividable by B or dividable by C (dividable by at least 1 element among A,B,C) and not more than N. We can get them by answer = N/A+N/B+N/C. But some elements might be counted multiple times. How many elements are counted multiple times? N/lcm(a,b), N/lcm(b,c),N/lcm(a,c) elements are counted multiple times. We must subtract them.so, answer = N/A+N/B+N/C-N/lcm(a,b)-N/lcm(b,c)-N/lcm(a,c). But N/lcm(a,b,c) valid elements are subtracted of their all occurrences. So we need to add them again. answer = N/A+N/B+N/C-N/lcm(a,b)-N/lcm(b,c)-N/lcm(a,c)+N/lcm(a, b, c). ↵
↵
Time complexity : O(T log(10^9)).↵
↵
↵
↵
### E.Children's intelligence game:↵
This can be solved multiple way but I want to explain about hashing + binary search. ↵
Let's see how we can find the lexicographically smaller string between two string using binary search. Using binary search, our target is to find the smallest position where character of two strings differs. If we can find that position then we can find the smaller string by comparing only that character. In binary search, for every mid if we find hash of s1[l...mid] = hash of s2[l...mid] then we need to go to right because left part are equal otherwise we need to go to left because somewhere in the left has difference.↵
↵
Let's use it in our problem. Given string s has length n. Declare, str=s+s. Create hash of string str of length 2n. keep an pointer p that points the position where the lexicographically smallest string starts, initially 1. Now, iterate over i = 1 to n, compare between substring str[p, p+n-1] and str[i, i+n-1]. If you find the str[i, i+n-1] smaller then update p=i.↵
At last print the substring s[p....n] + s[1....p-1].↵
↵
Time complexity :O(nlogn)↵
↵
[code](https://ideone.com/jBIcA1)↵
↵
### F. Fahim's magic stones:↵
Precompute the L array of length n where L[i] stores maximum subarray sum that ends at position i (1 <= i <= n).↵
↵
Precompute the R array of length n where R[i] stores maximum subarray sum that starts at position i (1 <= i <= n).↵
↵
What will be the maximum subarray sum if you don’t remove any value from the array? The maximum value of the array L and R. Keep that maximum value in the answer initially.↵
↵
Then for every index i (1 < i < n), if you remove the index, you will get L[i-1] + R[i+1]. Update this with your answer.↵
Removing the first and last element has already been calculated while taking the max of L array and R array.↵
↵
Time complexity :O(N)↵
↵
[code](https://ideone.com/eYHXLn)↵
↵
↵
Thanks for participating this round. ↵
↵
Hope you find this round educational. For the furthermore contest updates join our discussion group [here](https://t.me/+w27hkMksl_RjZDA9).
↵
The standings of this round is :[here](https://toph.co/contests/training/j86aezg/standings)↵
↵
The problem set of this round is:[here](https://toph.co/contests/training/j86aezg)↵
↵
Editorial:↵
----------↵
↵
### A.Programmer Homecoming : ↵
Imagine three straight lines a, b, c. a = distance of (0,0) to pillar, b = distance of pillar to home, c = distance of (0,0) to home. These distances are euclidean. If the pillar is on the way to line c, then can't go home. If a + b = c then the pillar must belong to line c otherwise not.↵
↵
Time complexity :O(1)↵
↵
[code](https://ideone.com/NiKKUF)↵
↵
### B.Love palindrome :↵
According to the palindromic character we need to make equals of A[i] and A[n-i+1], (1 <= i <= n/2). All such pairs are unique. For, every n/2 pairs the cost will be minimum of their distance and x. Sum up all n/2 costs for final answer.↵
↵
Time complexity :O(n)↵
↵
[code](https://ideone.com/Nh2WZ9)↵
↵
### C.Nice Pairs:↵
It can be proved that two numbers p and q can be Nice Pair if there is an integer x that satisfies x^3 = p and x^2= q. Because p^2 = x^6, and q^3 = x^6 so, p^2 = q^3.↵
↵
Instead of going for p or q we will go for x. So, it's enough to iterate x from 1 to 10^6 because our element limit is 10^18. If x > 10^6 then p will cross 10^18 which doesn’t exist in our array, we don't need to go beyond 10^6. for every x we add frequency(x^3) * frequency(x^2) to our answer. As combining them for every p with every q.↵
↵
Time complexity : O(10^6)↵
↵
[code](https://ideone.com/VixZ6Q)↵
↵
### D.HUNGKY MUNGKY:↵
We need to count the number of such elements which is either dividable by A or dividable by B or dividable by C (dividable by at least 1 element among A,B,C) and not more than N. We can get them by answer = N/A+N/B+N/C. But some elements might be counted multiple times. How many elements are counted multiple times? N/lcm(a,b), N/lcm(b,c),N/lcm(a,c) elements are counted multiple times. We must subtract them.so, answer = N/A+N/B+N/C-N/lcm(a,b)-N/lcm(b,c)-N/lcm(a,c). But N/lcm(a,b,c) valid elements are subtracted of their all occurrences. So we need to add them again. answer = N/A+N/B+N/C-N/lcm(a,b)-N/lcm(b,c)-N/lcm(a,c)+N/lcm(a, b, c). ↵
↵
Time complexity : O(T log(10^9)).↵
↵
↵
↵
### E.Children's intelligence game:↵
This can be solved multiple way but I want to explain about hashing + binary search. ↵
Let's see how we can find the lexicographically smaller string between two string using binary search. Using binary search, our target is to find the smallest position where character of two strings differs. If we can find that position then we can find the smaller string by comparing only that character. In binary search, for every mid if we find hash of s1[l...mid] = hash of s2[l...mid] then we need to go to right because left part are equal otherwise we need to go to left because somewhere in the left has difference.↵
↵
Let's use it in our problem. Given string s has length n. Declare, str=s+s. Create hash of string str of length 2n. keep an pointer p that points the position where the lexicographically smallest string starts, initially 1. Now, iterate over i = 1 to n, compare between substring str[p, p+n-1] and str[i, i+n-1]. If you find the str[i, i+n-1] smaller then update p=i.↵
At last print the substring s[p....n] + s[1....p-1].↵
↵
Time complexity :O(nlogn)↵
↵
[code](https://ideone.com/jBIcA1)↵
↵
### F. Fahim's magic stones:↵
Precompute the L array of length n where L[i] stores maximum subarray sum that ends at position i (1 <= i <= n).↵
↵
Precompute the R array of length n where R[i] stores maximum subarray sum that starts at position i (1 <= i <= n).↵
↵
What will be the maximum subarray sum if you don’t remove any value from the array? The maximum value of the array L and R. Keep that maximum value in the answer initially.↵
↵
Then for every index i (1 < i < n), if you remove the index, you will get L[i-1] + R[i+1]. Update this with your answer.↵
Removing the first and last element has already been calculated while taking the max of L array and R array.↵
↵
Time complexity :O(N)↵
↵
[code](https://ideone.com/eYHXLn)↵
↵
↵
Thanks for participating this round. ↵
↵
Hope you find this round educational. For the furthermore contest updates join our discussion group [here](https://t.me/+w27hkMksl_RjZDA9).
