Sorry. I think I read something else or the constraints has been updated.
Yes I figured it out a while later 
I request @vijju123 @admin and the codechef team to pls give the explanation of testcase 2 for REBGIT . I have been trying to understand this problem for 2 hours now and nothing seems to work. I hope you understand.
2 Likes
Itās just that you have to fill in ā#ā with 4 possible values, 0 / 1 / a / ~a
~a is written as A
thus the expression can evaluate to one of the four values after substitution
You have to tell the probability that for each possible outcome.
That problem indeed is hard to explain, the writer seems to have tried his best to explain it
1 Like
I am using third party code which is publicily available before the contest.I have provided link url and mentioned in my solution that Iām using third party code.
Is it enough or I have to do some more thing ??
Iām confused anybody please help.
@vijju123 .
Thanks in advance 
Its enough, happy coding
1 Like
No video solution has been released for the FCTRE and ANSLEAK.
sorry
As the long challenge has nearly ended (Please donāt reply about ANSLEAK and FCTRE), The editorials for all problems except LLLGRAPH and TRIPWAYS have been posted. (FCTRE will become available once submissions are stopped for that). Sharing brief hints for last two problems here.
TRIPWAYS
The number of ways to reach city N in D days can be basically written as a linear recurrence, with its transition matrix being same as adjacency matrix for positions not on main diagonal elements and L_i for position (i, i) in matrix. We can use matrix exponentiation to solve in O(N^3+Q*N^2*log(D) by precomputing powers of transition matrix.
For final speed up, one way is to use Berlekamp-Massey Algorithm along with FFT as mentioned here, or do as the setter says. The best setter notes i ever saw. Thanks to @pieguy
Jordan decomposition solution (Setterās solution)
Since Chef only moves from lower numbered cities to higher numbered cities, the adjacency matrix is triangular. It follows that the eigenvalues (letās call them E_i) are the values on the diagonal, and therefore a Jordan decomposition exists.
Denote m_i to be the multiplicity of a given eigenvalue - 0 for the first occurrence, 1 for the next, and so on.
The existence of a Jordan decomposition implies constants C_{j,i} exist such that the number of ways to reach city j in D days is given by \sum_{i = 1}^N((^DC_{m_i})E_i^{D-m_i} * C_{j,i}).
We only need to compute these constants.
Complexity: O(N * M + N * Q * log(MAXD))
LLLGRAPH
For 30 points, the max independent set of L(G) is the size of maximum matching in general graph, which can be found via Edmond Karp/Blossom algorithm.
For full solution, solve for each connected component independently. So k \leq 6 and we need to find the max matching.
Letās simulate and find the first line graph, calling it H. Now the Number of nodes in graph is up to M and number of edges up to M^2. k \leq 5 on graph H would work.
Fact: The size of maximum matching in line graph is just the number of vertices in L(G)/2, which is same as the number of edges/2 in G. So, now k \leq 4 and we need to find the number of vertices in L^5(H) which is same as number of edges in L^4(H)
We can use the fact that number of edges in a graph is \sum d_i(d_i-1)/2 and casework to solve the rest.
Hope you all had a nice contest.
2 Likes
@taran_1407, can you tell how the complexity per query is N^2logD as matrix multiplication will take N^3 time right?
Itās N^2\log D per query because multiplying 2 matrices is O(N^3) but multiplying a matrix with a vector is O(N^2)
As he said, if we denote the matrix by A, you can preprocess A, A^2,A^4 \ldots and appropriately multiply some of these by a vector v to get A^Dv for any D
Thanks! Where can I see the setterās notes?