Weekly Training Farm 25 — Editorial

Revision en16, by dreamplay, 2017-02-26 17:42:33

Editorial will be completed soon!!

Problem A

Code

This is an adhoc problem. We just need to consider all the possible cases of joining. Note that we can join 2 rectangles only along their common side lengths, if any.

For n = 1, it is trivial, check if it is a square.

For n = 2, only possible way is to join the 2 rectangles.

For n = 3, we have two cases. Either join them all linearly, all 3 in a row kind of fashion. Another way is to join the 2 rectangles to form a greater rectangle and then join third one, perpendicularly.

For all of the above cases, if it is possible to form a square, the side length of square is the largest length / breadth from rectangles.

Problem B

Code

First of all, g(0) = 0.

Since g(g(x)) = -x then using this condition, g(g(g(0))) = -g(0) if we expand 2 outer g's and g(g(g(0))) = g(0) if we expand 2 inner g's. Thus, if g(0) = -g(0) then g(0) = 0.

Now, let g(a) = b then g(b) = g(g(a)) = -a, similarly g(-a) = g(g(b)) = -b and g(-b) = g(g(-a)) = a. Thus we get {a, b, -a, -b}, that is we need to divide the given integers into such groups.

Therefore, if r != -l, then answer is zero, as we need both positive and negative of a number.

Also, if r is odd, then answer is zero, as we need to divide into groups with exactly 2 positive and their negative integers. By using combinatorics, we can get the answer as follows: ** yet to write further**

Problem C

Code

To find all triangles, we need to find number of ways to select 3 lines such that no 2 of them have same slope.

We can do this counting, by sorting all the lines by their slope. Now let the slope of 3 lines that we select be m1, m2 and m3, such that m1 < m2 < m3.

So we iterate on the 2nd line, that has slope m2 and for each such line, add the possible ways for selecting m1(<m2) and m3(>m2) ways.

Problem D

Code

Since C(n, i + 1) = C(n, i) * (n — i) / (i + 1).
We can iterate on i from 1 to k, and keep some table to store the prime factorisation of each C(n, i).

Then we can know the maximum power of each prime that occured and thus their product will give us the required LCM. Another solution for this problem can be to use a mathematical identity
Let X be the required answer, X = lcm { C(n, 0), C(n, 1), ...C(n, k)} % mod
then (n + 1) * X = lcm(n+1, n, n — 1, ..., n + 1 — k),
for proof of above identity see this
So now all we need is to find the lcm of (n + 1 — k, n + 1 — k + 1, ...n-1, n, n + 1)
We can do this by iterating over all the primes and then iterating on powers from 1 till the smallest power that is not divisible is found in this range.

Problem E

Code

A suboptimal solution first.

Let us first look at the algorithm for finding Minimum Spanning tree.

We may observe that if the ordering of edges, when sorted by weights, does not change, then the minimum spanning tree remains to be unchanged i.e. the edges in MST remain to be same, even if we increase/decrease the edge weights.

So, if we considered all the pairs of edges, found the time when their edge weights become equal, then one of the edge weight becomes larger than the other one, forever, as they are linear functions of time.

Of course, in some cases, if they are identical, then always same.

Now, sort these O(m^2) times of intersections, we can say that minimum spanning tree between any of the two adjacent times, remains unchanged.
Thus we can find the MSTs for each of these times and answer the queries.
This will certainly TLE, O(m^3 log n).
The optimal solution uses binary search and attains following complexity.
precalculation:(O(log 10^8 * m log(m)))
each query:O(m log(m))
** optimal solution soon **

Tags weekly training farm, #editorial, discussion

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en20 English dreamplay 2017-02-26 18:42:27 2 Tiny change: 'in range [$-10^8$, $10' -> 'in range [-$10^8$, $10' (published)
en19 English dreamplay 2017-02-26 18:41:25 676 (saved to drafts)
en18 English dreamplay 2017-02-26 17:46:03 0 (published)
en17 English dreamplay 2017-02-26 17:44:00 4 Tiny change: 'uired LCM.\nAnother ' -> 'uired LCM.<br>\nAnother '
en16 English dreamplay 2017-02-26 17:42:33 628 (saved to drafts)
en15 English dreamplay 2017-02-26 17:35:32 1 (published)
en14 English dreamplay 2017-02-26 17:34:51 2803
en13 English dreamplay 2017-02-26 17:29:56 1017
en12 English dreamplay 2017-02-26 17:25:15 896
en11 English dreamplay 2017-02-26 17:23:17 331
en10 English dreamplay 2017-02-26 17:17:57 30
en9 English dreamplay 2017-02-26 17:16:42 16
en8 English dreamplay 2017-02-26 17:15:50 1086 (saved to drafts)
en7 English dreamplay 2017-02-26 17:07:38 15
en6 English dreamplay 2017-02-26 17:01:07 0 (published)
en5 English dreamplay 2017-02-26 17:00:05 32
en4 English dreamplay 2017-02-26 16:59:20 8
en3 English dreamplay 2017-02-26 16:58:26 1949
en2 English dreamplay 2017-02-26 16:25:52 749
en1 English dreamplay 2017-02-26 16:07:29 695 Initial revision (saved to drafts)