Where are the rest of the editorials for CodeChef February Long Challenge
I can only see 5 Editorials in the link provided by CodeChef : FEB Editorials
If the problem setters are not going to upload the editorials could
someone in this forum post them or explain them ?
EDIT: The remaining editorials have been posted here.
I’m working on them. Apologies for the delay.
What about remaining editorials? It’s been 4 days since the contest ended.
How much more delay?
In the absence of a WRDSUM editorial, here are some thoughts.
The problem statement WRDSUM provides a definition of F(n) equivalent to smallest x for which n is a perfect power of x.
Define S(N) as F(2) + F(3) + ... + F(N).
WRDSUM asks for various values of S(N) for N \le 10^{2600} modulo a given prime.
For most n, we have F(n) = n, so a first step is to write
S(N) = \sum_{r=2}^N r - \it corrections
The first corrections come from the perfect squares. In the sum over r, the values 4, 9, 16, 25, 36, 49, 64, ... are replaced by 2,3,2,5,6,7,2,..., or better written as F(2), F(3), F(4), F(5), F(6), F(7), F(8), ....
Perfect cubes follow the same pattern: the values 8, 27, 64, ... are replaced by F(2), F(3), F(4), ...
So S(N) has become
S(N) = \sum_{r=2}^N r - \sum_ {p} \left( \sum_ {r=2}^{\sqrt[p] N} r^p - S(\sqrt[p]N) \right) + \it more\ corrections
where the sum over p is a sum over prime numbers.
Perfect sixth powers have been subtracted twice (because perfect sixth powers are both squares and cubes) so have to be added back. Continuing along these lines, and introducing the mobius function \mu(n) to handle the inclusion/exclusion arguments, we have
S(N) = \sum_{r=2}^N r + \sum_{n} \mu(n) \left( \sum_{r=2}^{\sqrt[n] N} r^n - S(\sqrt[n]N) \right)
where the sum over n is now over all integers >1. The \mu(n) is the number theory möbius function, defined as zero if n has a square divisor, -1 if n has an odd number of distinct prime divisors, and +1 in n has an even number of distinct prime divisors.
The largest value of n in which we are interested arises when 2^n = 10^{2600}, which is n=8638. Calculating primes and the möbius function to 8638 is fairly quick.
Calculating sums of n th powers can either be done by explicit calculation, or using Faulhaber’s formula, depending on how many nth powers are required. Formulae for the Bernoulli numbers from wiki or similar.
Integer n th roots can be calculated using a mix of logarithms, or iterative formulae.
Various numbers are needed repeatedly, so caching or memoizing of functions is useful.
I couldn’t answer the last group of test cases during the FEB16 competition. Since then I have
an untidy solution. Other answers seem to be smaller and faster, so must use better ideas.
How long till the editorials?
By when are the editorials expected to be posted for FEB16 long challenge…plus the problems links for certain practice problems of FEB16 are missing…It would be really helpful if these issues are fixed as soon as possible.
@tarun_007 Editorial for RECTLOVE
For RECTLOVE Problem. To calculate expectation value you have to count in how many rectangles each cell which is painted comes. Sum this value and divide by total number of rectangles and that’s the answer.
A common approach that one may think is that independently see by applying inclusion exclusion principle that how many disjoint rectangles are there in which only one painted square comes, then similarily for 2 and so on, but that wont work here.
The main point to think is that when we are counting total rectangles for any cell then some other painted squares will also be included in the set of rectangle to which this particular cell belongs but this works which for simplicity i am illustrating from the figure.
For Cell 3 while we are counting total rectangles then {3,4,7,8} will be counted and when we are counting this for Cell 8 then again this will be counted i.e. {3,4,7,8} i.e. this value is counted twice and so its contribution to total sum is 2 which is equal to 2 * total rectangles in which there are two squares. i.e. 2 x 1. If multiple cells say k come under contribution for total rectangles of any cell then that particular rectangle will be counted for all those k cells which gives us the expectation value of getting k cells one time.
How to calculate how many rectangles does any cell belongs to ---->
In the figure for cell 7 you have 3 choices to increase its size in downward direction,2 towards right,3 towards left and again 2 towards top. So total = 3 * 2 * 3 * 2 = 36. Why two on left? because you have choice either to completely not extend the rectangle or extend by size 1. You can think it like how many rectangles for 1 x 2 or 1 x 1 or 2 x 1 matrix.
Counting total rectangles is also very easy task which can be done similarly.
Answer = (Sum of count of rectangles in which all cell belongs / total number of rectangles)
Do comment for any help
Execution time for the bigger test cases was for the most part determined by the speed of calculating the roots. I had basically no experience of bigint computation, so I just picked an implementation from the net - in fact it seems I took the same as you.
This was enough for passing the time limit, but using a better implementation increases the speed drastically. The GMP lib was faster by a factor of 50 for computing roots than my implementation. Even ordinary multiplication is faster by a factor of 30.
The conclusion is right but the explanation hard to follow.
Questions asking for Expectations of something often depend on the fact that an expectation of a sum of things is equal to the sum of the expectations of the things. In symbols, E(A+B) = E(A)+E(B). Always true.
For this question, the expectation of the sum of the hearts is equal to the sum of the expectations of each individual heart.
Expectation of each individual heart is given by number of rectangles containing the heart / total number of rectangles.
The discussion shows how to calculate the number of rectangles for each heart.
Where can we find the editorials for problem SEAPERMS?
**
**
I wasn’t able to solve the problem in the contest, but in seeing the post above (@apptica), I was able to make out the solution.
Since the explanation was not that clear in the previous post, I will try to explain it further.
The main objective of the problem is to find the expected number of hearts a randomly chosen rectangle will contain.
Expected value is nothing but the mean value. So to calculate the expected value, we can calculate the mean by the following steps.
For a rectangle of size M x N
Expected Value = (Total number of hearts) / (Total number of subrectangles)
Total number of subrectangles = (N) * (N+1) * (M) *(M+1)/4
To calculate the total number of hearts, we can use the naive method to use a nested for loop to go through all the subrectangles, and the count the number of hearts in each, and add them up to get the total.
But that will give TLE because it will use 4 nested for loops.
We can optimally calculate the numerator by making the following observation.
The amount by which each subrectangle contributes to the total is equal to the number of hearts in it. So if we can take each heart separately and count the number of rectangles it a part of, we get the same total.
This is because,
Taking one subrectangle and counting two heart == Taking two hearts individually and counting the same subrectangle
The counting can be done optimally by
Taking the 1x1 rectangle the heart is in, and expanding it in left, right, bottom, top directions.
Suppose the heart is located at (i,j) in a MxN rectangle
Number of places it can expand to the left = i
Number of places it can expand to the right = N - i + 1
Number of places it can expand to the top = j
Number of places it can expand to the bottom = M - j + 1
Total number of subrectangle in which the heart is part of = (i) * (N - i + 1) * (j) * (M - j + 1 )
Use this formula to calculate the total number of subrectangles for all the hearts and divide by the denominator to get the answer.
Do comment for any clarification.