Geekhaven the technical society of IIIT Allahabad is organising its first open contest for the year 2019. The contest will be held on Codechef and will start at 10:00 PM on 19th April, 19. We hope to see you all on the leaderboard in large numbers.↵
↵
Contest Link : https://www.codechef.com/GHC22019 ↵
↵
Prizes : Codechef Laddus for top 3 in the leaderboard.↵
↵
↵
**Update :** Hints of the questions are given below, Full editorials of the questions will be posted soon.↵
↵
↵
↵
<spoiler summary="Round Around">↵
We can run a loop for every position (not A and B) and check whether this will give the minimum sum of the number of jumps and update the answer accordingly.↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Battle of the Bests">↵
Total runs scored for a delivery of speed x is max(reliability[i][p] * x + experience[i][p]) for all 1 <= i <= n. So you need to find the line with maximum value of y for a given x if you consider y = reliability[i][j] * x + experience[i][j] as a linear equation.↵
</spoiler>↵
↵
<spoiler summary="Maximum and Minimum">↵
It can be solved using disjoint set union.In a vector store the edges with their respective weights.To get product of maximum weight between all pairs sort the vector↵
in increasing order of weights.Loop and get connectivity(number of connected components of a edge) for each vector index edges, update the answer as ans*power(weight,connectivity(e1)*connectivity(e2)) and take union(e1,e2).For minimum weight do the above thing with vector sorted in decreasing order of weights.Get P and Q in form of prime factors raised to respective powers and calculate Z.↵
</spoiler>↵
↵
<spoiler summary = "Sweet by Chef">↵
We can build the resultant string character by character and if last part of the current string is their unliked strings we delete it from the string. Check if last part is their in the given unliked strings can be done by keeping a hash of all the distinct lengths found in N string. ↵
</spoiler>↵
↵
↵
<spoiler summary="Tom - The Gardener">↵
Suppose that common flower is f. Now find the maximum difference between subsequent flowers of type f. Suppose f occurs as follows xffxxfxfxxfxxx. The maximum difference is between 4th and 5th f. So, from there we can see that f occurs in every subarray of size 3. But we haven’t considered the first and last f. The gap before first f is 1. But the gap after last f is 3. So, from last f, we can conclude that every subarray of size 4 will include a f. Similarly for every f we calculate this size and take minimum of all these to find out x and corresponding f.↵
</spoiler>↵
↵
<spoiler summary="Base-ic Task">↵
It’s just a play of the odd and even arithmetics. Let Odd — o, Even — e. o*o=o; o*e=e; e*e=e and o+o=e; o+e=o; e+e=e. Ans = parity[(no of odd bases*parity of num in odd base)+(no of even bases*parity of num in even base)]. While the no of odd and even bases is simple impl.that can be found in O(1), parity of num in odd base can be found in O(N) and even base in O(1). Think how, by then, we will be back with the editorial!↵
</spoiler>↵
↵
<spoiler summary="Around the planets">↵
The question asks nothing but to count the number of substrings in the string where the string is obtained from appending each of the array elements to a null string serially.↵
Store the suffixes of the string and the reverse of the same in a suitable data-structure which will yield you the number of distinct substrings.↵
</spoiler>↵
↵
↵
Contest Link : https://www.codechef.com/GHC22019 ↵
↵
Prizes : Codechef Laddus for top 3 in the leaderboard.↵
↵
↵
**Update :** Hints of the questions are given below, Full editorials of the questions will be posted soon.↵
↵
↵
↵
<spoiler summary="Round Around">↵
We can run a loop for every position (not A and B) and check whether this will give the minimum sum of the number of jumps and update the answer accordingly.↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Battle of the Bests">↵
Total runs scored for a delivery of speed x is max(reliability[i][p] * x + experience[i][p]) for all 1 <= i <= n. So you need to find the line with maximum value of y for a given x if you consider y = reliability[i][j] * x + experience[i][j] as a linear equation.↵
</spoiler>↵
↵
<spoiler summary="Maximum and Minimum">↵
It can be solved using disjoint set union.In a vector store the edges with their respective weights.To get product of maximum weight between all pairs sort the vector↵
in increasing order of weights.Loop and get connectivity(number of connected components of a edge) for each vector index edges, update the answer as ans*power(weight,connectivity(e1)*connectivity(e2)) and take union(e1,e2).For minimum weight do the above thing with vector sorted in decreasing order of weights.Get P and Q in form of prime factors raised to respective powers and calculate Z.↵
</spoiler>↵
↵
<spoiler summary = "Sweet by Chef">↵
We can build the resultant string character by character and if last part of the current string is their unliked strings we delete it from the string. Check if last part is their in the given unliked strings can be done by keeping a hash of all the distinct lengths found in N string. ↵
</spoiler>↵
↵
↵
<spoiler summary="Tom - The Gardener">↵
Suppose that common flower is f. Now find the maximum difference between subsequent flowers of type f. Suppose f occurs as follows xffxxfxfxxfxxx. The maximum difference is between 4th and 5th f. So, from there we can see that f occurs in every subarray of size 3. But we haven’t considered the first and last f. The gap before first f is 1. But the gap after last f is 3. So, from last f, we can conclude that every subarray of size 4 will include a f. Similarly for every f we calculate this size and take minimum of all these to find out x and corresponding f.↵
</spoiler>↵
↵
<spoiler summary="Base-ic Task">↵
It’s just a play of the odd and even arithmetics. Let Odd — o, Even — e. o*o=o; o*e=e; e*e=e and o+o=e; o+e=o; e+e=e. Ans = parity[(no of odd bases*parity of num in odd base)+(no of even bases*parity of num in even base)]. While the no of odd and even bases is simple impl.that can be found in O(1), parity of num in odd base can be found in O(N) and even base in O(1). Think how, by then, we will be back with the editorial!↵
</spoiler>↵
↵
<spoiler summary="Around the planets">↵
The question asks nothing but to count the number of substrings in the string where the string is obtained from appending each of the array elements to a null string serially.↵
Store the suffixes of the string and the reverse of the same in a suitable data-structure which will yield you the number of distinct substrings.↵
</spoiler>↵
↵
