Lets Hurt the Problems(➢ᴗ➢)

И теперь мне не хватает 9...

Great perfomance in this round from you!

Same :)

carrot

C is doable with just 1 sort + array iteration.

Pretty cool, thanks for sharing! An alternative solution that I implemented uses binary search on prefix sums to find the rightmost drinker that can be satisfied and uses the $$$+1$$$ on left and $$$-1$$$ on right boundary trick. Solution

LOL No just basic binary search

If u have code it up C problem using Segment Tree, then Can u please share the link of your submission

I think the idea is each group needs to be colored either BRB or RBR inorder to extract the maximum 2 edges from each group and we cannot extract more than that from each group. Then we need exactly half of the group to have BRB and half to have RBR inorder to have n/2 vertices of each colors . For each group we can calculate the number of ways to color BRB so that we get max 2 edges and same for RBR

I could not figure out how to implement the part where we select exactly n/2 groups to have BRB and n/2 to have RBR in the given constraints

For each triangle find # of ways to choose two edges to get the max value, multiply those numbers and finally multiply (n / 3 choose n / 6).

Some observations:

• It's never a good idea to color all three vertices in a triangle with the same color, since you would always get a higher total weight by coloring one of them differently from the others. Therefore, each triangle should be either 2 blue, 1 red or 2 red, 1 blue.
• Since exactly half of the vertices must be blue and exactly half of the vertices must be red, this means that exactly half of them will 2-blue-1-red (I call them blue-heavy) and exactly half of them will be 2-red-1-blue (I call them red-heavy).
• With $$$n/3$$$ triangles, there are exactly $$$n/3 \choose n/6$$$ ways to assign blue- and red-heaviness.
• Now, given a triangle, we know 2 should be of the same color, but which two? Well, the edge between these two is the only edge from this triangle that will NOT contribute to the weight. So we should choose the edge with minimum weight.
• However, there might be 1, 2 or 3 edges with minimum weight in the same triangle. This number is also the number of ways to color the triangle after you already decided if it's blue-heavy or red-heavy.

Basically, if $$$f(\Delta)$$$ is equal to the number of copies of the minimum-weight edge in the triangle $$$\Delta$$$, then the required answer is $$${n/3 \choose n/6} \prod f(\Delta_i)$$$.

My submission: 193883975. I first computed $$${n/3 \choose n/6}$$$ (by accumulating a factorial vector) and then checked each triangle one by one, sorting the three edges and counting how many copies of the minimum edge there is.

solved using only binary search and range updation where we perform update queries first and in the end calculate the ans

I have solved it using Binary search + dif array. The basic idea behind was that I calculated for every tea how many testers will be able to test the tea, for this I just calculated the prefix array of tea, each tester can have at max and then simply iterated the array by finding upper bound for each element in that prefix array.

This is my submission 193883206

me

The problem would become equivalent to this:

we have an array in each operation you can decrease an element by one. Whats the minimum number of operations needed to make the array increasing/decreasing the array?

Am I right?

How do you solve this?

Can you give some hints to solve E ?

