Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### user311's blog

By user311, history, 2 months ago, An undirected graph is called a ring if all its nodes have degree two. For a ring of size n, find the number of ways to color it using three colors Red, Green or Blue such that no two adjacent nodes have the same color.

Constraint — n < 2e5

By user311, history, 2 months ago, We are given a sequence A = {a1, a2, ... , an} which is index wise sum of two sequences B = {b1, b2, ... , bn} and C = {c1, c2, ... ,cn}.

i.e. a1 = b1 + c1, a2 = b2 + c2 , ... , an = bn + cn

B is non decreasing and C is non increasing.

Find the minimum possible value of abs(b1) + abs(b2) + ... + abs(bn) + abs(c1) + abs(c2) + ... + abs(cn).

Constraint — array size <= 2e5, -1e8 < a[i] < 1e8.

By user311, history, 2 months ago, for (s[pos += n] = val; pos /= 2;){
// code
}


saw this in a segment tree implementation. How does this work ?

By user311, history, 4 months ago, I didn't notice that as per the question statement, we can only switch adjacent characters to reach the original string.

If this wasn't the case and we could switch any characters of the string, how would you solve it.

I wrote a greedy solution: complete as many possible cycles of A -> N -> T -> O -> A until we exhaust the least frequent character. Followed by smaller and smaller cycles.

by completing cycles A -> N -> O -> A, I mean swap 'A' and 'N', swap 'N' and 'O' and so on.

code

Code

By user311, history, 8 months ago, 