In a palindrome, the first and last characters are equal, the second and second last characters are equal, ...

182556248

182551321

182551219

• Amazing problem
• Good problem
• Bad problem
• Didn't solve :sadness:

Think small, then big!

182734541

182551371

182551107

Video Editorial

• Amazing problem
• Good problem
• Bad problem
• Didn't solve :sadness:

Consider the cycles in the permutation. What cycles can there be?

183029471

Soon

182603684

Video Editorial

• Amazing problem
• Good problem
• Bad problem
• Didn't solve :sadness:

Try separating the even and odd cases.

Soon

Soon

182550901

Video Editorial

• Amazing problem
• Good problem
• Bad problem
• Didn't solve :sadness:

What do two clocks with assigned values on the same column tell us about their respective rows?

182550042

Soon

182550690

• Amazing problem
• Good problem
• Bad problem
• Didn't solve :sadness:

If we are modifying a point already in an interval, how can we grow/split the interval to maintain balance?

182550752

182550559

• Amazing problem
• Good problem
• Bad problem
• Didn't solve :sadness:

Provided that there exists a solution for our configuration. We can give each node from $$$1$$$ to $$$n$$$ a weight of $$$0$$$, and each node from $$$n + 1$$$ to $$$2n$$$ a weight of $$$1$$$, as we only care about the number of imposters in our configuration. Now, for each pair of symmetric components, take the one that contains the maximum number of players being imposters.

My AC submission

163478635

169912969

169902868

169902269

In today's Codeforces round, I realised a minute before the contest that I had forgotten to register. "No problem", I thought to myself, "extra registration open in a few minutes". To try to minimise penalty losses due to my delayed submissions, I decided to start with problem C. Unfortunately, it took me longer to implement than I expected, and by the time I was ready to submit, the extra registration period had ended. Now I am left with nothing to do for the next hour and twenty minutes :(

The next multiple of $$$100$$$ after $$$X$$$ is $$$X + 100 - (X \mod{100})$$$, so our answer is $$$100 - (X \mod{100})$$$.

Time complexity: $$$O(1)$$$ My solution

Simply check if the condition given in the statement is fulfilled.

Time complexity: $$$O(|S|)$$$ My solution

We can simulate the process directly. $$$g_1(x)$$$ can be calculated by sorting the digits in $$$x$$$ in ascending order, while $$$g_2(x)$$$ can be calculated by sorting the digits in $$$x$$$ in descending order.

Time complexity: $$$O(K \times log_{10}(N))$$$ My solution

I suggest using Python for this task. We can use binary search to find the largest integer $$$n \ge d+1$$$ such that $$$X_n \le M$$$. There exists an edge case for $$$X$$$ of length $$$1$$$, as there can only be $$$0$$$ or $$$1$$$ unique values of $$$X_n$$$ in base $$$10$$$.

Time complexity: $$$O(log_2(10^{18})*|X|)$$$ My solution

We can solve this problem using a modified version of Dijkstra's algorithm. Since we can only take a train $$$i$$$ at multiples of $$$K_i$$$, before taking a train, we must also add the waiting time for the next train to the "weight" of an edge. The next occurrence of train $$$i$$$ given current time $$$t$$$ is $$$K_i \lfloor \frac{t+K_i-1}{K_i} \rfloor$$$.

Time complexity: $$$O(MlogN)$$$ My solution

We can solve this problem with dynamic programming. Let $$$dp_{i,j,k}$$$ be the maximum possible initial potion magic power, where $$$i$$$ is the planned final number of materials used, $$$j$$$ is the number of materials used so far, and $$$k$$$ is the potion power modulo $$$i$$$. Our transitions are $$$dp_{i,j,k} = dp_{i,j-1,k-a_y \mod{i})}$$$ for each index $$$y$$$ in the given array $$$a$$$. Our answer is the minimum of $$$X - dp_{i,i,X \mod{i}}$$$ for all $$$1 \le i \le n$$$.

Time complexity: $$$O(n^4)$$$ My solution

Simply simulate the game and print out the winner.

Time complexity: $$$O(A+B)$$$ My solution

