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
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
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.
for (s[pos += n] = val; pos /= 2;){
// code
}
saw this in a segment tree implementation. How does this work ?
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