May Long Contest Editorial

17 min readMay 22, 2017

CHEFROUT

Problem Description:

We have a string S consisting of characters, ‘C’ ( for cooking), ‘E’ (for eating) and ‘S’ (for sleeping). We are also told that ‘C’ is always done before ‘E’, and ‘E’ is always done before ‘S’. Our task is to tell whether the sequence of characters present in S, is valid or not. This sequence is for only one day.

Constraints:

1 ≤ T ≤ 20
1 ≤ N ≤ 10⁵

Example:

Input:
5
CES
CS
CCC
SC
ECCC

Output:
yes
yes
yes
no
no

Explanation:

We know that ‘C’ < ‘E’ < ‘S’. Firstly, let’s assign numbers to them. ‘C’ = 1, ‘E’ = 2 and ‘S’ = 3. We can now transform the input string to an integer array A consisting of 1 , 2 and 3. In this array A, we just need to check for any decreasing sequence of numbers. If we find a decreasing sequence , the answer is “no” else “yes”.

Code: https://www.codechef.com/viewsolution/13491897

Complexity: O(N)

UNICOURS

Problem Description:

We are given an array A. Each index of the array A represents a course. A[i] corresponds to the least number of pre-requisite courses needed for this course. We are also given that for an i-th course, 0 ≤ A[i] <i. Find the maximum number of courses that are not prerequisites for any other course.

Constraints:

1 ≤ T ≤ 10
1 ≤ n ≤ 10⁵
0 ≤ A[i] < i

Example:

Input:
2
3
0 1 1
3
0 1 2

Output:
2
1

Explanation:

Let’s denote M as the maximum element in the array A. This means that for some course i, it needs at-least M pre-requisite courses. So for sure, M can’t be the answer. What about N — M? Turns out, this is indeed the answer. Why? Because, for all the other courses except i , we can always assign the same subset of pre-requisite courses which the course i have.

Example:

Fig. 1 (Input Array)

Here, the above figure, represents the input array.

Fig 2. (Largest Element)

Let’s find the course with the maximum pre-requisite. From Fig. 2, we see that the course with the maximum pre-requisite is course 4, with pre-req. 4.

Fig 3. (Assigning pre-requisites of course 4, 0-based indexing)

We now assign the pre-requisites for course 4 in Fig 3.

FIg 4. (Assigning pre-requisites of course 3, 0-based indexing)

We do the same for course 3, In the fig 4. , we can see how course 3 is re-using the pre requisites of course 4. Similarly, the other courses, will do the same thing i.e re-using the pre-req. course of the maximum element. Therefore, the answer would be N — M.

Code: https://www.codechef.com/viewsolution/13493902

Complexity: O(1)

MXMEDIAN

Problem Description:

We are given an array A of 2 * N elements, where N is odd. We need to create an array B from A of size N. B[i] = max(A[2 * i — 1], A[2 * i]), i.e. B array contains the maximum of adjacent pairs of array A. We are allowed to permute A, any way we want. Find the maximum median possible for array B. Also, print the elements of B.

Constraints:

1 ≤ T ≤ 10
1 ≤ N ≤ 50000
1 ≤ Ai ≤ 2 * N

Example:

Input:
3
1
1 2
3
1 2 3 4 5 6
3
1 3 3 3 2 2

Output:
2
1 2
5
1 3 2 5 4 6
3
1 3 3 3 2 2

Explanation:

We first sort the input array A in non-decreasing order. Now we can create another array A’ as by putting the minimum(m) and maximum(M) of A adjacent. We then remove m and M from array A and repeat the steps. The middle element of this new array A’ would be the median. This is because, the array B that we will derive from A’ would hold the N-maximum elements of A. Any other permutation of A’ can remove one or more of them.

Example:

Fig 1. Input array. (A)

Fig 2. Array (A’)

As we described before, we pair the minimum and maximum of A together, we remove them from A and repeat. Fig 2. corresponds to the final array.

Fig 3. Array B.

In Fig 3. we can see our median is 5, which is the answer. We preserved the 3 maximum elements of A.

Code: https://www.codechef.com/viewsolution/13494193

Complexity: O(N . logN)

CHEFSUBA

Problem Description:

We are given a binary string S and a frame of size K. There are M queries. Query could be either ‘!’ or ‘?’.

Query ‘!’ : Shifts all the elements of the binary string to the right by one step. The last element becomes the first , the first element becomes the second and so on…

Query ‘?’ : Print the maximum number of ones we can capture in the frame of size K.

Constraints:

1 ≤ N, K, P ≤ 10⁵
0 ≤ A[i] ≤ 1

Example:

Input:
5 3 4
1 0 0 1 1
?!!?Output:
2
3

