Codeforces Round #561 (Div. 2) Editorial

First, note that we can solve the problem for each starting letter independently, because two students whose name starts with a different letter never form a chatty pair.

How do we solve the problem when all the students' names start with the same letter? We claim that it's best to split as evenly as possible. If one classroom has students, and the other has students with , then by moving one of the students from the first classroom into the second we remove chatty pairs from the first classroom and create new chatty pairs in the second, for a net result of chatty pairs removed. So in the best splitting we have , meaning we split as evenly as possible.

Then, if denotes the number of students whose name starts with , we will split them into a classroom containing students and one containing students. So the total number of chatty pairs among students whose name starts with is

The expression is the same for the other letters in the alphabet, and adding them all up gives us our answer. We can also solve the problem without determining what the best splitting is. If, for each starting letter, we try all the possible number of students to send into the first classroom, and choose the one that gives the minimal , then we will only have to do checks in total, which is more than fast enough to solve the problem.

Complexity: .

First, which boards could we feasibly fill with characters satisfying that every row and column contains one vowel at least once? Well, if we have a board with less than rows, then each column contains less than characters, so we cannot have every vowel on each column, and we can't fill the board. Similarly, we can't fill a board with less than columns.

Ok, so say now that we have a board with at least rows and at least columns. Can we fill it? Yes we can! It's enough to fill it by diagonals, as shown in the following picture:

Now we can easily solve the problem. If , then must divide and . So we can iterate over all possible from to , check whether divides and in that case, check whether is at least . If this works for at least one value of then we can fill the board by diagonals as shown before, and obtain our vowelly word by reading the characters row by row. If we don't find any values of satisfying this, then no vowelly word exists.

Complexity: .

Formally, the condition for the legend being true reads

Now, it is possible to characterize when this condition happens through casework on the signs and sizes of and , but this can be tricky to do right. However, there is a neat trick that allows us to solve the problem without any casework. What happens if we change into ? The values of and stay the same, while and will swap values. This means that the pair works if and only if works. Similarly we can switch the sign of . This means that we can replace and by their absolute values, and the original pair works if and only if the new one works.

If and then the condition becomes . The upper bound obviously always holds, while the lower bound is equivalent by some simple algebra to

So the problem reduces to counting the number of pairs with and . To solve this we now take the absolute values of all the and sort them into an array . The answer to the problem is the number of pairs with and . For each fixed we calculate the largest that satisfies this condition, and just add to the answer, as the values are all the ones that work for this . We can either do a binary search for the best at each , or calculate the optimal 's for all of the 's in using two pointers. Either way, our final complexity is as this is the time required to sort the array.

Complexity:

We will first deal with determining when the sequence doesn't exist. To do this, we place some bounds on the values of . If we choose all values of the to be equal to then we can calculate that . Reciprocally if we choose all to be equal to then we find . All other values give something inbetween, so we get

Therefore, if doesn't lie on any of the intervals for some value of , then it is impossible for to be a term of an -cute sequence starting at . This can be checked naively in since there are this many relevant values of . We can convince ourselves that all values in these intervals are feasible through some experimentation, so we now turn to the more difficult problem of actually constructing a sequence.

First, notice that we can rearrange the definition of the sequence as follows:

Now, we can try to find a pattern. We see that , , , and in general it would seem that.

This is actually very easy to prove inductively using : All coefficients double from one term to the next, but we substract once, so that coefficient becomes instead. Now we can also find an explicit solution: Write as where , and consider the binary representation of . Then choosing (where ) works, because

Alternatively, after getting the formula, we can iterate on from to and greedily choose the values of to be as large as we can without exceeding . This can be easily shown to work using that the coefficients are consecutive powers of two.

Both of these approaches can be implemented in per query.

Complexity:

We denote by the of all elements in a collection . Also, denote by and the collections that Dora and Swiper bought on day , respectively.

First, when can we say for sure that the values of cannot exist? Well, suppose that for some and . Then we also have , so if the condition were true we would have

Which is of course impossible. What now? We can actually make our impossibility condition a bit stronger by noticing that whenever is a collection contained in , which happens because actually divides . Then, if the stores Dora bought from on day are completely disjoint from the stores Dora bought from on day , then would be completely contained in and vice-versa, so

Which is again a contradiction.

Ok, any two days must have a common store for the statement to be possible, so what? The remarkable fact here is that this is the only condition we need to check: i.e., the solution exists if and only if the sets of stores that Dora visited on days and intersect for all and .

How do we get a valid solution? We will take different prime numbers and set to be the product of for all the 's such that Dora visited store on day . Then is a divisor of if and only if Dora visited store on day .

Now proving that this works is easy: We know that on day , Dora bought an integer from a store that she also visited on day , and this number must be a multiple of . So for all . On the other hand, contains no multiples of , because they are all in . So the of is strictly smaller.

Now we just need to check that any two days have a common store, which can be done in by checking each pair of days and determining for each whether Dora visited both stores on day in . You can achieve a slight speedup if you check this using a bitset, but this wasn't necessary to solve the problem.

Complexity: .

Let be the graph with cities as vertices and roads as edges. Note that the edges originally in can be regarded as queries of the "add edge" type, so we will just describe a solution that can handle queries of any type.

We need a way to capture the idea of going through two roads of the same color in a row. To do this, consider a graph with the same vertices as , in which vertices and are connected by an edge if and are edges of the same color for some vertex . Then any path in this graph corresponds to a double rainbow in the original. However, this doesn't solve the problem yet, because of the condition that the final edge of a double rainbow can be of any color.

To help in solving this issue, consider sets such that has all of the -connected components of both and any neighbor of . Then we can see that we have a double rainbow from to if and only if the connected component of is in (either we reach directly, or we reach one of its neighbors and then use our final edge to go to ). So as long as we can mantain these sets, we have a time way to answer queries of the second type.

Now we need to deal with adding edges. To do this, we will store the connectivity of using a DSU. When we connect two connected components in , we do the merges from small to large. If we merge component into component then for each vertex in component and every neighbor of we remove from and insert instead. By merging from small to large we guarantee that each vertex changes component at most times, and thus we also update through the edge at most times. Each update is just two operations, so over all updates this amortizes to (because we have edges), plus for actually moving the vertices.

There's an easy to fix, but important note, which is that the number of edges in can be quadratically large. However, we can check that for each edge of color that we add, we only need to add two edges to . Namely, if and are neighbors of and respectively through an edge of color , then it is enough to add edges and . (If one of or doesn't exist then we just don't add the corresponding edge). We can store these -colored neighbors of each vertex in sets which have total size at most , so we can find in which updates we need to perform, and we perform a constant number of updates per added edge.

Complexity: , or using hash tables.