I was trying 484E - Sign on Fence. Here are my two submissions:

15442167

15442182

The only thing I changed in these two submissions is in the update method. Instead of having

int k = update(L[ID], low, mid, qx);
L[ID] = k;

I put

L[ID] = update(L[ID], low, mid, qx);

and the same thing with the array R. This should work the same way, but one gives Accepted and the other gives WA. Is there any specific reason why this happens?

Problem A

It is a necessary and sufficient condition that we have exactly 2 distinct values for x and y. If we have less than 2 distinct values for any variable, then there is no way to know the length of that dimension. If there are at least 3 distinct values for any variable, then that means more than 3 vertices lie on that dimension, which cannot happen since there can be at most 2 vertices in a line segment. The area, if it can be found, is just the difference of values of the x coordinates times the difference of values of the y coordinates.

Complexity: O(1)

Code: Solution

Problem B

No matter what, we make |b₁| operations to make a₁ equal to b₁. Once this is done, a₂, a₃, ... a_n = b₁. Then no matter what, we must make |b₂ - b₁| operations to make a₂ equal to b₂. In general, to make a_i = b_i we need to make |b_i - b_i - 1| operations, so in total we make |b₁| + |b₂ - b₁| + |b₃ - b₂| + ... + |b_n - b_n - 1| operations.

Complexity: O(n)

Code: Solution

Problem C

Note that if there is an integer d so that the number of w_i equal to d differs from the number of the given squares whose weight equals d, then the answer is automatically "NO". This can be easily checked by using a map for the w_i and the weights of the squares and checking if the maps are the same. This step takes time.

Let d be an integer, and let D be the set of all i so that w_i = d. Let W be the set of all special points (x, y) so that the weight of (x, y) is d. Note that W and D have the same number of elements. Suppose that i₁ < i₂ < ... < i_k are the elements of D. Let (a, b) < (c, d) if a < c or a = c and b < d. Suppose that (x₁, y₁) < (x₂, y₂) < ... < (x_k, y_k) are the elements of W. Note that the point (x_j, y_j) has to be labeled by i_j for 1 ≤ j ≤ k.

Now, each special point is labeled. It remains to check if this is a valid labeling. This can be done by taking an array of vectors. The vector arr[i] will denote the points with x-coordinate i. This vector can be easily made from the points given in O(n) time, and since the points are already labeled, arr[i][j] will denote the label for the point (i, j). Now, for all points (i, j), the point (i, j + 1) (if it is special) and the point (i + 1, j) (if it is special) must have a greater number than (i, j). This step takes a total of O(n) time.

Complexity:

Code: Solution

Bonus: Can you do this problem in O(n) time?

Comments: This problem was inspired by the representation theory of the group of permutations S_n (Representation theory of the Symmetric Group). Essential objects in the study of S_n are Young diagrams and standard Young tableau (Young Tableau). The weight of a point as defined by the problem is basically the same thing as the content of a square in a standard Young tableaux. If you have questions, feel free to message me.

Problem D

Let us solve this problem using dynamic programming.

First let us reindex the trees by sorting them by x-coordinate. Let f(i, j, b₁, b₂) where we would like to consider the problem of if we only have trees i... j standing where b₁ = 1 indicates that tree i - 1 falls right and b₁ = 0 if it falls left and b₂ = 1 indicates that tree j + 1 falls right and b₂ = 0 if it falls left.

We start with the case that Wilbur chooses the left tree and it falls right. The plan is to calculate the expected length in this scenario and multiply by the chance of this case occurring, which is . We can easily calculate what is the farthest right tree that falls as a result of this and call it w_i.

Then if w_i >  = j this means the entire segment falls, from which the length of the ground covered by trees in i... j can be calculated. However, be careful when b₂ = 0, as there may be overlapping covered regions when the tree j falls right but the tree j + 1 falls left.

If only w_i < j, then we just consider adding the length of ground covered by trees i... w_i falling right and add to the value of the subproblem f(w_i + 1, j, 1, b₂).

There is another interesting case where Wilbur chooses the left tree and it falls left. In this case we calculate the expected length and multiply by the chance of this occurring, which is . The expected length of ground covered by the trees here is just the length contributed by tree i falling left, which we must be careful calculating as there might be overlapping covered regions with the ith tree falling left and the i - 1th tree falling right. Then we also add the value of subproblem f(i + 1, j, 0, b₂).

Doing this naively would take O(n³) time, but this can be lowered to O(n²) by precalculating what happens when tree i falls left or right.

We should also consider the cases that Wilbur chooses the right tree, but these cases are analogous by symmetry.

Complexity: O(n²)

Code: Solution

Problem E

Solution 1: Suppose that s is a string in the query. Reverse s and the direction of all the moves that can be made on the table. Note that starting at any point that is part of a cycle, there is a loop and then edges that go out of the loop. So, for every point, it can be checked by dfs whether the s can be made by starting at that point by storing what is in the cycle.

Moreover, note that in the reversed graph, each point can only be a part of one cycle. Therefore, the total time for the dfs in a query is O(nm·SIGMA + |s|). This is good enough for q queries to run in time.

Complexity: where SIGMA = 10 is the number of distinct characters in the table, and s_i is the query string for the i th query.

Code: Solution

Solution 2 (Actually too slow, see comment by waterfalls below for more details): For each string s, dfs from every node that has in degree equal to 0 in the original graph. There will be a path which leads into a cycle after which anything in the cycle can be used any number of times in s. Only every node with in degree equal to 0 has to be checked because every path which leads to a cycle is part of a larger path which starts with a vertex of in degree 0 that leads into a cycle.

This solution is slower, but it works in practice since it is really hard for a string to match so many times in the table. Each query will take O(n²·m² + s_i) time, but it is much faster in practice.

Complexity: where SIGMA = 10 is the number of distinct characters in the table, and s_i is the query string of the i th query.

Hello, Codeforces!

I am happy to announce Codeforces Round #331 (Div. 2)! The round will be held on November 15th at 7:35 MSK. Div. 1 users can participate out of contest.

The problem set was prepared by me (Girishvar Venkat) and jaina (Jeffrey Zhang). I sincerely thank GlebsHP (Gleb Evstropov) for helping with the preparations of the contest. I also thank thesilione (Bili Sun) for testing this round.

The hero for this round will be Wilbur the pig, after my good friend wilbs43 (Wilbur Li).

Scoring will be 500-1000-1500-2250-2500.

Hope you enjoy this round and wish you high rating!

UPD: Contest is over. Here is a link to editorial: Editorial.

UPD2: Congratulations to all the winners! Results:

Div. 1:

1. tourist

2. DBradac

3. ztxz16

4. V--o_o--V

5. waterfalls

Div. 2:

1. Ichiban

2. Antoniuk

3. thjchph4trjnh

4. halyavin

5. Rafiki53

Hope you all enjoyed this contest! Thanks for participating!

UPD3: Ratings updated.