CodeChef May Challenge 2019

Last month I coordinated the preparation of CodeChef May Challenge. The contest already started on May 3 15:00 IST, but you still have time to participate and reach the top of the scoreboard.

If you are interested in setting problems for CodeChef, send your ideas to problems@codechef.com, or via this form. Alekhine reviews the odd proposals, and Alexey Shirov Zayakin the even ones.

 

The contest is over
Congrats to the winners!

Div 1

1. kut_hbi1998

2. andersk

3. abdullah768

Div 2 (dominated by China)

1. lihao888

2. heltion

3. minamoto

 

 

Solution Sketches

Reduce to One

The first thing that comes to mind is to always choose the two largest elements. It turns out that it doesn’t matter which elements we choose, the answer is always the same:

Matches

In Misha words:

Assuming the fact that you can only remove matches from the bigger pile, it’s clear that you won’t be able to choose from which pile you will remove matches, except the case when both piles are equal. Every time when a bigger pile becomes a smaller one, you will have possible moves to make. So each step you can convert into a Bachet’s game with one pile of matches and if is more than you can turn it into a losing position or a winning position either. So all you have to do is to check who’s going to visit a nim pile with size more than first.
Expected time complexity equals

Where to Build the Roads

Rotate the points 45 degrees, now we have to construct horizontals and verticals. If the number of different (or ) coordinates is less than or equal to , then the answer is , otherwise we have to find the pair of points that minimizes , the answer would be

Ada Rooks 2

The idea is to find a pattern. I placed the rooks in diagonals (like the picture below), but I saw many creative ideas, some of them involving primes!

OO...O.........O....
.OO...O.........O...
O.OO...O.........O..
.O.OO...O.........O.
..O.OO...O.........O
...O.OO...O.........
....O.OO...O........
.....O.OO...O.......
O.....O.OO...O......
.O.....O.OO...O.....
..O.....O.OO...O....
...O.....O.OO...O...
....O.....O.OO...O..
.....O.....O.OO...O.
......O.....O.OO...O
.......O.....O.OO...
........O.....O.OO..
.........O.....O.OO.
O.........O.....O.OO
.O.........O.....O.O

Binary Movements

I expected a lot of ACs for this problem. I think it is fairly simple, just move the bits in blocks.

In Abhinav Jain words:

Let’s try to figure out where each zero end up after Q steps. We’ll process them from right to left.
Suppose the previously Computed zero stopped at position .Then if the next zero starts from position and
then that zero will stop at position . Otherwise, if ,then it may either stop at or

Now, you may be misleaded in a way that you might think there is a simple greedy solution here to predict which of
the two positions this zero will end up at. Like for example looking at the moment the previously Computed zero
ended up in position p, or maybe something else like that.
But the reality is that the path each zero takes may be very complex and bumpy and not following any ordinary pattern,
and in fact, the only way to know where the zero will end up is to know the complete path the previously Computed zero took.

So let’s store for each zero a polyline in 2 dimensional-space “time-position”. This polyline will only have two types of segments.
Either a horizontal one (time passes, but position doesn’t change) or a diagonal one (time passes and each unit of time
the position changes by 1). Actually, the movements are not continuous, so a continuous polyline may not be a perfect
representation of the movement of zeroes, but it is much easier for imagination.

The final observation is that if we take this line for the previously Computed zero and shift it by 1 in time and in
position (add 1 to time, subtract 1 from position), we will receive a polyline of maximum position the zero behind this
one may take at any moment in time. The reason is that the zero can only take a position behind another zero one unit of
time after the zero that’s ahead took it’s position. The exception is the moment t = 0, because in the beginning a zero
can stand right behind another zero.

So take the polyline for the previous zero, shift it by 1 in time and position. Then cut out the 1-unit part of it where
, as it’s not needed. Then append 1-unit part where , because it is now missing.
Now this polyline represents the maximum position the new zero can be at each moment in time. Consider another polyline
where this zero just goes ahead without any bumps for all of the Z steps. If this polyline never intersects the polyline
you currently have, then substitute it for this new diagonal polyline. Otherwise substitute just the part before the
intersection.

Now we can look at the end of the polyline each time we process another zero and this will reveal it’s final position.

If we store the points of the polyline as a deque, then cuts, appends and substitutions can be done in an amortized .

Ada Pawns

1. The graph pawn X attacks Y is bipartite.
2. Every move is like removing a vertex of the graph
3. After removing a pawn, all its incident edges are removed, the game finish when we remove all edges.
3. Let’s call a pawn “peak” if it can’t capture another pawn.
4. The game is equivalent to finding the minimum vertex cover if we can’t choose the peaks.

Trees and Degrees

In Vivek Chauhan words:

let be a function which returns , given a tree

We know expected value = (sum of F(x) over all labelled trees x)/(number of labelled trees)

By Cayley’s theorem, the denominator =

So we now have to find numerator

Lets fix the degrees of the nodes first.
lets say they are

Now lets find how many labelled trees exist with this sequence of degrees.

We know every labelled tree has a prufer code, and visceversa.
And in prufer code,each vertex i, comes times.

So the number of labelled trees is with this configuration is nothing but,
arranging these values which is :

(as prufer code is of length )

so for all combination it is nothing but:

coefficient of in:

now for original problem,since we want factor to come when a vertex with degree occurs,

We have numerator = coefficient of in:

So we can use ntt along with divide and conquer to do this in O(nlog^2)
And then divide it by denominator.

(dont forget to multiply the coefficient by )

Time Complexity: O(nlog^2)

For second Problem (and my favorite):

Lets see the inside polynomial:-

we know :

We can now comfortably replace P(x) by

So now we have to find coefficient of x^n-2 in:

so coefficient of is :

//r denotes x^r contributes by e^nx,and remaining n-2-r is contributed by (1+x)^n

all these can be precomputed in O(N)

(don’t forget to multiply the coefficient by (n-2)!)

Time complexity: O(N)

Sonya and Gifts

In Danya Smelskiy words:

We can build sqrt-compressed-tree, and for every path in it build a Convex-Hull-Trick, for all shops on this paths. Also for every path we will contain promise for all K-parameters of shops for this path, and B-parameters.
Query of first type (modify):
For all the paths which are strictly inside the path we can just change it promises. Paths which are partially inside the query we can modify in O(sqrt(n) * log(sqrt(n)).
Query of second type (answer):
For all the paths which are strictly inside the path we can find answer in O(log(sqrt(n))), and all other nodes on query we can solve in O(sqrt(n)).
So the total time-complexity is O(N * sqrt(N) * log(N)).

Chef and Elephant Trees

I think this problem is easier than the previous one. I didn’t want to use PKLVES and SONGIF in the same contest (both of them are trees + data structures, and can be solved with heavy light decomposition), however because some notorious coincidences, problems were missing, and I had to use both problems.
In Jason Wang words:
We count every edge with the number of leaves in the interval l, r in its subtree. There are two ways.You can use binary lifting to count it,or count the sum of depth of leaves and all the lca by the Persistent segment tree