The problem set of **SPC Round 67** is [here].(http://www.hackerrank.com/spc-round-67/challenges ))↵
↵
The final standings of this round is [here](https://www.hackerrank.com/contests/spc-round-67/leaderboard)↵
↵
Congratulations to the winners of this round. ↵
↵
###**Last digit** :↵
↵
You dont need to care about any other digit except last digit of every elements. Multiply and go forward and keep modding the result by 10 so that the multiplication result always remains one digit.↵
↵
Time complexity :O(n)↵
↵
↵
###**IEA Capital** :↵
↵
This problem can be break down as 'all pairs distance sum of the tree' and the result will be multiplied by 4. Because you travel 4 times between every pair (u, v). ↵
↵
Now Let's solve the problem : all pairs distance sum of a Tree.↵
↵
Maintain an array sub[n], that keeps the subarray size of every node. When backtrack from dfs update parent nodes subarray size as sum of its all child's subarray size. And then add one for the node itself. ↵
Let's see how we can use the idea of contribution here. If we notice carefully that our final answer constitutes only the edges of our tree. (i.e.,) Our final answer is just a collection of edges taken many times. So, our basic entity of the final answer is my edge of the tree.↵
Let's iterate on each edge and find its contribution. Basically, I am fixing my edge say (u,v), and trying to find how many of the paths contain this (u,v) edge. Number of nodes left to this edge times Number of nodes right to this edge. Because if any nodes you select from left of the edge as starting and any nodes you select from right of the edge as ending then (u, v) edge belongs to their path. ↵
Left nodes is actually sub[u] and right nodes are actually N-sub[u] (v is parent of u). ↵
Edge (u, v) contributes sub[u]*(N-sub[u]) to the answer.↵
↵
After finding the answer, just multiply it with 4.↵
↵
Time complexity :O(n)↵
↵
↵
###**Ideal array** :↵
↵
You can't change the last value of the array. So, calculate the number of elements which is not equal to last element. That will be the answer. ↵
↵
Time Complexity :O(n)↵
↵
↵
###**Ideal array |** :↵
↵
For every value A[i], you can make all value equal to A[i] that costs N-frequency[A[i]]. For all i from 1 to N, count the minimum cost to make all elements equal to A[i]. Maintain a variable that keep tracks of minimum cost among all A[i]. That will be the answer. ↵
↵
Time Complexity : O(n log n).↵
↵
↵
###**Permutation subarray** :↵
↵
Store positions of all array elements in a pos map or array.↵
We will go from 1 to MEX of the array and maintain two pointer lo and hi. initially make lo = n+1, hi = -1.↵
for every i, update lo and hi with pos[i]. ↵
if pos[i] < lo, lo = pos[i]↵
if pos[i] > hi, hi = pos[i]↵
If hi-lo + 1 == i, that means the subarray [lo....hi] is a permutation. update your maximizing answer with this length.↵
Lastly you got the answer.↵
↵
Time complexity :O(nlogn)↵
↵
↵
###**Divide by 9**:↵
↵
If you set x = 1, then N will be divided by 9. because, N looks like N = 99999....↵
↵
now go through all the multiples of 9.↵
like x = 1 + 9*0, 1 + 9*1, 1 + 9*2, 1 + 9*3, 1 + 9*4........ 1 + 9*y.↵
If y is even positive number then 1 + 9*y must be a prime number. Otherwise not.↵
Now you have to find p-th smallest y which is even. And that y is nothing but p*2.↵
So, answer will be 1+9*(p*2) = 1 + 18p.↵
↵
Time complexity :O(t).↵
↵
↵
###**Last character**:↵
↵
go through the last character to first character of the string, if you find any lowercase letter then output that and break. If your iterator goes front of the first character that means there is no lowercase letter in the string, print -1 in that case.↵
↵
Time complexity :O(n)↵
↵
↵
All the submissions of this round is open. You can check them out from the contest page. ↵
↵
Hope you find this round educational. Thanks for your participation. ↵
Any kinds of suggestions are welcomed.↵
↵
The final standings of this round is [here](https://www.hackerrank.com/contests/spc-round-67/leaderboard)↵
↵
Congratulations to the winners of this round. ↵
↵
###**Last digit** :↵
↵
You dont need to care about any other digit except last digit of every elements. Multiply and go forward and keep modding the result by 10 so that the multiplication result always remains one digit.↵
↵
Time complexity :O(n)↵
↵
↵
###**IEA Capital** :↵
↵
This problem can be break down as 'all pairs distance sum of the tree' and the result will be multiplied by 4. Because you travel 4 times between every pair (u, v). ↵
↵
Now Let's solve the problem : all pairs distance sum of a Tree.↵
↵
Maintain an array sub[n], that keeps the subarray size of every node. When backtrack from dfs update parent nodes subarray size as sum of its all child's subarray size. And then add one for the node itself. ↵
Let's see how we can use the idea of contribution here. If we notice carefully that our final answer constitutes only the edges of our tree. (i.e.,) Our final answer is just a collection of edges taken many times. So, our basic entity of the final answer is my edge of the tree.↵
Let's iterate on each edge and find its contribution. Basically, I am fixing my edge say (u,v), and trying to find how many of the paths contain this (u,v) edge. Number of nodes left to this edge times Number of nodes right to this edge. Because if any nodes you select from left of the edge as starting and any nodes you select from right of the edge as ending then (u, v) edge belongs to their path. ↵
Left nodes is actually sub[u] and right nodes are actually N-sub[u] (v is parent of u). ↵
Edge (u, v) contributes sub[u]*(N-sub[u]) to the answer.↵
↵
After finding the answer, just multiply it with 4.↵
↵
Time complexity :O(n)↵
↵
↵
###**Ideal array** :↵
↵
You can't change the last value of the array. So, calculate the number of elements which is not equal to last element. That will be the answer. ↵
↵
Time Complexity :O(n)↵
↵
↵
###**Ideal array |** :↵
↵
For every value A[i], you can make all value equal to A[i] that costs N-frequency[A[i]]. For all i from 1 to N, count the minimum cost to make all elements equal to A[i]. Maintain a variable that keep tracks of minimum cost among all A[i]. That will be the answer. ↵
↵
Time Complexity : O(n log n).↵
↵
↵
###**Permutation subarray** :↵
↵
Store positions of all array elements in a pos map or array.↵
We will go from 1 to MEX of the array and maintain two pointer lo and hi. initially make lo = n+1, hi = -1.↵
for every i, update lo and hi with pos[i]. ↵
if pos[i] < lo, lo = pos[i]↵
if pos[i] > hi, hi = pos[i]↵
If hi-lo + 1 == i, that means the subarray [lo....hi] is a permutation. update your maximizing answer with this length.↵
Lastly you got the answer.↵
↵
Time complexity :O(nlogn)↵
↵
↵
###**Divide by 9**:↵
↵
If you set x = 1, then N will be divided by 9. because, N looks like N = 99999....↵
↵
now go through all the multiples of 9.↵
like x = 1 + 9*0, 1 + 9*1, 1 + 9*2, 1 + 9*3, 1 + 9*4........ 1 + 9*y.↵
If y is even positive number then 1 + 9*y must be a prime number. Otherwise not.↵
Now you have to find p-th smallest y which is even. And that y is nothing but p*2.↵
So, answer will be 1+9*(p*2) = 1 + 18p.↵
↵
Time complexity :O(t).↵
↵
↵
###**Last character**:↵
↵
go through the last character to first character of the string, if you find any lowercase letter then output that and break. If your iterator goes front of the first character that means there is no lowercase letter in the string, print -1 in that case.↵
↵
Time complexity :O(n)↵
↵
↵
All the submissions of this round is open. You can check them out from the contest page. ↵
↵
Hope you find this round educational. Thanks for your participation. ↵
Any kinds of suggestions are welcomed.↵
