Problem 1 (Chandra and Logs):
PREREQUISITES
Sieve of eratosthenes, prefix sums.
DIFFICULTY
Simple
EXPLANATION:
The main observation in this problem was that ln(x)=ln(a) + ln(b) where a*b=x. From this we can infer that we just need to know the natural logarithms of those numbers which can’t be expressed as a product of two numbers, i.e. prime numbers. Thus, for a given L and R, we just need to calculate the number of primes in the range. This can be done using prefix sums and sieve of eratosthenes.
AUTHOR’S SOLUTION
Problem 2 (Lazy Shash):
PREREQUISITES
Greedy.
DIFFICULTY
Easy
EXPLANATION:
The problem statement is suggestive of a greedy strategy. We had employed such a strategy in our solution but realised after the contest that there was a small bug in our solution which is why the wrong results were being produced. We have, however, rectified this bug and re-evaluated all the solutions. We regret any inconvenience.
Note that the problem is equivalent to the maximum no. of people working at any point of time. We can count the maximum by keeping a track of the no. of people working by sorting the events in chronological order and maintain a counter which we increment when we encounter the starting time of a job and decrement when we encounter the ending time of a job.
Since,sorting the events is O(n log n) , the overall complexity is O(n log n). This is actually a classical problem whose solution can be found at https://www.geeksforgeeks.org/find-the-point-where-maximum-intervals-overlap/
AUTHOR’S SOLUTION
Problem 3 (And Subarray):
PREREQUISITES
binary search.
DIFFICULTY
Easy-Medium
EXPLANATION:
The key to solving this problem is realising that if for a given value x, we can partition the array such that the minimum gcd of all subarrays is greater than or equal to x, then we can also partition the array such that this value is greater than or equal to x-1. This gives us the intuition that the problem can be solved using binary search. Our strategy should be as follows:
Binary search on the answer. In the predicate (the function used to evaluate whether the condition is true or not), iterate through the array and maintain variables cur and count. The variable cur is the bitwise AND of the current subarray and count indicates the number of segments that have been created till now. If the value of cur is smaller than the current value as per the binary search, we should create a new segment and increment counter. We are essentially partitioning the array so that all subarrays have a bitwise AND greater than or equal to a given value. In the end, we can just compare the value of count with L. If we have greater greater than L subarrays, then the current value cannot be the answer and we should check lower values. Otherwise, we can just check higher values.
AUTHOR’S SOLUTION
Problem 4 (Candies on a tree):
PREREQUISITES
Tree DP.
DIFFICULTY
Easy-Medium
EXPLANATION:
A careful interpretation of this problem reduces it to finding the path whose values form the longest strictly increasing subsequence. The constraints offer an insight to how this problem can be solved. The values of the nodes are smaller than or equal to 50.
The DP state can be dp[n][51] where dp[i][j] represents the maximum sum from all increasing subsequences in the subtree of the ith node with maximum value smaller than or equal to j. The transitions are as follows:
dp[i][j]=max(dp[v][j]) for all children v of node i.
dp[i][arr[i]]=max(dp[v][arr[i]-1] + arr[i]) for all children v of node i. Note that this transition changes the definition of dp[i][j] as we are only considering those paths in which the final value is exactly j. To change this, we have to iterate once through the array and update it as follows:
dp[i][j]=max(dp[i][j], dp[i][j-1]) for all valid j.
This state gives us the O(N^2*Maximum array value) solution. We can simply fix every node as the starting node (essentially root the tree at this node) and do a DFS to calculate all the dp values. We can then update answer as max(answer, dp[current_root][50]);
The complete solution requires a few more observations. Consider an increasing subsequence C1, C2…C[n]. Now, for all indices i, we can say that C1…C[i] is increasing while C[n]…C[i+1] is decreasing. This gives us the insight that the maximum sum increasing subsequences can be calculated by independently combining the increasing subsequence to that point with the decreasing subsequences starting from that point.
To calculate the second quantity, we introduce a second dp state, dp2[i][j] which contains the maximum sum of a decreasing subsequence starting within i’s subtree containing minimum value no smaller than j. The transitions are as follows:
dp2[i][j]=max(dp2[v][j]) for all children v of node i.
dp2[i][arr[i]]=max(dp2[v][arr[i]+1] + arr[i]) for all children v of node i. Again, we will need to run a for loop and update values as shown below so that dp2[i][j] shows the maximum sum for decreasing subsequences with AT LEAST j as the minimum element and not EXACTLY j as the minimum element:
dp2[i][j]=max(dp2[i][j], dp2[i][j+1]) for all valid j.
This gives us the O(N*Maximum array value) solution. We can simply update the answer variable as ans=max(dp[i][j]+dp2[i][j+1]) for all i and j.
AUTHOR’S SOLUTION
Problem 5:
PREREQUISITES
Floyd Warshall, Dijkstra.
DIFFICULTY
Medium
EXPLANATION:
Since all the labyrinths have the same design , we can calculate the distance between any two checkpoints in O(P^3) using Floyd-Warshall however since C can be different for every labyrinth, we will have to run it P times for all possible values of C for a total time complexity of O(P^4). These stored shortest distances can now be used to calculate the weights of the edges between different countries in O(1) lookup time. This gives us another graph in which we have to calculate the shortest distance of each node from node 1. The statement itself is suggestive of Dijkstra’s algorithm. We can use a priority queue to implement the ElogV version of Dijkstra’s algorithm. The complexity of the solution is O(M log N + P^4).