last AC

What's the optimization?

I couldn't speed up my C2 :(

How do you efficiently calulate minimum operations required where you keep incrementing single element?

And I thought I am only querying 2n times. Lol, what a funny blunder. Guess that's what a year long break from CF does to you.

Anyways, thanks for pointing out my mistake

How to solve Div2 D? What's wrong with my submission 343369699?

How to solve E ?? :(

Easy explanation for F :

Firstly, you can binary search over your answer (you can easily observe monotonicity)

Let's check if $$$X$$$ can be our answer or not.

$$$-$$$$$$ \gt $$$ If there is no index such that $$$a_{i+1}$$$ $$$-$$$ $$$a_i$$$ $$$ \gt $$$ $$$X$$$, then surely $$$X$$$ can be our answer.

$$$-$$$$$$ \gt $$$ If there are more than 1 indexes such that $$$a_{i+1}$$$ $$$-$$$ $$$a_i$$$ $$$ \gt $$$ $$$X$$$, clearly $$$X$$$ can't be our answer.

$$$-$$$$$$ \gt $$$ Else let's say $$$a_{i+1}$$$ $$$-$$$ $$$a_i$$$ $$$ \gt $$$ $$$X$$$ for some $$$i$$$, what should be the complexity of the extra problem?

Let's say the complexity is $$$C$$$, then $$$C \leq a_i + X$$$ and $$$C \geq a_{i+1} - X$$$. Thus, we have a range $$$[$$$$$$a_{i+1} - X$$$, $$$a_i + X$$$ $$$]$$$.

Lastly, we need to check if we could make a problem with complexity in the given range, say $$$[$$$ $$$L$$$ , $$$R$$$ $$$]$$$, for that, you can simply iterate over $$$d$$$ or $$$f$$$ and use set kind of data structure for searching a possible answer.

Oh, I thought this will TLE, but min(n,m) can be at most sqrt(1e5), which idk why, I missed :(

How to solve G?

Basic idea is precomputing answers for all d <= $$$\sqrt{N}$$$, which can be done by prefix sums in O(N*$$$\sqrt{N}$$$). For d > $$$\sqrt{N}$$$, simply iterate and get your answer.

Why am I sweating in winters

Is it 2^(number of pairs u-v where dist(u,v) < S) ??? I couldn't think of a concrete solution

I've never seen a predictor working for a contest with a hacking phase

I literally picked up my chess board and played an entire end game with no pawns to study problem A

How to handle both a[i] and b[i] even case in C ??

System testing is going on. All submissions are being rejudged based on successful hacks testcases. But as I can see, your solution for problem C has failed the system test and D one is waiting to be judged.

Why it was a great Div3 round :

• Problem A & B : Naah, they don't teach a lot

• Problem C : Teaches use of custom comparators

• Problem D : Teaches to handle precision in floating point numbers and some geometry

• Problem E : You've to be prepared for future "Math-forces" rounds to grow as a competitive programmer.

Problem F : Simple idea but teaches how to interact with the judge

Problem G : Shows the power of dijkstra and also bitmasks with it

Overall, great round covering so many topics that are pretty relevant to div 3. Congratulations to the authors.

Nothing is obvious / standard in a div3/div4 round. People here are learning these topics. How could you say bit-mask + dijkstra problem is an obvious one for div 3? It was indeed a great problem

That's why we're using dijkstra, do you ever comeback to the same node in dijkstra bfs ?? Use that analogy here, take days as edge weights

I made your solution AC, 212462179

I did the priority distribution right, but couldn't come up with this idea that minimum operations is just number of zeroes that should've been 1. Thanks for your solution btw :)

Let biwise AND of all the elements equal to k,

Case 1: k == 0 : Try to create maximum number of partitions such that AND of all partitions = 0.

Case 2: if k > 0 , it's always optimal to create only one group, i.e. the whole array. Reason :--> It's easy to prove Bitwise AND of any partition is >= k , hence more the partitions, more will they contribute to sum, so make just 1 partiotion with AND = k

How to solve D ?

You've to be sure about monotonicity of your search space whenever you're going for binary search, which in this case is not monotonic.

That's just sum of all ratings

I've tried, scroll above

I solved this question and I still don't understand the intuition behind it.

Here are some less complex observations for problem D :

1. Let's make a prefix array first. Now, our answer is definitely from one of the values in the prefix array.(or 0 if all prefix values are -ve). Why? cuzz we won't let our rating fall from a point where we reached , so out k must be a value we reached.

2. We can calculate answer for each prefix value (though it's easy to prove that optimal value is always a local maximum).

3. Begin traversing the prefix array now how to calculate the answer from this value of k = prefix[i] ? ---> Answer is : [ Σa_i + (maximum distance you go below from k in you prefix array) ]

How to prove this ? ----> You can think of it as : When you add something -ve that takes your prefix value below the threshold k, you actually add some EXTRA to your answer to keep it fixed at value k. Hence , whenever next time when again prefix value goes below k , again add value to EXTRA to keep it at k. Finally you will notice you added total EXTRA = max(0 , k — min(pref[i])).

--> min(pref[i]) is minimum prefix value that we reached.

What's your logic to add edge u->v only if u < v ??

And to check if a node is a leaf , you can just check if adj[node].size() == 1 && node != 1

Tree is undirected, you should add adj[b].push_back(a) too in your solution. Since its not certain that node with a smaller value will lie above the node with higher value.

I'm not able to calculate probability that n exceeds M + 62500 ... How to do it ??

201512259 Can someone please tell why it failed on Problem A ??

Can you please explain why bfs from leafs doesn't work ?? Any test-case ???

int overflow where you used --->>> (r-l+1)*k <<<----

endl in c++ flushes the i/o stream by default so no need to use cout<<flush after using endl Though I didn't check your code thoroughly (some other bug maybe there)

That would've been one of the best geometry problems.

You managed to dodge the wrath of test case 4 on problem D. Congo

I was trying to solve it using dp , but unable to implement. I appreciate the code , but I'm unable to understand the dp state. Can you elaborate it a bit ??

Can you please explain the approach used for revolution problem ??? Thank you

Can you please explain the approach used for revolution problem ??? Thanks

C destroyed me :( How to get total number of possible sets ????? ^_^

A single dispenser can never serve >1 cakes at a time without spilling (Given that w >= h)

Yup , I thought the same , sadly couldn't remove bugs in my code. This approach should work.

Array is 1 indexed every where , maybe you're misreading the sample tests. And also ,there is no port at 0

You only choose subsets with length == k. And complexity will decrease enormously.

@Codeforces , atleast give update about rating changes