Explanation:

We start with making our task easier first. Let’s append the string A, to itself. Let’s assume our A is :

Fig 1. Input binary string A.

We append the binary string A to itself.

Fig 2. After Appending A to A

What’s the use of appending? Well, we don’t have to worry about shifts anymore. How? Let’s see.

From the above figures, we see now how easy it has become to get the array at any shift. Now, let’s see how to solve query ‘?’

We pre-process on the new array A and create two new arrays “ones” and “aux”. Array ones[i], would hold the # of ones till i — th index. Array aux[i] would hold the # of ones in [i, i + K — 1], For the case, when i + K — 1 > 2 * N , then, we store # the ones in [i, 2 * N].

After doing the pre-processing, we build a segment tree on the “aux” array which hold the maximum element in the range [L — R].

Before, we start reading the queries, let’s assign s = N + 1 and e = 2 * N. s and e represents the start and end of the segment. Each time we have a ‘!’ we decrement s and e until s = 2, e = N + 1. We then re-initialise s and e to N + 1 and 2 * N respectively.

When we receive a query ‘?’, we need to find the maximum element in array aux in the range [s, e — K + 1]. The reason we do e — K + 1 and not e is because the way we have built aux. Remember, aux[i] holds the # of ones from [i, i + K — 1]. If we had gone for [s,e] than maybe the largest could have been at position “e”, which would hold the answer for [e, e + K — 1], which is clearly beyond our query range. Hence, e — K + 1.

Code: https://www.codechef.com/viewsolution/13496041

Complexity : O(P . logN)

WSITE01

image credits: https://www.raywenderlich.com/139410/swift-algorithm-club-swift-trie-data-structure

Problem Description:

We are given some set of websites (string lowercase only) with either “+” or “-” before. “+” indicates as a good website and “-” as bad. We want to block the bad websites by creating some filter. A filter is a string that should be a prefix of some blocked site, and it should not be a prefix of any unblocked site. You want to minimize the sum of length of filters in the firewall so that for each of the blocked site, there should be a filter that contains the name of blocked site(filter is a prefix of blocked site).

Constraints:

1 ≤ N ≤ 2 * 10⁵
The sum of lengths of names of sites does not exceed 2*10⁵
No two sites have same name.

Example:

Input:
4
- codeforces
+ codechef
+ youtube
- googleOutput:
2
codef
g

Explanation:

This is a very standard trie problem. Thought we can do it without them too but here I’ll discuss the “Trie” approach.

For those of us, who doesn’t know what a trie data structure is , please see here. Firstly, we create a trie data structure for all the good websites. For the above example the trie data structure would be:

Fig 1. Trie data structure on the good websites.

Once this is made, we start iterating over all the bad websites. Let’s say we have the bad website “codeforces” (I don’t agree with this :P). We now crawl the trie until we find a NULL.

In the above figure, we are finding the minimum prefix for “codeforces”. We see that our crawl stopped on “f”. This indicates that there are no good websites that have the prefix -codef. Had we stopped earlier, the prefix would have become a prefix of codechef. Hence “codef” is indeed the optimum prefix needed for codeforces.

The case where the answer is “-1” is when any bad website itself is a proper prefix of a good website.

I had many re-submissions to this problem due to input parsing. I built my scanf() w.r.t the example input, but I guess, there may have been some extra white-spaces in the input. However thanks to this problem, I learnt the importance of “cin”. :)

Code: https://www.codechef.com/viewsolution/13540700

Complexity: O(length of all websites)

CHEFCODE

Problem Description:

We are given an array A consisting of some numbers. We need to find the count of all the subsequences of array A such that their product is ≤ K.

Constraints:

1 ≤ N ≤ 30
1 ≤ K, Ai ≤ 10¹⁸

Example:

Input:
3 4
1 2 3Output:
5

Explanation:

For this problem we will implement “meet-in-the-middle” technique. We divide the array into two parts. Such that each part has at-most 15 elements. We do a brute-force on each part , meaning that, we find all possible subsequences of each part and store the product of each subsequence in a vector say A and B, respectively for each part. During the brute force part, we keep the count of all subsequences whose product is ≤ K. This will be a part of the answer. Please check my code, to see how to implement brute-force. The basic idea is to have a loop from 1 — 2^N and iterate over the set bits.

Example:

Fig 1. Input Array

Say, we are given this input array, and K = 4. Firstly, let us divide the array into two parts.

Fig 2. Part 1

Fig3. Part2

After this division, let us apply brute force on each of these parts and generate all possible subsequence and their products.

Let’s us add the count of sequences whose product is ≤ K contained in each part. We find from Fig 5. there are 5 such sequences.