For each spell $$$i$$$, check if $$$X_i < S$$$ and $$$Y_i > D$$$. If such spell $$$i$$$ is found, the answer is "Yes", otherwise, if after all spells have been processed and no such spell has been found, the answer is "No".

Time complexity: $$$O(N)$$$ My solution

We can approach this problem using bitmasks. For each $$$i$$$ from $$$0$$$ to $$$2^K-1$$$, if bit $$$j$$$ is "on" (i.e. $$$i$$$ AND $$$2^j = 2^j$$$), we give the $$$j$$$-th dish to ball to $$$C_j$$$, otherwise we give it to $$$D_j$$$. We calculate the maximum number of satisfied conditions across all $$$i$$$, and that is our answer.

Time complexity: $$$O(2^K * (M + K))$$$ My solution

The sum $$$S$$$ of an arithmetic sequence with first term $$$a$$$, $$$n$$$ terms, and common difference $$$1$$$ can be found with the formula $$$S = \frac{n}{2}[2a + n - 1]$$$. Rearranging this and multiplying across by $$$2$$$, we get $$$2S = n(n+2a-1)$$$, therefore $$$n$$$ must be a factor of $$$2S$$$, which is $$$2N$$$ in this problem. Rearranging further, we get $$$a = \frac{\frac{2N}{i}-i+1}{2}$$$. Now, we can iterate over all the factors $$$i$$$ of $$$2N$$$, and we need to check if $$$\frac{2N}{i}-i+1$$$ is divisible by $$$2$$$.

Time complexity: $$$O(\sqrt{N})$$$ My solution

We can represent the gems which can be placed adjacent to each other using a graph. Now, for each $$$C_i$$$, do a breadth-first search of the graph and calculate distances to all other gems. We can now model the solution as one with dynamic programming with bitmasks. Let $$$dp_{i,j}$$$ be our answer if we use all the gems included in the mask of $$$i$$$, ending with gem number $$$j$$$.

Time complexity: $$$O(K(N + M) + 2^K * K^2)$$$ My solution

We can calculate the number of inversions in the original array in a number of ways, such as with a Fenwick tree or with merge sort. Now, notice that each of the resulting sequences essentially remove the first element of the previous sequence and insert it at the end of it. This removes $$$a_i$$$ inversions and adds $$$N-a_i-1$$$, changing the total number of inversions in the new sequence by $$$N - 1 - 2a_i$$$ for each $$$i$$$ from $$$0$$$ to $$$N-2$$$.

Time complexity: $$$O(NlogN$$$ for calculating inversions $$$)$$$ My solution

Calculate the sum of the digits of both integers, and print out the maximum.

Time complexity: $$$O(1)$$$ My solution

As the slope $$$m$$$ of a line between two points $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ can be found by the equation $$$m = \frac{y_2-y_1}{x_2-x_1}$$$, we simply need to compute the value of $$$m$$$ for each pair $$$(i,j)$$$, while adding $$$1$$$ to our count every time $$$-1 \le m \le 1$$$.

Time complexity: $$$O(N^2)$$$ My solution

We observe that a string $$$T$$$ is unsatisfiable if there exists $$$S_i$$$ such that $$$S_i = T$$$ and $$$S_j$$$ such that "!" $$$+ S_j = T$$$. We can maintain a data structure, such as a map or a set, and each time we add a new string to our set, we check if its pair string (with or without a leading "!") has already been added. If it has, we have found our answer, and we can simply print it (removing a leading "!" if necessary), and exit.

If, after processing all the input strings, no unsatisfiable string has been found, we print "satisfiable".

Time complexity: $$$O(|S|log(|S|))$$$ My solution

Notice that every time Takahashi makes a speech in some town $$$i$$$, his vote count, relative to Aoki's vote count, increases by $$$2A_i + B_i$$$, as he gains $$$A_i + B_i$$$ voters, while Aoki loses $$$A_i$$$ voters. We can sort the towns in decreasing order of $$$2A_i + B_i$$$, and greedily take the town which adds most relative votes until Takahashi's relative votes are greater than Aoki's.

Time complexity: $$$O(NlogN)$$$ My solution

