Problems proved to be much harder than we expected. There were some corner cases we didn't include in pretests, so many solutions failed, which was definitely a mistake. Anyway, I hope you find this problemset interesting!

Problem A.

Very simple implementation problem. Just implement what is written in the statement: for every element of array, find the number of array elements greater than it, and add one to the sum. This can be easily done with two nested loops. Total complexity O(n²).

Solution:

Problem B.

First, calculate the number of occurences of every English letter in strings a, b, and c. We can now iterate by number of non-overlapping substrings of the resulting string equal to b, then we can calculate in constant time how many substrings equal to c can be formed (by simple operations on the number of occurences of English letters in c). In every iteration, maximise the sum of numbers of b and c. Number of iterations is not greater than |a|. At the end, we can easily build the resulting string by concatenating previously calculated number of strings b and c, and add the rest of the letters to get the string obtainable from a. Total complexity is O(|a| + |b| + |c|).

Solution:

Problem C.

Problem solution (complete work time) can be binary searched, because if the work can be done for some amount of time, it can certainly be done for greater amount of time. Let the current search time be k. We can determine if we can complete work for this time by folowing greedy algorithm: find last non-zero pile of boxes and calculate the time needed to get there (which is equal to it's index in array) and take with first man as much boxes as we can. If he can take even more boxes, find next non-zero (to the left) pile, and get as much boxes from it, and repete untill no time is left. When the first man does the job, repete the algorithm for next man, and when all m men did their maximum, if all boxes are removed we can decrease upper bound in binary search. Otherwise, we must increase lower bound. Total compexity is .

Solution:

Problem D.

First convert number k into binary number system. If some bit of k is 0 than the result of or opertion applied for every adjacent pair of those bits in array a must be 0, that is no two adjacent those bits in array a are 1. We should count how many times this is fulfilled. If the values were smaller we could count it with simply dp_i = dp_i - 1 + dp_i - 2, where dp_i is equal to number of ways to make array od i bits where no two are adjacent ones. With first values dp₁ = 2 and dp₂ = 3, we can see that this is ordinary Fibonacci number. We can calculate Fibonacci numbers up to 10¹⁸ easily by fast matrix multiplication. If some bit at k is 1 than number of ways is 2ⁿ — \t{(number of ways bit is 0)}, which is also easy to calculate. We must be cearful for cases when 2^l smaller than k (solution is 0 then) and when l = 63 or l = 64. Total complexity is .

Solution:

Problem E.

First we divide array a in groups with numbers. Every group in each moment will be kept sorted. For type 1 query, If we update some interval, for each group, which is whole packed in the interval, we will add the number it is being increased to it's current increasing value (this means all the elements are increased by this number). If some part of group is covered by interval, update these elements and resort them. Now, let's handle with type 2 queries. When we want find GukiZiana(a, j), we search for the first and the last occurence of j by groups. One group can be binary searched in , because of sorted values, and most groups will be searched. Of course, for the first occurence we search for minimum index of value of j, and for the last occurence maximum index of value of j in array. When we find these 2 indexes, we must restore their original positions in array a and print their difference. If there is no occurence of j, print  - 1. Total complexity is .

Solution: