"Now we just have to count how many pairs $$$(x, y)$$$ there are such that $$$ax + by \lt ab - a - b$$$"

I have just read your solution to this line. But the problem is count how many numbers can be represented, not how many pairs $$$(x,y)$$$ (As $$$2$$$ different pairs can result in the same number: $$$1\times 1 + 2\times 2 = 1\times 3 + 2\times 1=5$$$). Sorry if I missed something.

PS: You can place your math equations between $$$2$$$ Dollar sign $.

Auto comment: topic has been updated by Libraion (previous revision, new revision, compare).

Thanks <3

Thanks so much!

https://ideone.com/6O6oxw

This is the $$$O(N^2)$$$ version. The problem is to find the total weight of Minimum Spanning Tree.

Could you elaborate a little bit more? Like with a real example. Thanks

Thanks <3

Interesting! Thanks for your reply.

Thanks for your reply.

Thanks for your reply. At least we would know to try to put inline before function with many recursions when getting RTE.

Added #pragma GCC optimization ("O3"): 123037331, but still RTE. Sorry if I missed something.

That's an idea to consider. However, as I'm fed up with this problem, you can try to implement your approach and check the above 3 big testcases google drive link. (If you are successful, please show me your code <3. Thanks)

Thanks so much. Your approach is no neat. Unfortunately, the three big test case didn't match your output (the remaining 17/20 works). I don't know why, maybe the testcase was poorly generated.

You can check the three testcase here: https://drive.google.com/drive/u/0/folders/1WdIhtuiy5hML6x2tFmOe6iBQ6KdV4j3I

It seems to me that your solution won't be able to pass the below case. Sorry if I missed something.

Thanks for everybody. Using your ideas and suggestions, I have come up with a weird solution. (It outputs correct for 17/20 test cases — the 3 remaining are huge ones and I don't know what to do — maybe just assume that the test output is wrong by float/double/long double reasons).

At first I think about sweepline 2 directions and calculate like Veladus ideas. But I stucked at the polygon which is like the picture below. As we each time we get to an event there can be O(n) different trapezoids (and it seems that there is hardly a way to manage every trapezoid and sum up all of them at once).

So I changed the idea a bit. First I took the convex hull of the polygon. And calculate with the above idea. But it will be redundant of course. So I just iterate through the polygon again and find which inner-polygon is redundant and recursively solve it again then minus the redundant part. It is a lot of implementation, though.

I thought it would be slow, but in fact it was fast but it was WA.

I'm looking for a way to generate testcase for this problem. But the restrictions of polygon which is not self-intersecting and the input have to be ccw/cw order, makes it really hard. Not only that I don't know how to have correct output for that generated testcases :'(.

I'd appreciate if anyone suggest me a way to generate test and help debug my code.

I don't know if it is online or not. I have about 20 local tests for this problem.

Sorry but may I have a few absurd question?

1. When do we add/delete/replace lines in our container?

2. How that there is 2 same lines in our container [(-2, 2)->(0,0); (-2, 2)->(0,0)] ?

3. $$$\Delta y$$$ denote the left most distance... What do you mean by left most distance? (A real example would be great.)

4. $$$\Delta y_1$$$ is the distance per step. I don't understand. Could you give an example?.

5. Is $$$l$$$ the difference of x coordinate between the current event and the last one?

Thanks for answering! Could you elaborate your idea with the above test case please? Appreciate!

Thanks so much ❤❤

Auto comment: topic has been updated by Libraion (previous revision, new revision, compare).

So what happen when there is > 2 odd degree vertex that you cannot fit every vertices into 1 path. Then how many paths? And what if after finishing 1 path you make the graph unconnected ... etc.

Sorry I don't understand what you mean. Could you elaborate it a bit?

Thanks <3

You can see my proof here

My proof goes like this:

Let $$$H, X, P, Q, M, A, R$$$ is declared the same as in the editorial above.

We prove (from the editorial), when we increase $$$H$$$ by $$$1$$$:

• $$$P \ge Q$$$ : the cost will change $$$AN−M(N−X)$$$.

• $$$P \le Q$$$ : the cost will change $$$-RN+MX$$$. $$$($$$Because $$$R(Q' - P') + MP' = R(Q - P) + MP - RN + MX$$$).

Let $$$F(H)$$$ is the cost when ADD / REMOVE / MOVE so that the resulting height for all the pillars is $$$H$$$.

Let $$$H_0$$$ is the minimum $$$H$$$ such that : $$$P \ge Q$$$ and $$$X$$$ is minimum as possible (call this $$$X$$$ : $$$X_0$$$).

When $$$H \ge H_0$$$, because the rate of change when $$$H$$$ increases by $$$1$$$ in $$$F(H)$$$ is $$$AN−M(N−X) \Rightarrow $$$ when $$$H$$$ increases $$$\Rightarrow X$$$ increases $$$\Rightarrow AN−M(N−X)$$$ increases . The same thing implies with $$$H \lt H_0$$$, when $$$H$$$ increases $$$\Rightarrow X$$$ increases $$$\Rightarrow -RN + MX$$$ increases.

• Case 1: Suppose $$$AN−M(N−X_0) \lt 0$$$, when $$$H$$$ increases the rate of change will go from negative to positive. And the function will go like this:

So it's a part of a unimodal function. We need to prove that with $$$H \lt H_0$$$ the function $$$F(H)$$$ will be the remaining part of that unimodal function.

• Case 2 : Suppose $$$AN−M(N−X_0) \gt = 0$$$, no matter the sign of $$$-RN+MX$$$ it will always make an unimodal function because the monotonicity of $$$-RN+MX$$$ and $$$AN−M(N−X)$$$.

Thanks so much <3

Could I ask some stupid questions ^^ ?

1. So do you mean your "$$$c$$$" is the local minima of the function?

2. And the form of your function is $$$F(x) = ay + bz$$$, so how do you ensure that $$$F(x - 1) \lt F(x)$$$ or $$$F(x + 1) \gt F(x)$$$ or something like that? It actually wasn't intuitively understandable for me.

Sorry for my poor logic ^^. Hope you will answer me <3 <3. Thank you

I have a question. How can we deal with the problem of calculating $$$LCM(l, l + 1, ..., r)$$$ % $$$(1e9 + 7)$$$ with $$$r - l + 1 \lt = 1e6$$$ and $$$l, r \lt = 1e14$$$ (1 query only) ?

Thanks for reading <3 <3.

Thanks

And the time complexity if $$$O(1)$$$ also ?

Can I ask a quite stupid question ? What is the complexity of __builtin_clz ? Is it $$$O(1)$$$ or $$$O(log n)$$$ ?

Thanks <3.

Me: Scrolled down the comments section to see if this was a joke :').

People will not have your information like nations, names, schools, ... and you are free to speak what you think straight without worry about some of personal reasons.

Thanks! So the problem setters need to think harder and harder everyday to have new problems for us. Really appreciate them <3.

You know people use clones to post weird posts, don't you :D ?

I stucked at this problem too. There are some suggestions here. But he didn't mention how the transtions between the DP states work. I have been comtemplating about that for 3 days and still didn't have an idea.

Can anybody help please ?

Thanks for reading <3 <3.

Thank you for clarify it out <3 <3. At first, I was thinking $$$d[n + 1][j + 1][m + X]$$$ can include $$$d[n + 1][j][m]$$$ somehow but it turned out to be wrong.

Love you <3 for answering my question.

Any..body kind in this awesome Codeforces community :< ?

Sorry for asking these silly questions but what knowledge or definitions I need to learn in order to understand what is $$$N_{\supseteq T}$$$, $$$N_{= T}$$$, $$$N_{= \emptyset}$$$, ... and what really $$$N$$$ and $$$T$$$ represents for in this definition: (Because it just pops up from nowhere and I could not understand).

Thanks for reading and helping me!!.

Anybody can help me :<< ?

In problem 167B — Wizards and Huge Prize editorial, it says "The answer will be the sum of $$$d[n+1][j][m]$$$ for all $$$j,m$$$ such ...".

I have the question about this: What if there are some $$$d[n + 1][j + 1][m + ...]$$$ that will include $$$d[n + 1][j][m]$$$ (What I means is they are not distinct to each other), so can we just sum all of them so simply like that?.

I learned that: Only if all the events A, B, C, .. are pairwise distinct, $$$P(A + B + C + ...) = P(A) + P(B) + P(C) + ...$$$. So how are all the $$$d[n + 1][j][m]$$$ are pairwise distinct anyway?

Sorry for my bad English, thanks for reading <3 <3.

Thank you guys very much <3 <3.

So E1 editorial solution can be done for E2 also with some modifications (or a lot of modifications :D). Am I right?

I also wonder about the time complexity :<. Could anyone clarify this?

Could you suggest me some problems of this type?

Nobody can help me ? :(

Can you suggest anything else? Because that article doesn't focus on explaining the smaller_to_larger I think.