...

well, not everyone...correct solutions have passed.

Well, it do seems that many people wrote the correct solution, but failed because of some details... At least I do.

The issue is that nothing shows the special detail on pretests.>_>

I didn't understand the editorial of problem D. Please someone help me to understand it.

The $$$ 2^k $$$-sized intervals may overlap.

Video-Editorial*

Did exactly this idea..although i was thinking it as a point of change.

My implementation was same as your idea, except instead of blindly sorting them, I choose between which of two events is going to happen first: Car1 reaches next flag, or Car2 reaches its next flag first and then update system (speed,next flag,etc). Code

Let's say $$$n = 4$$$, that means

• for $$$i = 1$$$, $$$p_1 \neq p_2$$$
• for $$$i = 2$$$, $$$p_2 \neq p_3$$$
• for $$$i = 3$$$, $$$p_3 \neq p_4$$$
• for $$$i = 4$$$, $$$p_4 \neq p_1$$$

Statement doesn't explicitly specify that "this should hold for each $$$i$$$", but it's pretty obvious that's what they mean.

I guess, each time one tries to calculate $$$f(x, y)$$$, return the minimal unused number unless the function was calculated before, in this case return the value we returned last times

set $$$f$$$ as a random function

Here is how I solved the problem :-

Say we have the array[12,13,27,34,35] and k=2.

At first we will try to take k distinct elements and make them 0 So, after that the array becomes [0,0,27,34,35]; Now as we can't take any more distinct elements so fill all the next elements by subtracting any previous number in the array say 13.Then the array becomes [0,0,14,21,23]; Now in the second step do the same step however now we can take only k-1 distinct elements as 0 is already in the array.In this way you can do 0(N^2) solution(As constraints are small).You also need to take care of edge cases(k=1).My is a bit messy code(Dont mind that) https://mirror.codeforces.com/contest/1408/submission/94349947

This is in the problem statement:

For each i, $$$a_i≠b_i, a_i≠c_i, b_i≠c_i$$$.

So the testcase is invalid.

Yeah, I did some hard bullshit instead of trivial solution, do you really want to hear it? Why?

For problem C, I did binary search on time variable. For a given time, I calculate the total distance travelled by the person that starts from 0 and I calculate the total distance travelled by person that starts from the end and check whether they cross each other.

Submission: https://mirror.codeforces.com/contest/1408/submission/94324318

For a particular value of t, find the position of both the cars(x1 and x2). If x1 < x2, that means the cars have not yet crossed, so we try for a greater value of t. If x1 > x2, then the cars have already crossed each other. So we try for lesser value of t.

We keep trying like this till the difference between the positions of cars reduces to less than ϵ.

I feel like it is easier to not do binary search but instead find which car reaches a flag first and update the velocities and positions. Keep doing this until the two cars have no flags in between them and then find the remaining time. This is my solution — https://mirror.codeforces.com/contest/1408/submission/94324831 If you still aren't clear send me a private message

No, as you want to remove the cheapest edges first. You want to minimize the total cost hence maximize the ST cost.

Actually, it technically is a typo but for a different reason. The graph G is not necessarily connected, so it should be called a spanning forest, not a tree.

It is extraordinarily difficult.

I don't think B was ugly (though it seems to have weak pretests)
I agree on C though. I felt like crying while implementing it. It's been a while since I felt that way. Pure implementation

Yes, creating a nice problem is difficult, and creating a problem everyone will consider nice is virtually impossible

IMO D, E were quite ugly, F was decent, G was very nice, A, B, C were "yet another easy standard problems", so I don't want to judge their niceness

Questions like B.

Basically, none. Cause even Legendary Grandmasters like Radewoosh or even Errichto failed to solve problem B, whereas some pupils did it.

Looks like you are ternary searching on the x shift. Ternary search doesn't work because the function can have multiple local minima. Sample case 2 gives 7 8 [4] 5 6 7 8 [7] 8 9 10 11 12 13 14 which has 2 minimums and ternary search can converge to any of them not necessarily the global minimum.

Why blame the pretests or the problem setter. Why don't you write a perfect code that it can pass all pretests. I mean why rely on them

Horrible audio quality bro...

Maybe that is why it called div1+2 :D