I miss D by 1 min :(. Due to PC for case 2 in which two values of edges are the same.

How did you plan to use a segment tree with constraints <= 1e9?

Problem C and 923B - Producing Snow are same.

Most of div2C problems do not require segment trees.

I used segment tree and passed, although it's really dirty compared with others' solutions. You may check my code here: 193914285

by idea no, by implementation yes

I thought D looked easier than C, but I only had 8 minutes to read it :(

About 2300-2500 I think.

Great work bro try to be regular Upload editorial for all contents

you're supposed to mention the link to your submission as well so that people could see it.

Yes. $$$\frac{X}{Y} \mod M \ne \frac{X \mod M}{Y \mod M}$$$.

E.g.: $$$X = M + 1$$$, $$$Y = 2$$$;

$$$\frac{X}{Y} \mod M = \frac{M + 1}{2}$$$, but $$$\frac{X \mod M}{Y \mod M} = \frac{1}{2} = 0$$$

You should use modular inverse to calculate answer

$$$n$$$ inserts on a multiset and at most $$$n$$$ deletions : $$$nlog(n)$$$.

I also implemented with same idea.

Suppose our multiset S contain let say m elements and we are processing index i , so we can consider all the elements which are smaller than b[i] and erase them from the set and keep the elements greater than it. Deleting the smaller elements wont allow them to participate in further iterations and thus causing atmost n deletions.

Now all the elements greater than it are decremented in the same amount delta, so we don't need to perform decrement operation in that range, what we can do is keeping a variable delta for tracking the decrements

Now when we process the next index i + 1, we are essentially comparing an element x in set by considering x — delta with b[i+1].

Smaller elements such that x <= b[i+1] + delta are removed from the set as they eventually become 0 and positive elements remain with the effective delta being delta = delta + b[i].

TC: nlog(n)

The issue is that it must be possible for $$$k$$$ to be in the highest number of intervals, with no ties allowed. For example, if there is only one interval, with range $$$[k - 1, k + 1]$$$, then regardless of whether you keep or remove it, the number of intervals with $$$k$$$ will always be equal to the number of intervals with $$$k - 1$$$ and also the number of intervals with $$$k + 1$$$.

What you need to do is find some interval that includes $$$k$$$ but not $$$k - 1$$$ and also find some interval that includes $$$k$$$ but not $$$k + 1$$$. If you can find both (note that the interval $$$[k,k]$$$ already satisfies both), then the answer is YES. Otherwise, the answer is NO.

Google competitions -> https://codingcompetitions.withgoogle.com

ICPC depends on regions, but it usually starts in Autumn, as far as I know.

learn english

А нужно ли? Можно прочитать авторский разбор, и вроде бы на edu раунды всегда делают разбор на русском языке

O(n^2) is not fast enough. With n being 2*10^5 n^2 is 4*10^10 which is too much. You need an O(nlogn) solution here, you can read about it in other comments.

Your time complexity is 4 * (10 ^ 10) in the worst possible scenario. As far as i know C++ can process no more than 10 ^ 9 operations in 1 sec(in the best scenario).

Great work bro

Care to explain how did you get your hands on someone else's code?

Lol you should be really ashamed ! you are the worst cheater in history !

The trick you were trying to pull off by changing the contents of your comment, all the revisions are publicly available if you don't know. Just accept that you have cheated and come clean.

1500 i guess

I have discord sever for that.

Common discord group- https://discord.gg/P5TEZB4zAr

(Beginners) The new coders- https://discord.gg/4DH3PWUX3t

(Intermediate) Pro coders- https://discord.gg/H8TeFjvq6z

(The Pro coders channel is most active)

No, it's rated only for div2.

1600 or 1700.

binary search the answer, then do the tree dp, let dp[x] be the minimum score of a subtree of node x you can get, where the score of a subtree rooted at x is:

if dp[x]<=0 that means that node x isnt yet painted black and that we have a white path starting at x in the subtree of x which is of length -1*dp[x]

if dp[x]>0 that means that node x is painted black and that it contains currently a chip and that the chip needs dp[x] more steps which will go upwards from x

make vectors global as this 193938114

Your code complexity is $$$O(T * MAXN)$$$. $$$MAXN$$$ in this case is $$${10}^5$$$. If T is large (>= $$${10}^4$$$) you code will TLE

It usually takes a super long time to update your rating in EDU/div3/div4 rounds.

Take a look at Ticket 16736 from CF Stress for a counter example.

Have you ever read the Terms of agreement before you register yourself

Here it is read again

The registration confirms that you:

• have read the contest rules by the links http://mirror.codeforces.com/blog/entry/456 and http://mirror.codeforces.com/blog/entry/4088
• will not violate the rules described on http://mirror.codeforces.com/blog/entry/456 and/or http://mirror.codeforces.com/blog/entry/4088
• will not communicate with other participants, share ideas of solutions and hacks
• will not use third-party code, except stated in http://mirror.codeforces.com/blog/entry/8790
• will not attempt to deliberately destabilize the testing process and try to hack the contest system in any form
• will not use multiple accounts and will take part in the contest using your personal and the single account.