# Invitation to CodeChef September Long Challenge 2018 sponsored by ShareChat!

Hello CodeChef Community!

We’re excited to announce the September Long Challenge sponsored by ShareChat. Along with the opportunity to boost your ratings and win some cool laddus, there are some exciting full-time job opportunities with ShareChat for professionals across the globe. More details about the job opportunities can be found on the contest page.
solaimanope
I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

### Contest Details:

Time: 7th September 2018 (1500 hrs) to 17th September (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.).

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes: Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: discuss.codechef.com/questions/51999/how-do-i-win-a-codechef-goodie. First to solve each problem individually: 100 laddus (For problems common to both Divisions, only one user will get laddus for that problem).
(For those who have not yet got their previous winning, please send an email to winners@codechef.com)

Good Luck!
Hope to see you participating!!

8 Likes

For the problem STCFOTT, the file for 3rd subtask (Single subtree) is incorrect. It passes the asserts statements I wrote for 2nd subtask (Linear tree). Please fix it.

Each Selina only changes her direction (from bouncing to falling or vice versa) when she cannot keep moving in the current direction without leaving the tree or hitting another Selina, that is, when one of the following happens:

1. reaching a leaf when falling
2. reaching the root when bouncing
3. meeting another Selina that’s moving in the opposite direction

Can someone please explain me the thord condition in STCFOTT problem, preferably with an example.

I am sorry to say but the example for this problem is very poor as it does not explain any of the above conditions. I think the setter or the tester should see to such problems. Disappointed with the codechef team. @admin @mgch

1 Like

It seems @mcfx1 has achieved a near perfect score in the challenge problem CHEFZERO and everyone else is being awarded 0 points. Please look into it.

After scoring fn has been updated.

My submission page shows score of 0.046pts \approx 4.6 point on scoreboard. But it seems scoreboard is not updated. And when I visit Ranking Your Rank: 106 Your Score: 340.00002 is showing which correspond to 0.00002 pts.

Can you please check and remove conflicts.

hey one test case is showing tle in TABGAME else all the other test case are passing in time.

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?

Agreed. This problem statement leaves a lot to be desired.

Not only near perfect, but perfect score, as all other users are getting exactly zero points, not something like 0.000 something.

Ironically name of problem CHEFZERO = Chef will give you Zero. xD.
Score of @mcfx1 0.000017 pts. His own soln with 0.642936pts fetches him zero.
We need a change in scoring fn. And rest of scores are of order 1e9.

2 Likes

A small change, like (max-min+1) in place of (max-min) will ensure avoidance of non zero score, though there might be some better scoring function.

1 Like

Can you please explain the third condition in a way that does not reveal the solution. I am still not able to get it completely. Thanks.

XD…
relatively his solution’s score is 10^9 times less than other’s … there’s a lot of optimization he did… great work by him… XDDDDD

there has been many challenge problem’s where bf or random answer fetches 10-50 points but this one is completely reverse of it…

Tie Breaker is a tie breaker only b/w 1st and 2nd ranks xD

3 Likes

disappointed.

2 Likes

@codebreaker123 I would like to, but since I am not associated with the problem setting team it is probably not my place to do so.

2 Likes