Hello Guys. I hope you all had a fun solving problems of November Challenge. So, time for Editorials, Editorials for problems other than RECIPES, MAXDTREE, CHEFEQUA, and BINSTR has been posted (will be available as soon as moved to public by admin). I’ll try to complete these editorials too, as soon as I can. For now, I am sharing brief setter’s notes for these problems.
RECIPES
Click to view
The solution is based on a Monte-Carlo false-biased algorithm, an algorithm which always answers correct when the answer is false, but it has a probability of failure when the answer is true.
For each base recipe we’ll asign a random vector from F_{2^{64}}. The other recipes will be written as the sum of R_1, R_2, … R_{p-1} and R_p’s vectors.
In a query we’re interested if the set of vectors is linearly independent. This can be done with gaussian elimination in O(K^2) time.
For K <= 15 a single run of this algorithm suffices, whilst for K <= 30, in practice, the algorithm must be run 5-10 times.
MAXDTREE
Click to view
Firstly, I want to solve this task:
You have number 1 <= N <= 10^1000 and you have to find out if it’s belong to max digit sequence or not. Let’s define function dp(md, ld, len) = y, where y is the difficult thing. Let’s consider some process - you have number of kind 10000…(ld), where ld - is last digit of number with length len, first digit is 1 and other digits are 0. Let’s increase this number (let’s denote it by the curr) on value equal to max(md, maxDigit(curr)), where curr - our current number, md - parametr from dp(md, ld, len). In some moment we will have number with length equal to len + 1 and looks like 10000…(y), where y = dp(md, ld, len). How to calculate y, it’s very easy. Let’s consider you have counted all states with length <= len - 1 and now you want to calc dp(md, ld, len). Firstly, we will forget about first digit at the moment, we can look at state dp(max(md, 1), ld, len - 1) = y2, it’s obviously that on some moment of iterations that add to our number max(md, maxDigit(curr)) curr will be equal to 2000…(y2), after that we will look at state dp(max(md, 2), y2, len - 1) = y3 and go on. So, dp(md, ld, len) = y10 and will be calculated in 10 operations.
After we calculated all states of our dp, we have to check if N belongs to max digit sequence. We can do it in same way that we processing our dp, firstly we will first member of max digit sequence which length equal to len(N), it looks like 100…ld. Let’s fix ld, after that, we can jump over states of dp. Firstly, we will consider dp(1, ld, len(N) - 1) = y2, after that we will consider dp(2, y2, len(N) - 1) and so on while md not equal to the first digit of number N, after that we will turn to dp(N[0], y10, len(N) - 2) and do same things. In the end we have to compare last y10 digit and N[size(N) - 1] digit, if they are equal, then the number belongs to the sequence, otherwise there is no. So we have O(N * 1000) solution.
We can solve main task using supporting function dp(md, ld, len).
Let’s denote function f(v, len, md, fd) - cnt of members of max digit sequence, which satisfy all these conditions:
-
We made decision about all vertices u such that tin(u) < tin(v) if we take vertex of this kind in our subset or not (now we are making decision about v)
-
md = maximum digit of all taken digits
-
We will still make decision for exactly len vertices
-
last len digits of this member is equal to 000…(ld)
We will send current state to other states of our dynamic programming. (index[v] - index of vertex v in asceding tin array, order[] - tin asceding array).
f(order[index[v] + 1], len - 1, max(md, digit[order[index[v] + 1]]), X) += f(v, len, md, fd), where X is result of jumping over dp(md, fd, len - 1) = y_2, dp(max(md, 2), y_2, len - 1) = y_3 to y_k where k = digit[v], so X equal to dp(max(md, k - 1), y_(k-1), len - 1). (We considered case when we take next vertex in order array). If we wan’t to take it, we have to skip all subtree to satisfy condition if we take i we have to take p_i, it’s obviosly that subtree is subarray of order array, so we should go to order[index[v] + size[v]] where size[v] is size of subtree with root v. In this case we will have this addition:
f(order[index[v] + size[v]], len, md, fd) += f(v, len, md, fd). The answer is sum f(v, 0, md, digit(v)) where v and md can be arbitrary. So, we have (N^2 * 1000) solution.
I know it might seem a bit complex for now. I’ll try to simplify this in editorial
CHEFEQUA
Click to view
consider generating function of C: C(x) = \sum \frac{b_i}{1-a_ix} = \frac{\sum b_i \prod_{j\neq i} (1-a_jx)}{\prod (1-a_ix)}
let P(x) = \prod(1 - a_ix) , then C(x)P(x) = \sum b_i\prod_{j\neq i} (1 - a_jx)
let Q(x) = C(x)P(x), x = \frac{1}{a_i} then Q(x) = b_i\prod_{j\neq i}(1 - \frac{a_j}{a_i})
use multipoint evaluation to calculate Q(x) for each x = \frac{1}{a_i} then what we need to do is calculating \prod_{j\neq i} (1 - \frac{a_j}{a_i}) , we can do it using a method like multipoint interpolation
the time complexity is O(n\log^2 n)
BINSTR
Click to view
Let’s create a new array B of length N - a permutation of numbers from 1 to N. Let pos (i) be a number j such that B [j] = i. Then, if pos (X) < pos (Y), then A [X] <= A [Y].
Let’s get the function to solve (L, R, L, R, bit, X) that will solve the next task. Let’s for all the numbers in the array A and also for the number X remove all bits that are older than the bit bit. Then you need to find a number C (L <= C <= R) such that L <= B [C] <= R, and A [B [C]] XOR X is maximally possible. If there are several possible options, then among them it is necessary to choose a number with a minimum B [C]. This function assumes that all bits higher than bit a bit are equal for all A [B [i]] numbers (L <= i <= R).
How will our function work?
If bit = -1, then all the numbers in the segment L…R are equal, and we need to find a number i (L <= i <= R) such that B [i]> = L` and B [i] is minimal.
We can do this with a tree of segments.
Otherwise, it is advantageous for us to choose the number for which the value of a bit is bit back to the value of a bit bit in the number X. If there is no such number, then choose the same bit. Then, if we want to set the bit 0 here, we need to choose the maximum number K (L <= K <= R), such that the bit bit of the number A [B [K]] is 0. Then you need to check that on the segment L …K there is at least one number i, such that L <= i <= K and L <= B [i] <= R. Otherwise, select bit 1. If we want to set bit 1 here, we need to choose the minimum number K (L <= K <= R) such that the bit bit of the number A [B [K]] is 1. After that you need to do the same checking that with bit 0, if it is not correct, then select bit 0 here. Thus, we go either to solve (L, K, L, R, bit-1, X) or to solve (K, R, L , R, bit-1, X).
How to apply this feature to our solution? We have two options.
- All numbers from the segment L…R of the array A have a record length not greater than the length of the record of the number X. Then the answer to the query is
solve (1, N, L, R, record length of the number X, X);
- There is at least one number from the segment L…R of the array A, which has a record length greater than the length of the record of the number X.
Note that in this case such numbers are more advantageous for us than numbers that have a record length less than or equal.
Find the maximum number of K, such that L <= B [K] <= R. Then we find the minimum number K, such that all bits of the number A [B [K]] except for len (X) the least significant bits are equal to the bits of the number A [B [K]] (len (X) is the length of the record of the number X). Then the answer to the request is
solve (K`, K, L, R, len (X), X).
All operations can be performed using various modifications of the segment tree.
Please bear with me, Pardon for delay, Thanks.
-