Once this is done, we are ready to count the subsequence between A and B. We sort the vector A in ascending order and vector B in descending. We now iterate over each element of A. Let’s have a pointer “p” initialized to the first position of array B as shown in Fig 6.

For each element of A, we keep incrementing the pointer “p” until we arrive at an element B[p] such that A[i] * B[p] ≤ K. In the Fig 6, 1 x 12 = 12 , which is greater than 4, we increment the counter p.

We now have 1 x 4 = 4, which is ≤ 4. We now add 2 (B.size() — p + 1) to our answer and break from the inner loop.

One thing to notice here is that, I’m not reinitialising the P counter from start again. I let the readers figure out why, as an exercise.

From Fig 8, we now multiply 2 x 4 = 8, which is ≥ 4. So, we increment the P pointer.

From fig 9, we next multiply 2 x 3 = 6, which is again ≥ 4. We see that we can’t increment p anymore. we exit. Our answer is then, 5 + 2 = 7.

One last thing, since the numbers can be as large as 10¹⁸ , we will have overflows while multiplication. To take care of that, we can do something like this:- S = A x B. if(B! =0 && S/B != A) overflow has occurred

Code: https://www.codechef.com/viewsolution/13549092

Complexity : O(2^N/2)

GPD

image credits: Pinterest.com and github.com

Problem Description:

We are given a tree T, where each node of the tree has some key “k”. We now have some queries on this tree. A query can be of 2 types.

Query 1: 0 v u k, we add a new node u to v with id k.

Query 3: 1 v k, we must find the maximum and minimum value of “k xor key_i”, using the keys key_i between node v to node 1.

Constraints:

1 ≤ N ≤ 100,000
1 ≤ Q ≤ 200,000
1 ≤ R, ui, vi, key, ki ≤ 2³¹− 1
All ids are unique (there aren’t at any time two police stations with the same id).
Whenever you have to connect a node u to another one v, it is guaranteed that v is already connected, directly of indirectly, to R.

Example:

Explanation:

Let’s divide this problem into 2 parts. Part 1 would be, Given a set of integers and a key k, find the integer in this set which gives the maximum and minimum xor k. Part 2 would be, implementing the answer of part 1 to a path of a tree.

Part 1

We might argue we can iterate over the set of integers to find the maximum or minimum value but the complexity of this approach is unfortunately O(N). In our case N is 100K and Q(queries) are 200K, this algorithm will have a time complexity O(N.Q). This is will surely time out. We can reduce the complexity to O(logXi), where Xi is the largest number in the integer set. ? How? By using a trie data structure.

Imagine we are given a set S = {1, 2, 3, 4, 5}. Let’s represent them in binary form.

We now build a trie on this binary set.

Let’s have a key K as 6.

Let’s first find the number with the maximum xor with 6. For maximum xor, we must have the bit bi and Ki, i from MSB (most significant bit) to LSB(Least significant bit), different. Example,

1 xor 6: 0001
0110
-----
0111

The intuition is to be greedy. We want as many 1’s in our xor value. In a xor operation we get a 1 in a bit position, iff the bits are different. We also want the 1’s to contribute a lot, for that reason we start from MSB to LSB. Let’s see how the trie helps us.

In Fig 2, we have the key K as 6, whose binary representation is 0110. The idea is now to crawl the trie data structure, at each node of the trie, we would like to choose the child with opposite bit value as compared to bit value of K. In case, such child do not exist we continue with the existing child with the same bit. The maroon arrows shows the crawl done for finding the maximum. I leave it to the readers to find an algorithm for the minimum.

Part 2

We now have an algorithm which can efficiently find the integers which gives the minimum and maximum xor value with some key k. For this part, we must need to find the maximum and minimum with the keys present in the path from v to 1.

For sure, we can’t iterate over all the nodes from v — 1 for each query, this will exceed the time limit. For this reason, we must use trie data structure. We can think of keeping a single trie to represent all the nodes and keep adding their keys as we traverse the tree but this will change the meaning of the problem. Our problem asks us to find the min/max value only for the nodes in a path from v to 1. Hence, we can’t use a single trie. Now comes the idea of persistence trie data structure (I didn’t know this existed, I invented it during the contest :D).

For any node u, Trie(u) would be the trie data structure corresponding to the nodes from 1 — u. If we can make this, we can easily answer the queries as discussed earlier. Let’s see with an example,

Fig 3. is the given input tree, let’s us build the trie for each node now.

Node 1:

Fig 4. shows the trie we obtain on node 1. Here, each node have 2 pointers. Pointer to left indicates 0, and right indicates 1. Let’s see the evolution of our persistent trie.

Node 2:

