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, In English

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

Read more »

 
 
 
 
  • Vote: I like it
  • -10
  • Vote: I do not like it

By user311, history, 2 months ago, In English

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.

Read more »

 
 
 
 
  • Vote: I like it
  • -20
  • Vote: I do not like it

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

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

Read more »

 
 
 
 
  • Vote: I like it
  • -21
  • Vote: I do not like it

By user311, history, 4 months ago, In English

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

Link to Problem

Read more »

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

By user311, history, 8 months ago, In English

I sincerely need help, I've tried everything to not get a TLE.

problem

my solution

Thanks in advance

Read more »

 
 
 
 
  • Vote: I like it
  • -18
  • Vote: I do not like it