As all queries involve certain edges, once we perform a DFS traversal of the tree, rooted at some arbitrary vertex, each query will involve a parent and child vertex in some order. If we are asked to increase by $$$x_i$$$ the vertexes reachable from the child vertex without visiting the parent vertex, we can simply increase the value of all vertexes in the child vertex's subtree by $$$x_i$$$. On the other hand, if we are asked to increase by $$$x_i$$$ all the vertexes reachable from the parent vertex without visiting the child vertex, we need to increase by $$$x_i$$$ all vertexes which are not in the subtree of the child vertex. We can do this by maintaining a variable which is to be added to all vertexes, and increasing it by $$$x_i$$$, and decreasing the value of all the vertexes in the child vertex's subtree by $$$x_i$$$, effectively undoing the global change for those vertexes. We can perform these changes by doing a total of two DFS traversals.

Time complexity: $$$O(N)$$$ My solution

This is a classical dynamic programming with bitmasks problem. We can calculate the minimum amount of components possible for some mask $$$m$$$, and iterate over its submasks to reduce this number further. More to be added if there are requests for such.

Time complexity: $$$O(3^N)$$$ My solution

Since we need exactly one of each of $$$A_1$$$, $$$A_2$$$, $$$A_3$$$ and $$$A_4$$$, we are limited by the minimum number we have of one of these. Therefore, we need to print the minimum element of these four.

My solution

If Takahashi's phone is to run out of battery during his walks between two of the locations, it will be at an even lesser battery at the end of that walk. So, we simply need to check that upon entering one of the $$$M$$$ cafes, or returning to his house, that his phone's battery is greater than 0, and increase his battery by $$$y_i-x_i$$$ for each of the cafes, while making sure the phone's battery is capped at $$$N$$$.

My solution

We can maintain a $$$dp_{i,j}$$$ where $$$i$$$ represents the number of cuts made so far, and $$$j$$$ represents the length of the iron bar accounted for so far. The transitions are $$$dp_{i,j} = \sum_{k=0}^{j-1} dp_{i-1,k}$$$, and our answer is $$$dp_{12,n}$$$.

My solution

See here

saarang123's implementation (warning: Python used)

First, sort $$$A$$$, so that we have all the blue squares in increasing order. Now, note that the number of white squares between two blue squares is $$$A_{i+1}-A{i} - 1$$$. Since we don't need to paint any squares between two blue squares if they are consecutive, as there are none, our value of $$$k$$$ will be the minimum across all of the number of white squares between all blue squares that are non-zero, including the number of consecutive non-zero white squares before the first blue square and after the last blue square. Now that we have our value of $$$k$$$, we simply need to colour each of these consecutive blocks of white squares. If there are $$$x_i$$$ consecutive white squares, we can colour them all red in $$$\lceil \frac{x_i}{k} \rceil = \lfloor \frac{x_i+k-1}{k} \rfloor$$$

My solution

Let $$$dp_{i,j}$$$ be the minimum number of operations to convert the first $$$i$$$ elements of $$$A$$$ into the first $$$j$$$ elements of $$$B$$$. Clearly, we can convert the first $$$i$$$ elements of $$$A$$$ into the first $$$j$$$ elements of $$$B$$$ by simply deleting all $$$i+j$$$ elements. Now, we can recalculate our $$$dp$$$, in order of increasing $$${i+j}$$$, as follows:

• If $$$A_i=B_j$$$: $$$dp_{i,j} = min(i+j, dp_{i-1,j-1}, dp_{i-1,j}+1, dp_{i,j-1}+1)$$$

• Otherwise: $$$dp_{i,j} = min(i+j, dp_{i-1,j-1}+1, dp_{i-1,j}+1, dp_{i,j-1}+1)$$$

This is because we can reduce the problem down, respectively, by:

1. deleting all $$$i+j$$$ elements
2. leaving the $$$i-th$$$ and $$$j-th$$$ elements as they are and taking any penalties for having non-equal elements
3. deleting the previous element from $$$A$$$
4. deleting the previous element from $$$B$$$

Our answer is $$$dp_{n,m}$$$.

My solution

We can use a data structure, such as a Fenwick tree, or segment tree, to process these queries.

My solution (using a Fenwick tree)