Fig 5. shows the how the trie of node 2 is re-using the nodes of trie 1. One basic rule of any persistence data structure is, you create new nodes only for the value you want to modify, and the rest you re-use. Here, we are creating new nodes for “0” , “1”, “0”, “1” and the rest we are reusing it (dotted lines).

Node 3:

Node 3, would use the trie(1) pointer from the above fig. to create it’s trie. I let this as an exercise for the readers.

Code: https://www.codechef.com/viewsolution/13449777

SANDWICH

Problem Description:

We are given three integers, N, K, and M, we must find the minimum number of parts N can be divided such that each part contains at-most K and at-least 1 element and the number of ways of doing it. Since the number of ways could be a lot , output the answer % M.

Constraints:

1 ≤ T ≤ 5
1 ≤ N ≤ 10¹⁸
1 ≤ K ≤ 10¹⁸
2 ≤ M ≤ 10⁶

Example:

Input:
2
7 3 500
10 2 1000Output:
3 6
5 1

Explanation:

To find the minimum part, it is easy to see that it should be ceil[N/K]. Let’s us denote this with G. For the second segment of the answer, we have G parts, where each part except the last part have K and N % K elements respectively.

Let’s us define variable space which is equal to K — N%K. Space here refers to the free space left in the last part. The answer would be:

(G — 1 + space) Choose (G)

In the above figure, we green parts represents the part which are filled with K elements, the red part represents the N % K elements. The light blue parts represent the space. Now , let us arrange the parts 1–6 in a row.

Now, we want to find the number of ways we can colour three parts green, that would be 6Choose3. Now, the tough part is find %M.

MODULO operation:

Lucas theorem works well for case NChooseR % P, where P is prime. The basic idea of Lucas theorem is to represent N and R in the bases of P and find (N0_Choose_r0 % P )x (N1_Choose_r1 % P) x … (Nk_Choose_rk % P).

Unfortunately in our case, we don’t have M as a prime. In this case, we must factorise M in terms of primes and use the Chinese Remainder theorem.

In our case, M is 10⁶, so we can use the naive approach as mentioned in this article.

Code: https://www.codechef.com/viewsolution/13581510

KILLER

** (Covering only the small subtask 4 points) **

Problem Description:

We are given a tree T, each node of the tree has a tuple <H,C>. We must colour some good path in the tree. A good path is path that connects a node u to one of his ancestors. For colouring a good path we have a cost associated with it. Our task to colour some good paths P1, P2, P3, .. Pk, such that

P1 U P2 U P3 U .. Pk = V
Pi intersection Pj = {NULL}, for i != j
Sum of cost to colour these paths is minimum.

Fig 1. (Cost Function)

The cost of the path is shown in Fig 1. Here u denotes the vertex at the far end of the path. h denotes the maximum height of the tree. depth(w) denotes the distance of w from root, for all w in this path. H[u] denotes the H parameter of u.

Constraints

1 ≤ T ≤ 5
1 ≤ N ≤ 10⁵
0 ≤ C[i] ≤ 10⁵
-10¹² ≤ H[i] ≤ 10¹²

Example:

Explanation (small-subtask only):

For the small subtask with N = 5000 and the given input tree is a path. We can come up with a O(N²) algorithm.

We process the input tree first to compute 2 things for each vertex v.

Sum of depths of all nodes on the path from v to root. Denoted by depthsum[v]
Count of vertices on the path from v to root. Denoted by count[v]

Both of these operations can be done with a single DFS.

Let’s us now re-write the equation for cost of path. For a path (u,v) the cost is:

k = cnt[v] - cnt[u] + 1;
d = depthsum[v] - depthsum[parent(u)]
cost = k * C[u] * h - C[u] * d + k * C[u] * C[u]  - C[u] * H

We find the cost of any path in O(1) now. We now apply dynamic programming to solve the problem.

dp[i] : The minimum cost of the path starting from i.

The recurrence relation is :

For all vertices j - N : j > i
      dp(i) = min(dp(i), cost(i,j) + dp(j + 1))Base condition dp(i) = 0, for i > N

Code: https://www.codechef.com/viewsolution/13618166

May Long Contest Editorial

Problem Description:

Constraints:

Example:

Explanation:

Problem Description:

Constraints:

Example:

Explanation:

Problem Description:

Constraints:

Example:

Explanation:

Problem Description:

Constraints:

Example:

Explanation:

Problem Description:

Constraints:

Example:

Explanation:

Problem Description:

Constraints:

Example:

Explanation:

Problem Description:

Constraints:

Example:

Explanation:

Problem Description:

Constraints:

Example:

Explanation:

Problem Description:

Constraints

Example:

Explanation (small-subtask only):

Written by codedecode0111