The editorial for B skips the hardest part: that the answer is at least 1!

To be fair, most people who FST'd B probably knew how to solve it (or some equivalently difficult problem if they misread), but just glossed over a detail.

Lol, it's trivial. Some people have just fell into a trap on a corner case with constant sequence. Stop whining where you shouldn't because I have seen thousands of harder problems in Div2

ok

That's the whole point of CF having pretests/hacks; you have to watch for your own edge cases, and people can get hacks for noticing others fail them.

3) Whoever prepared B didn't make good multitest.

Why are you assuming that they left out such a test on purpose?

1000 free points? You have zero chance of getting 10 people in your room with this mistake.

I'd rather say: "$$$n, m$$$ shouldn't be up to $$$2000$$$", instead of "TL should be higher".

I used binary search by maintaining both their coordinates and lower_bound/upper_bound to find nearest locations. I am not sure if there is any other use.

I hope this helps:- 94316872

Sorry, if this sounds stupid, but could you please describe this a bit please. I completely understand the editorial, like, how does making the virtual verticies for each set, and making a bi-partite graph out of it is helping.

I also get, to why we need to find the Max Spanning Tree.

Yet, I fail to realize, what could have hinted me, to use all of this. Or what prompts us to do create the virtual vertexes for each set, and making the bi-partite graph out of it.

Thanks in advance.

I didn't use FWHT (even though I typed it up in my code LOL) ...

Since, l and r are "long double" in your code, instead of using "l<r" you should prefer using something like this "fabs(r-l)>10e-7"

While using doubles it's better to fix the number of iterations of doing binary search (~100 for accuracy upto 1e-9) instead of while(l<r) as you have done in your solution since there can be a few reasons because of which your while loop will never terminate .

You can learn more about these issues and the proper implementation of binary search on real numbers from the EDU section .

The transition ends up looking something like $$$dp_{\text{merge}(A, B)}[i + j]$$$ += $$$dp_A[i] \cdot dp_B[j]$$$ for every two components $$$A$$$ and $$$B$$$ that we merge, for all $$$1 \le i \le size(A)$$$ and $$$1 \le j \le size(B)$$$. That is, we perform $$$O(size(A) \cdot size(B))$$$ operations, and we want to estimate the sum of this over all merges.

To analyze the total complexity imagine that whenever you merge two components $$$A$$$ and $$$B$$$, you write down the pairs $$$(a, b)$$$ for $$$a \in A$$$ and $$$b \in B$$$. Then the number of pairs you write is equal to the number of operations you perform in a particular merging step. But notice that each pair $$$(u, v)$$$ will be written at most once. This is because once it is written for the first time the vertices $$$u$$$ and $$$v$$$ will lie on the same component on all future steps. There are $$$O(n^2)$$$ possible pairs of vertices, each written at most once, so there's also $$$O(n^2)$$$ total operations.

Edit: Sorry, I used slightly different notation than the editorial. Here $$$dp_C[sz]$$$ denotes the number of ways to split component $$$C$$$ into $$$sz$$$ sets.

The arrays should be non-decreasing.

It does not ignore $$$r$$$, as I choose the pair with the smallest $$$r$$$. I forgot to write that after that on $$$r$$$'s of the remaining tuples we have to solve the problem "guy can be matched with a suffix, find the maximum matching".

About your other question, $$$x$$$ corresponds to the position in the left part. If you can't find a pair for the fixed $$$x$$$, just ignore it.

For all the points who have smaller x-coor difference but larger y-coor difference

Try to avoid using capital letters.

There won't be $$$mn$$$ edges in the graph, the statement guarantees that $$$\sum\limits_{i=1}^ms_i=\sum\limits_{i=1}^m\left|A_i\right|\leqslant2\cdot10^5$$$.

It seems that your solution strikes a lot of similarity with tourist ’s solution Link, which I’m struggling to understand for a couple of days now. Could you please check if that’s true?

Can you give us more details about this ’HMT’ thing? (EDIT: never mind, I guess it means Hall Marriage Theorem)

The best thing I got is that your solutions seems to solve the hitting set problem as the dual for the bin packing problem. Also, maybe it’s related to the matroid intersection approach briefly mentioned in the editorial, which I’m not familiar with.