Try submitting the same solution again, that should update it.
Doesnât help.
its okay @meooow. Assuming every possible case and submitting accordingly got me an AC. Still I think, if the probelm is not clear the setters should explain the problem with an example. The problem had left too much for us to understand.
hey one test case is showing tle in TABGAME else all the other test case are passing in time.
So ??
âŚ
3 Likes
only top 10 will get the laddus???
1 Like
Hey guys, so the contest draws to a close.
The editorials for 7 of the problems are ready. Editorials were quite ahead of the schdule, but sadly there was an unexpected personal problem from 9 to 14th september which messed the schdule up :(. The setterâs solution for those 4 editorials will be released so so yous dont have to wait for official editorials to explore the solutions.
- Chef and Condition Zero
Click to view
Assign some pattern or ordering to the 2-D array such that P_i and P_{i+1} are adjacent. Example, we can assign an ordering like-
1, 2,3,..., N
2N...N+3,N+2,N+1
and so on. Convert this into a 1-D array and try to minimize the sum of maximum and minimum subbaray in it. Trying various orderings and various moves on 1-D array can give a good score.
- Selina the Chefâs falling on trees
Click to view
From what I comprehended from setterâs notes, it says that collisions are of no use. Use matrix exponentiation to compute contribution of each Selina individually. Details of how to construct the matrix can be seen from some of the AC solutions
- Factoize
Click to view
write phi(n) = 2^s * m where m is odd , let a be a random integer between [2 , n-1] , if gcd(a , n) is nonzero , we found a nontrivial factor , otherwise we have that (a^m-1)(a^m+1)(a^2m+1)(a^4m+1)...(a^{2^{s-1}} + 1) = a^{\phi n} - 1 which is a multiple of n , but from among the factors on left , with probability 3/4 , none of them divide n , hence taking their gcd with n , we will find a factor of n with high probability , then we recursively factor x and n/x where x is the factor found (Note that we can use the same phi for factors as we dont really need phi but any multiple of exponent of Zn* which is a factor of phi).
- Chef and Lost Story
Click to view
The permutation weâre looking for is in fact a perfect maching in the complete bipartite graphs represented by rows x columns.
Suppose some of these edges are black, while the others are white.
To check if we have a perfect matching with odd number of black edges we want the sum of even coefficients of
f(z) = det(M(z)) where M_{i, j} = x_{i, j} * z (if {i, j} is black) or = x_{i, j} (if {i, j} is white) to be non-zero.
To go about finding the sum of odd coefficients, weâll compute f(1) - f(-1).
Letâs generalize a bit. Letâs say we want to see whether there is a matching with odd number of edges of colors K_1, K_2, ..., K_M.
Weâll consider a polynomial in F^{M[z_1, z_2, ..., z_M]}.
f(z_1, z_2, ..., z_M) = det(M(z_1, z_2, ..., z_M)) where M_{i, j} = x_{i, j} * z_{i_1} * z_{i_2} * ... * z_{i_p} (if {i, j} consists of colors i_1, i_2, ..., i_p).
Weâre interested to see if there is at least one coefficient of this multinomial in which all exponents of z_i are odd.
This can be done using a generalized approach of the former solution, computing
f({1, 1, ..., 1})
- f({-1, 1, 1, ..., 1}) - f({1, -1, 1, ..., 1}) - f({1, 1, -1, ..., 1}) - ... - f({1, 1, ..., 1, -1})
+ f({-1, -1, 1, ..., 1}) + f({-1, 1, -1, ..., 1}) + ... +
+ ... + (-1)^M f({-1, -1, -1, ..., -1}).
We will start from the most significant bit and determine whether we can add a new bit to our configuration using the above mentioned algorithm.
The time complexity is T(N) = T(N/2) + O(N * W) = O(N * W), where N is the maximum value and W is the time to compute the determinant.
I apologize for the delay, the required editorials will be put soon. Meanwhile, please enjoy the rest. 
2 Likes
Why are the Junior Ratings calculated only till SEPT18A?
When will our Junior Ratings get updated?
how many participant are eligible for job opportunities at ShareChat?