Invitation to CodeChef August Long Challenge 2019

@admin please clarify this.

Ties will not be broken, and all the users with the same rank will be eligible for the corresponding scholarship.

1 Like

Ties will not be broken. Hence whatever rank a participant gets will be used to determine the scholarship as detailed in the rules. Not sure what’s confusing about this.

In particular, yes, if multiple users score the same highest points from an institute, and if they have scored >= 400, then all of them will be eligible for 100% scholarship.

2 Likes

And if 10 people are at position 1 then next person (11th) will be eligible for scholarship of 11th rank and not 2nd rank( because 10 people have rank=1).
If I am not wrong.

I think those questions at the end of Div. 1 from Div. 2 also matter in ranking both the divisions together…

1 Like

Ik.
PS : admin gave rules after I and @yashrajkakkad posted those comments.

1 Like

Hi all,

Unfortunately, due to some personal reasons the editorials of following problems are delayed. They will be posted by end of this week tenatively

  • KS1 - Done
  • SYNBAC - Pending Approval
CHGORAM

Let’s consider the euler tour of the tree and build a merge sort tree over it. Let’s consider an arbitrary vertex x as a candidate for p2. Then with the help of the merge sort tree we can calculate for every adjacent vertex the number of vertices in its subtree that are less or greater than x in O(log^2 n). Let there be k adjacent vertices, a_1, …, a_k and the number of vertices with smaller index in the appropriate subtree be l_1, …, l_k, similarly the vertices with larger index be g_1, …, g_k. Then for example if we have the permutation p={1,2,3} or {3,2,1}, then we want to calculate \sum_{i!=j} l_i * g_j, this can easily be calculated in O(k) time in the following manner, let L=l_1+…+l_k and G=g_1+…+g_k, then the above sum is LG-\sum^{k}_{i=1} l_ig_i. There are 2 other cases which can be similarly examined. And because for this arbitrary x vertex we have calculated the answer in O(k log^2 n) then for the whole problem we have a O(n log^2 n) solution. We can reduce this to O(n log n) by applying fractional cascading. However we can also notice that the queries are offline thus a sorting method is feasible too (and much faster in practice), i.e let’s look only at queries like in an interval [l;r] we want to calculate the numbers which are larger than y (the case when we want to calculate the numbers which are smaller than y can similarly be solved). Then we put these queries and the indices of the vertices in one list and sort them by their index (for the queries the index is y and for the vertices its their index :P), and then just loop over them from the largest index to the smallest, and do a point increase in a fenwick tree at a vertex, and calculate the sum from l to r for a query.

CSTREE

We use generalized cayley’s formula (combinatorics - Proof of Generalized Cayley's formula - Mathematics Stack Exchange) and inclusion/exclusion.

For inclusion/exclusion. We need to count the number of spanning trees that use at least t forbidden edges. We can split t = t_1+t_2+...+t_k, where t_i is number of forbidden edges we used in i-th copy of graph. We also need to take the size of the components into account, so if we use t_i edges in the i-th copy, there will be n-t_i components with some sizes s_{i,1},...,s_{i,n-t_i}. The number of spanning trees in total with this configuration is sum product$(s_{i,j}) * (kn)^(kn-t)$, over all valid ways to split the sizes of each component.

The second term is only dependent on the number of forbidden edges we use, so we can pull it out.
We can split the first term per component, so we only need to find these values for one tree, then we can use polynomial multiplication to get the values for k copies.

To compute sum product (s_{i,j}) for one tree, use the generalized matrix tree theorem. Consider a matrix M, with M_{i,i} = deg(i) and M_{i,j} = -1 if there is an edge and 0 otherwise. Fix some set A. If you delete the i-th row and column for every i in A, then the determinant of M will be the number of forests of the original graph with every node in A belonging to a separate component.
Consider the matrix M. If we add a variable x along the diagonal of M, then the determinant of M will be some polynomial in x. We claim that the coefficient of x^k is exactly what we need to compute. It sums over all ways to split some nodes into k different components. Forests are counted multiple times according to the product of their sizes, which is what we need.

So the solution will look something like this:

  • Compute the determinant of matrix M + I * x to get a polynomial (easiest way can be to evaluate this at x=0,x=1,…,x=n-1, then do polynomial interpolation to get coefficients)
  • Exponentiate this polynomial to k-th power (maybe need fft here).
  • Take i-th coefficient and multiply by (-1)^(i) * (k*n)^(k*n-i)), and sum them up to get the final answer
TSEQ

We can build an HLD there. Then we can split every path into O(log(N))
paths. You can note that only values with A_i not equal to -1 matter.
So we can check whether these values satisfy the non-decreasing
condition. If no then the answer is 0.
Now for every A_i not equal to -1 let’s maintain the number of ways to
change -1 till the next A_i not equal to -1 on its heavy path(This can
be done easily with some binomial coefficients and if we store set of
A_i not equal to -1 on every heavy path) And store this values in
segment tree. For -1 these values should be equal to 1. Now roughly
speaking we can query product on the range in segment tree. And for
most left and rightest A_i on the path we can find the number of ways
to change values of -1 on it and on the previous heavy path by hand
again with some binomial coefficients.
Update : O(log(N))
Query : O(log^2(N))

3 Likes

when will the rating be updated?

2 Likes

Hold your horses! @vivek_1998299

7 Likes

seams to me time limit of CHGORAM was harsh. Used euler traversal and persistent segment tree. Still got TLE

2 Likes

well idk whether your solution is online or offline but I think the strict time limit means that you must figure out an offline solution for the problem.

Yeah, I also found it a bit tight - I had a worst-case O(N log2 N) solution, but for a long time my constant factor was just (frustratingly!) a tiny bit too high - it almost certainly would have passed in 3 seconds, but just missed 2.

Happily, it forced me to think of better ways to do it, and I managed to squash the constant factor by quite a bit, so the tight time-limit probably worked out in the end :slight_smile:

I’m still very impressed by this guy’s solution - 0.32 seconds!

Edit:

Hey, I’ve got a little blue-star thingy - have the Rankings been updated already?? I assumed it would take at least 24 hours!

@taran_1407
For Tree sequence problem. Can you please explain the idea a little bit please?

I used HLD + seg_tree. In each node I store the whether the current range is increasing or not, and if there are ‘-1’ in between I stored the answer (as we know what is the max and min we can put there). So at each node we have at most two ranges for which we don’t know the answer (the left end and the right end).

I know it’s very hard to find mistake in the solution. But if possible can you please look at approach and can tell whether my approach is correct or not? Please …

You are on fire! Congrats again (after CF ;P)

1 Like

I had the same thing, then I removed all dynamic allocation and pointer usage by static memory and indices of that static memory and got AC!

1 Like

my solution of CHGORAM is N*logN \hspace{0mm}.

thanx :slight_smile:

4 Likes

First I used merged sort tree(NLOGNLOGN) which timed out.Then used persistent segment tree(N*LOGN) still timed out.

Code:CodeChef: Practical coding for everyone

1 Like

I used sum query segtree after sorting queries.
Numbsubarrayer of elements less than or equal to a given number in a given - GeeksforGeeks
Along with euler tour and logic
Passes : CodeChef: Practical coding for everyone

2 Likes

Can some1 plz tell where am i going wrong? i used upperbound and lowerbound
on sorted array to get elements greater and lower than P2.
my sol: https://www.codechef.com/viewsolution/25895177
Edit : Lol i misunderstood the Question. Nvm!!

To start with your answer with p1 p2 p3 should be same as p3 p2 p1

1 Like