As a competitive programmer I never even think about SKIPPING A ROUND.

sure won't

As a tester, I can confirn this round is great.

As a down-voter I down-voted this comment

Best of luck

wish u luck

Hope I become an Expert and you become CM.

Good luck :)

One problem has an easy version and a hard version.

Most of the references are not very hidden, just some quote in the start of the statement...

True AF.

Hope to expert

This round looks so balanced.

My man got the time machine

There is plenty of time to sample all the problems! But maybe not enough time to complete all of them, since some of the dishes are quite big.

Is Marinush your alt?

good luck to you too ☺

damn

I didn't know palindromes would ever make me think that much.

No, only in the announcement)

It just means that each problem has some kind of reference. For example, maybe the problem contains a quote from some particular movie or something. This has no bearing on the actual problem design whatsoever, so you don't have to worry about trying to find these references.

Problem E will have two subtasks: the first has a base score of 2000 and the second has a base score of 750.

Since the first one is scored much higher than the second, my guess is that the second subtask is an extension or improvement to the first subtask, so you would need to be able to complete the first subtask first to be able to solve the second subtask. Solving the first subtask only achieves a base score of 2000, but solving both subtasks is worth a base score of (2000 + 750 = 2750).

I don't think it would be possible to solve the second subtask before the first (since such problems would generally present the Easy version before the Hard version).

I think E1 is easier than D.

HORAYYY!!

I think it's completely unreasonable to expect a random user who decided to problemset to have power just because they are high rated. I won't get into the semantics of what you should have done, but expecting a user to know what to do is like walking up to a customer who's looking at bad standards (as another customer) in a shop and asking them where you can report bad standards. At best, you might be referred to a website, and at worst they won't know.

Really happy right now :>.

Well, I'm going to play OSU! instead of stucking on D. Click the circle !

Hello fellow bad at guessforces! If you're also like me who insists on finding the pattern instead of actually solving the problem, try running brute-force solutions for smaller cases of $$$n$$$ and watch the pattern like so.

may be you are missing something small(try thinking of test cases that will fail your code and handle these cases) there is still some time so keep trying the first 3 problems are quite easy

actually D is not much harder than C. It is just that... I got WA 5 times (I got the idea tho).

Idk if your approach works, but I did a sweepline w.r.t $$$r$$$, and whenever we increase $$$r$$$, we first check the two cases when $$$lcm(i, j, r) = 2r \land i + j > r$$$ which only happens if $$$(i, j) = (\frac{1}{2} k, \frac{2}{3} k),$$$ $$$(\frac{2}{5} k, \frac{2}{3} k)$$$, which we can simply point update on our segment tree, and then, for divisors of $$$r$$$, we first sort them and iterate them from the closest to the furthest from $$$r$$$ and we make the point updates accordingly (we should add 0, 1, 2, ... in this order). Then, we can calculate the total number of bad tuples which we can subtract from the total $$${r-l+1 \choose{3}}$$$

You still need to consider is there a case both the x and x+1 is 1e9.

yes, the second fact:

This can be done using small to large merging + segment tree but I don't think that it will work under given constraints.

Binary search the answer and brute force through all the nodes.

Now $$$f_u$$$ is fixed, so the other node should have $$$f_v \geq something $$$ and we want to find the node having the largest distance to $$$u$$$.

Sort the nodes by $$$f$$$ in increasing order, now the valid nodes form a suffix of the array.

The key observation is we only need to consider the two nodes that form the diameter (easy to prove).

So we just maintain these two nodes and use a $$$O(nlogn)-O(1)$$$ LCA to calculate the distance and the complexity is $$$O(nqlogn)$$$.

It is

yeah, that's what i thought as well. the answer should be min(shortest edge * 2, longest edge) right? but apparently not according to pretest #2...

if you want to 0 some point you also 0 its last occurrence, then you need to zero all the points up to the last occurrence, then all their last occurrences, then all the points up to their last occurrences, etc. until the last occurrence is the point itself and the right is sorted

Binary Search over the final answer (lo = 0, hi = N)

one of the solution can be binary search, If you read the bold character correctly, every number is >0 , and we can make some of them 0. So let's find out how many from the prefix, we want to set 0. Rest is implementation.

168108660

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

I went for a binary search using just a copy of the original vector for each iteration.

I used only vectors, but I couldn't submit in time; so not sure if my solution is correct.

I used ordered set to maintain numbers other than the adjacent pair I am currently looking at. Helps in retrieving the Kth element fast.

Greedily replace the first k-1 minimums (I used vectors of (idx,value) so you can sort it by value, change the first few and then sort by idx). Then you have to find a position for the last value to replace. It'll either be another minimum or a value next to the maximum.

Just binary search on the diameter $$$d$$$, and for each adjacent elements $$$a_i$$$ and $$$a_{i + 1}$$$, count the number of elements $$$a_j$$$ left of $$$a_i$$$ with $$$2a_j < d$$$ and the number of elements $$$a_k$$$ right of $$$a_{i + 1}$$$ with $$$2a_k < d$$$.

Then the total number of modifications needed is the count above + $$$(a_i < d)$$$ + $$$(a_{i + 1} < d)$$$. If this count $$$\leq K$$$, diameter $$$d$$$ is feasible.

what are you guessing? I didnt guess to solve

Same as you. By the way, I am the guy claims to be similar as you in Bilibili, In fact, we both submitted D's answer in the last few minutes coincidently

After being stupid on B and a long struggle on D, it seems that my rating will drop dramatically. :(

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

The diameter isn't necessarily twice the minimum value; it can also be the weight of the single heaviest edge in the graph. consider the following test case:

4 1
3 100 4 5

The diameter is 4 here (not 6). By nuking the 4 (replace with 1e9), the new diameter becomes 6. However, your program outputs 8, probably because it only considered twice the minimum and nuked 3 (I didn't actually try understanding your code, FYI)

Because ignoring the k smallest weights doesn't necessarily optimize the longest edge. For example:

3 1
3 4 5

Here, the longest edge is 4. If you ignore the 3, the longest edge is still 4, so the diamter hasn't increased. The optimal choice would've been to nuke the 4, thus raising the longest edge to 5.

You can count all divisors greater or equal $$$l$$$ for all integers in $$$[l, r]$$$ using something like Eratosthenes sieve. Let that numbers be $$$d_i$$$.

Then for each $$$k$$$ the number of pairs $$$(i, j)$$$ satisfying $$$i|k$$$, $$$j|k$$$ and $$$i < j$$$ is $$${d_k \choose 2}$$$ and now obviously you can add it all up (also with number of triples of form $$$(3x, 4x, 6x), (6x, 10x, 15x)$$$) to get the number of triples that don't work among all ordered triples with different elements from $$$[l, r]$$$.

How did u get the idea of form(3x,4x,6x) and(6x,10x,15x) ?

If we input

1 4 1 3 2 4

the expected output is "1", but your program output is "0".

You mean to copypaste other's solutions or upsolve the problems?