That's why CF comment section and its community sucks

Simply,it's not for Russian 5th to 8th grade student anymore.

Random Guy: * copies https://codeforces.me/blog/entry/80723?#comment-670498 *

CF-Community: So, you have chosen death?!

C: I wasn't able to figure out the solution. Help

In problem C you should make string like this 11111 eg make all digits same or 202020 make string of even length where used only two distinct digits and no adjacent digits same

while doing paper work you observe that the only way to minimize the number of deletion and to make string good ..we have only three cases case 1->all character are same..(for that you just check the maximum frequency element and for number of deletion you just subtract with the length i.e number_of_deletion_required_to_make_all_character_string_equal =string.length()- max_frequency_element) case 2-> see the alternative character.. for that you have to find the a pair in [0 to 9] for which you make maximum length of of alternative character string .. observe that length greater than or equal to (>=)4 is beneficial for ous ..i simply mean this--> if (max_alt_len >= 4) { if (max_alt_len % 2 == 1) { max_alt_len = max_alt_len — 1; } alternate_deltion_requi = str.length() — max_alt_len; } case 3-> you have only 2 characters i.e number of deletion = string.length()-2; and then you have to take the minimum of all cases . please see the code for better understanding :) click here to see the implementation

Can you share your approach?

I still don't understand how can they do the same mistake for 3 contests in quick succession. Really disappointed.

Agree.(but someone working hard on B didn't even read the question of E)

(y — x) * (d — 1) = 0 (mod w)

Just reduce it to the no of i, j such that j > i and j — i is divisible by w / gcd(d — 1, w). You get a simple expression for the ans as Ans = sum_(k = 0 to (min(d, m)) — 1) floor(k / w') where w' = w / __gcd(d — 1, w) which can be obtained in O(1) by floor constraining.

if d == 0 -> answer = 0 else rearrange the expression to obtain (y-x)(d-1) == 0 mod w meaning the w divides this product, if g = gcd(w, d-1), then w/g must divide y-x also x < y < min(d, m), let L = min(d, m) and k = w/g and t = floor(L/k) then the answer is sum L — k*i where i*k <= L which is equal to L*t — k*t*(t+1)/2

x + d*y = y + d*x mod w implies (d-1)*(y-x) = 0 mod w, let g = gcd(d-1, w), then y = x mod(g/w), y > x, x <= min(m, d), y <= min(m, d) counting this is a standard problem.....

Let each interval be a vertex in a bipartite graph, where an edge indicates that two intervals intersect. We want to find the size of a maximum independent set in this graph. By Kőnig's theorem, this is equal to $$$n$$$ minus the size of a maximum matching in this graph. So, the problem reduces to finding a maximum matching in which we pair up red and blue intervals which intersect.

The condition for two intervals $$$x$$$ and $$$y$$$ intersecting is that $$$L_x\leq R_y$$$ and $$$L_y\leq R_x$$$. Now, let's assume that in this condition, $$$x$$$ is always blue and $$$y$$$ is always red. If we preprocess the input by replacing each blue interval $$$[L, R]\to[L, -R]$$$ and each red interval $$$[L, R]\to[R, -L]$$$, then the condition becomes $$$L_x\leq L_y$$$ and $$$R_x\leq R_y$$$, which is much cleaner.

From now on, we can think of each interval $$$[L, R]$$$ as being a point in the plane at coordinates $$$(L, R)$$$. To construct the maximum matching, we scan the points in order of increasing $$$L$$$. When we encounter a blue point, we add it to a multiset to be picked up later. When we encounter a red point, we can match it with any blue point from the multiset whose $$$R$$$ value is $$$\leq$$$ than that of the red point. Blue points with smaller $$$R$$$ values are "better", since they can be picked up by more red points. So, it makes sense to greedily get the "worst" point out of the way by choosing the valid blue point with largest possible $$$R$$$ value.

Short code: 88388914

I have an immature idea of dp solution for problem F. First do coord compression. define dp[len][lastcolor] as the answer of segmets until length len and last color is lastcolor.

when we go to a new length with color lastcolor, we want to know at which point prevlen we choose to start the last color range that we can get the max answer. so we need to update an array b[prevlen]. when a new seg [l, len] with color lastcolor added, b[1, l] will all plus one, while b[l+1, len] will not change. and dp[len][lastcolor] = max(b[]) to update b[] efficiently, Segment tree with lazy propagation will be used.

when both characters a and b are same you don't need to check cnt%2 == 1(example: 000)

a == b -> not minus if (cnt%2==1)

If all characters of the answer string are same then length can be odd.

check for a==b then length can be odd

You don't need to decrement cnt if cnt%2==1, when it comes to a==b

the final string should be of the form AAAAAAAA....AA or ABABAB......AB. Iterate over all possible A and B

Use the observation that in order to make a good string, either it has all the same characters such as "111111", or it has repeating pairs such as "121212". The minimum answer must be one of these two cases. There are 10 * 10 combinations that you need to check, each check takes O(N) time.

The longest subsequence should be either xxxxxx or xyxyxy(even length). We can simply brute force for every 2 digits from 0 to 9 like 010101... or 020202 and find the length of the longest pattern present in the given string. And finally, take maximum of all of them. Complexity O(81*n).

how to do it with dp?

There are only two form of the final string. aaaaa...(the length doesn't need to be even) or ababab...(the length must be even)

Why? I thought it was fine for an educational round. Probably not too interesting for a regular round though.

It's for Russian 5th to 8th grade students , they think it's great , but not us.

Sorry, I realised that it would be better to give it as a weighted graph when the whole testset and all solutions were already prepared :(

B took 1h, C took 7m for me :(

Notice that the number of total moves left can be directly derived from the current index and the number of moves to the left. Just don't include the number of total moves left in the dp memo.

moves = idx + 2 * lmoves

use map instead of 3d dp array it will be easy

Here, in this code how do you make sure that you don't go left twice or more times in a row?

(the answer is:not to use DP)

see this comment

how did you come up with this, I did brute force and it worked

LCM(L,2*L) = 2*L and is the smallest LCM you can find in the interval

try 121231212

is he a cm?