Special thanks to Ashraful Haque, Ahmeed Sakib Noman and IUT’s problem solvers for the editorial.
A. Old Tricks Are Cliche 2
The main object is to solve the following sub-problem:
“How many valid sequences are there between the interval from i to j?”
In order to solve this, let’s take another index k where k >= i + 1 and k <= j.
Now, if we say, both the indices i and k are “compatible” with each other, then a partial solution can be looked at from the indices i + 1 and k - 1 and from k + 1 to j. By compatible, we mean one of the following cases:
- i and k construct a valid pair of opening and closing sequences. So, they are either (), {} or [].
- At most one of i and k is a question mark and the other is a valid opening or closing sequence. For example, they are either ?), ?}, ?], (?, {? or [?.
- Both of them are question marks for which the result must be multiplied by 3 (what? Let’s keep it as an exercise).
This is the main idea of this solution. If we think of a similar problem, then the classic Matrix Chain Multiplication is a candidate problem.
Code: Ubuntu Pastebin
Please note that the solution did not print leading zeros, just take care of that for your solution.
B. Lost in Binary Tree:
First ask a question: what is the distance of node 1 from the root node and let the distance is d. Now, take a vector candidate_root that stores such nodes x that satisfy the condition distance(x,1) = d. Now continue the process until the size of candidate_root becomes 1
- Choose a node from the candidate_root vector and let this node be cur _node.
- Ask a query what is the distance of cur_node from the root node and let the distance is d.
- Now update the candidate_root vector. Exclude that kind of node x from the candidate_root vector whose distance(x,cur_node) is not equal to d. Since this is a binary tree, this process will reduce the size of the candidate_root vector by at least half each time.
So we can solve it in less than 20 queries. Also, we can find the distance from a node to any other node using DFS. Total time complexity is O(20*N).
C. I Am the Median:
As we need to find the sequence of median is exactly B, so firstly we can find the B’s location.
As all numbers are unique i.e. each integer appears exactly once, so there will be only one B in this sequence.
As the sequences can be made by deleting some elements from the beginning and from the end and there is only one B, so we can say that the possible sequences are containing the index of B and take some elements from the left and right of B consecutively.
So we can do the following :
After the index of B for each index we are going to count the number of elements greater than B and lesser than B. and count and save the difference from the greater and lower numbers in a map.
Now from the left of B’s index to the 0’th index we will count the same as before, i.e. greater and smaller elements of B. And find out the difference. Now in this time if we found the difference X of greater - smaller numbers, we all saved the count of -X ( negative X ) from the map we prepared before. Because if we find greater and less { 2, 3 } on the right, the difference -1 is saved in the map. And on the left if we found { 7, 6 } then this difference is 1. And -1 is saved on the map. It’s so because if we add the two pairs together we find { 9, 9 } and the B is in this element’s middle and the greater and smaller elements counts are the same so this is also an ans.
If we do this then we found all the solutions. But there are also cases. If for one pair the difference of greater and lesser than elements is 0 i.e. the count of both elements are same that is also counted as a ans too.
D. Is This the Easiest Problem of the Contest?
First thing is the new number can only be created using the digits available in the input.
And the output i.e. ans should only contain these digits available in the input. So both the inputs and outputs are the same length.
As out choice is limited by the input digits and the size of inputs or digits count in the input is limited to 6 so we can try all possible permutations of the input digits and choose the best one as the ans.
To do so, we are going to take the input number as string and then generate all possible permutations of the input digits.
To find the best ans we create a string of the same length as the input string and all the characters of this string will be 9.
Now for all possible permutations of the input string we check the current permutation is greater than the input string then we minimize this permutation with the all 9 string.
As all the strings we created or generated or input are the same length we can compare the numbers or strings with each other as strings that will also work.
Now after trying all possible permutations if the all 9 string is changed then this string is the ans. But if all 9 strings are the same then there is no ans.
E. Pascal the Programming Language:
The given input program is simple: start iterating from N-1 to 1 and break the loop as soon as the iterator is a divisor of N.
As the input is up to 10^9 so we can’t do the iteration.
But we can find all the divisors of N with sqrt ( N ) time.
So we are going to find all the divisors of N and take the biggest one which is less than N. This number is the number where the loop ends. So now finding the distance from N-1 to this number is just simple.
F. How to Answer the Query:
Assume that we have 10 segment trees for digits 0 to 9, where each node of the ith segment tree stores information for the ith digit. Now we can answer the query easily. The main part of this problem is updating the range. The first observation is that each number is updated cyclically and the cycle length is 10. For range updates, we can use lazy propagation and update the (i+1)th segment tree information from the ith segment tree.
It takes O(q*log(n)10) complexity for updates and O(qlog(n)*10) complexity for query.
G: Behold the Fear of Geometry 3
In this problem, we want to find the number of pairs of perpendicular segments. We can fix the point where the segments should be perpendicular, and iterate over all segments that end on that point, and save their slopes in a map, where the slope will be the key and the number of segments already visited with that slope will be the value. For every new segment, we will check in the map, how many segments are there with a slope perpendicular to the slope of this segment (y / x becomes -x / y). And then this segment should also be added to the map. Caution should be maintained for storing slopes in order to correctly identify the same slopes. Slopes can be stored as pairs of numbers (dx, dy) and reduced by their gcd. When dx is negative, or dx is 0 and dy is negative, both numbers should be multiplied by -1.
H.Turbo:
If the ith operation is odd, the number (i+1)/2 is moved to the (i+1)/2 position, and the initial position of (i+1)/2 is p. The total required number of swap equals how many numbers in range [1,p-1] that are greater than (i+1)/2 and less than or equal to n-i/2.
If the ith operation is even, the number (n-i/2)+1 is moved to the (n-i/2)+1 position, and the initial position of (n-i/2)+1 is p. The total required number of swaps equals how many numbers in range [p+1,n] that are greater than or equal to (i+1)/2 and less than (n-i/2)+1.
Using an order set or Merge Sort Tree we can find how many numbers are present in a range [L,R] that are less than a and greater than b.
We can solve it in O(nlog(n)) or O(nlog(n)^2) complexity.
I. TRUCKS:
Hint 1: Solve this problem without this condition “a driver cannot use an exit if his ticket says he used the same entrance”.
Hint 2: Without this condition, we can solve it greedily.
Hint 3: Apply the condition, swapping up to three adjacent entrance tickets in the same exit and entrance ticket situation, is sufficient for the minimum cost.
Solution: Sort the two arrays’ entrance and exit tickets. After sorting, the first entrance ticket and the first exit ticket are combined to pay the minimum cost otherwise the cost will increase. In this way combine the all ticket and take a dp array where,
dp[i] = inf (if exit and entrance are same)
otherwise, dp[i] = absolute difference of exit and entrance ticket.
Now iterate from i equal 1 to n and take another array dp_prefix ( store the prefix sum of dp array )
(i) combine and swap exit[i] and exit[i-1] ticket and store the new dp[i] and dp[i-1] value and update the,
dp_prefix[i] = min(dp_prefix[i],dp_prefix[i-2]+dp[i]+dp[i-1])
(ii) combine and swap exit[i], exit[i-1] and exit[i-2] ticket and store the new dp[i], dp[i-1] and dp[i-2] value and update the
dp_prefix[i] = min(dp_prefix[i],dp_prefix[i-3]+dp[i]+dp[i-1]+dp[i-2])
Finally dp_prefix[n] is the final answer. The time complexity is O(n*(3!+2!)).