Here it is. Thanks to TheOneYouDontWant and Stamford_Sloths for helping with the tutorial.
A. Dilemma of Perspective
First observation of this problem comes from the values of N (<=1000) and C(<=100000). It can not be an N^2 * C solution, since the constraints won’t allow it to run for that long. Then comes a psychological barrier of jumping into the optimal solution straight away. Instead of doing this, let’s first try to find a solution which is correct, but requires more resources than manageable.
Let’s say, we have an array of size N, if we want to place a number in the first position, we have N options. Our options are as follows:
1: If we place 1, there will not be any inversions for this placement.
2: If we place 2, there will be 1 inversion for this placement.
3: If we place 3, there will be 2 inversions for this placement.
N: if we place N, there will be N-1 inversions for this placement.
So, somehow, we need to eliminate the requirement to remember what exactly we had put in the first position, but still count the number of inversions it would cause to place a particular number.
At this point, think about one thing, do we really need to remember which number we have placed to count how many inversions this placement is causing? Not really. If we have x numbers left to make an arrangement and we choose the i’th largest number from these for the next available spot, then it will create i - 1 inversions for this placement. This is the Aha moment for this problem. So let’s create a recursive function based on the observations above:
int rec( int curPos, int remC ) {
if( curPos == lastPos && remC == 0 ) return 1;
if( curPos == lastPost && remC > 0 ) return 0 ;
int ret = 0 ;
int stillRem = N - curPos ;
for( int i = 0 ; i < stillRem ; i ++ ) {
ret += rec( curPos + 1, remC - i ) ;
ret %= MOD ;
}
dp[ curPos ][ remC ] = ret ;
return dp[ curPos ][ remC ] ;
}
Although the above one is a correct solution, it still takes more time than necessary. It’s complexity is O(N^2 * C ).
In order to reduce the runtime to O(NC), we need to take an iterative dp approach. Let’s also observe that a particular value of remC only looks up to a certain range of values from the previous position. Thus, we can use a cumulative sum approach to achieve a runtime of O(NC).
B. Triplets
Here we can think of the coordinates of the alphabet as a point(x,y) and the maximum number of points can be 26. Now we will choose 3 points from the total points and check are they in line? If yes, increase the answer by 1. Find the slope of the points so we can tell if they are on the line or not.
Total time complexity O(26^3)
Code link: Ubuntu Pastebin
C. Behold the Fear of Geometry!
Here we need to count the number of intersection points. Lets see how it can be done for N=5
Here if we consider all the lines from point A. first line is AC. So all the lines intersect with the line AB is { BD, BE } and then the next line for A is AD
So the lines intersecting with the line AD are { BE, CE }.
This observation shows us that if we start drawing lines from first point A, We can draw draw exactly N-2 lines and for each line the pints on left and right increases and decreases as follows.
Let. X = N - 2
On the right side there are 1 points and on the left side there are X - 1 points and the ans for this first line is ( 1 * ( X - 1 ) )
Next, line gives us 2 points on right and X - 2 points on the left so the ans for this ( 2 * ( X - 2 ) )
Ie… { 1, X-1 }, { 2, X - 2 } …… { X - 2, 2 }, { X - 1, 1 }
We get all the intersection points for lines starting from A i.e. first point. Now if we multiply the summation of all the answers with N we get almost the ans.
Almost because we double counted the intersection points. That is, lets see the below example.
For the intersection point P we counted it 4 times. I.e. { AD, BE }, { DA, BE },{ AD, EB }, { DA, EB }. So if we divide the current ans by 4 we get an accurate number of intersections.
D. Juggle The Labels
Let’s start with the trivial case where N = 2. Since the actual root of the tree is at level 0, the absolute difference between the left and right child of the root node will be 2^0 or 1. There are multiple solutions available for this, root can be either 1 or 3. It is hard to see a pattern from this example. But this would at least give an impression that with the increase of the levels, the distribution may remain mostly fixed for upper level numbers.
So, let’s jump on to the case where N = 3. The following tree will be a valid solution:
1
/ \
3 2
/ \ / \
4 6 5 7
Here, the difference between the roots at level 1 is 2^1 for both of the nodes and the difference of the left and right subtree of the root node is 1. Again, this gives the impression that we might be able to just assign the number in increasing order from the root node to the leaves.
Let’s focus on the above example once again. The sum of the child nodes rooted at node 3 is 10, while the sum of the child nodes rooted at node 2 is 12. This difference of 2 must be reduced to 1 using the values of roots 3 and 2. We got lucky because the differences were very small here, but for bigger levels, the difference of children will be higher and reducing it will be even more difficult. For any level D, the ideal scenario would be when nodes at levels greater than D should not contribute to the difference necessary at level less than D. In other words, we should try to keep the differences of sums at levels greater than D to 0. For example:
1
/ \
3 2
/ \ / \
4 6 5 7
/ \ / \ / \ / \
8 12 11 15 9 13 10 14
The sum of the children of 4 and 6 is 20 + 26 = 46. Similarly the sum of the children of 5 and 7 is 22 + 24 = 46. Thus, nodes of level 3, are contributing 0 while calculating the difference in level 1. For every node at level 2, the difference of its left and right children is 2^2 = 4. Notice how we distributed nodes at the leaf level. The smallest two numbers 8 and 12 were followed by the largest two numbers 11 and 15. Then the two second smallest numbers 9 and 13 are followed by the second largest two numbers 10 and 14… This is to maintain the same difference for all the adjacent pairs of leaves. Maintaining this same property for bigger levels will ensure the correct answer as well. This distribution of allocating numbers to leaf nodes follows a greedy pattern.
E. Ivana
All the numbers are plotted on a circle, As Ivana makes the first move she can start from any position.
After Ivana makes the first move that makes the game start and if Ivana chooses position I then Zvonko can only choose the position I+1 or I-1. As Zvonko will try to win, he will try to get the best option for him. As Zvonko is choosing the best option for him, Ivana will also try to get the best position for her in the next move.
So now if ivana chooses position I then the 2 moves Zvonko can make is I+1 or I-1 now the transition from one state to another state can be seen as. ( This is one of the way to represent this states and transitions )
Ivana chose position I so now its zvonko’s move and available positions from I+1 to circularly I-1 not I.
Now Zvonko can make two move
Choose I-1 and then its Ivana’s move and available range are I-2 and I+1
Choose I+1 and then its Ivana’s move and available range are I-1 and I+2
When there is no more move to make then the game ends and we can calculate the winner.
Only considering the moves is not enough, we also need to count how many odd numbers Ivana got and how many odd numbers Zvonko got and who is making this move.
With all this information we can make dp translation from one state to another.
If we do it recursively and memorize it then we can solve the problem.
The space and time complexity is
winner dp [ left_position ] [ right_position ] [ ivanas_odd_cnt ] [ zvonkos_odd_cnt ] [ who’s_move ]
which is 100 * 100 * 100 * 100 * 2 = 2 * 10^8.
Now we can omit one of the state from the dp and the problem is solved in 2 * 10^6 space and time.
Code link: Ubuntu Pastebin
F. Patterns in a String
Two solutions are possible in this problem. One is Binary Search and Hashing, the other is Suffix Array.
Binary Search and Hashing: The first observation is that if a substring of length x occurs more than once, there must be a non-empty substring of length less than x, that occurs more than once. So binary search will be applicable for this problem. For a fixed length x there are total n-x+1 substrings in the given string. Store the hash value of all these substrings. If any two hash value is equal then it satisfies the condition. Also, a map is needed to store the hash values.
It’s take total O(n*log(n)log(n)) complexity to compute.
Suffix Array: If you know how to build the LCP(Longest Common Prefix) array in Suffix Array, it is easier to solve this problem. Maximum LCP is the answer of this problem.
Building the Suffix Array takes O(nlog(n)) complexity and LCP array using Kasai’s LCP algorithm takes O(n) complexity.
G. Debug
First thing, how will the square change if it is rotated 180 degrees?
First row and last row exchange with reversely, then second row and second last row, and so on.
Let’s check if there is any x-length square in the grid that looks the same after 180 degree rotation.
We’ll check for every point (a,b) such that x+a<=n and b+x<=m and if there is any square maintain this rules:
for i=0 to x/2 , substring Sa+i[b,b+x-1] is equal to reverse(Sa+x-i-1[b,b+x-1]) ? if yes for every case then we got the x-length square. ( check it using hashing)
For maximum results, we iterate over x equals min(n,m) to 2 and check for validity.
Check the validity of x takes O((n-x)*(m-x)*x/2) complexity.
Code link: Ubuntu Pastebin
H. A Long Lost Problem
If there are no cycles in the graph, we can calculate the total ways by dynamic programming.
If there is a cycle in the graph, we will think of this cycle as a component node. If we can go from node 1 to node 2 using this type of component node then the answer is inf.
If the answer is greater than 9 digit you have to print the last nine digit. In this case you can use a big number as a mod.
Total time complexity is O(n+m).
Code link: Ubuntu Pastebin
I. This is the Easiest Problem of the Contest
Let’s solve this equation for R2:
(R1+R2)/2 = S
=> R1 + R2 = 2 * S
=> R2 = 2 * S - R1
We have the values of R1 and S, putting them into the equation will find R2.
J. Old Tricks Are Cliche
Our max perimeter rectangle’s lower side can be in any row, So let’s try to check for all possible rows.
Now for each row try to build an array of size C (column), where array[i] denote how much we may go up for taking max perimeter rectangle.
4 4
X.XX
X…X
…X.
…XX
For this example:
Array for row 1 will be [0, 1, 0, 0]
Array for row 2 will be [0, 2, 1, 0]
…
Array for row 4 will be [2, 4, 0, 0]
(This array can be build in O(C * R), simply for each position c, run a loop to check how much higher you can go with dots.)
(This array can be build in O(C) if you use value of previous row’s array, and then add +1 with the previous value, if it is dot. Or it is 0)
Now for each array,
For any position c in the array if you take the height array[c],
Then check how much right you can go so that array value >= array[c], similarly check how much left you can go so that the array value >= array[c].
(We a trying to maximise the width of the rectangle, if the height is array[c])
This can be done using a stack. Just like how we can solve this problem: Maximum Rectangle Area Problem in O(C)
Or This can be done using binary search and sparse table (for range minimum query) Then the complexity will be
O(C * log(C)).
(Sparse table build O(C * log(C)) and then O(C) for each position and log(C) this for binary search)
Depending on the implementation:
Your time complexity will be O(R * C)
or O(R^2 * C) or O(RClog(C))
all these should pass since 1<=R,C<=400