deleted

When people downvote for no apparent reason. :(

But solutions everytime is ready before the contest cause how authors get right answers on tests?

Why is this downvoted even though it is perfectly fine and resonable question? It makes much more sense for authors to release editorials right after contest, cause after two weeks just a tiny fraction of participants will still be interested in reading them.

love short statement with no long story else I will submit sample :>

But if you can't solve the problem a good story might cheer you up :)

Nope

then,are u NaCly_Fish?

I think you are not real NaCly_Fish...

Of coures you can.

You can be able to participate in division 2 if your rating is lower than 1900.

I suggest you register another account with a different username and forget about your current account. I learned the hard way that having "tmw" as a prefix and a permutation of "168" as a suffix of your username will give you a significant disadvantage.

Hurry, before it's too late.

this is truly a player who believes in submitting at 1:59:59

once I post the same statement , I got approximately 30-40 downvotes...

deleted

what happend?

good job, you just joined us.

But U can understand it through translators like This and stuff on the Internet. Or U can just work hard on learning English(as a mid-school student in China, I always do this)

are my eyes blind? why it shows and 49 + 15 = 64?

Your Solution to Count Pairs is awesome. ;)

I was expecting you would submit it anytime.

I was also watching leader board for almost one hour and then the idea struck me in last 6 mins.

Hint :$$$(x-y)(x+y)(x^2+y^2)=(x^4-y^4)$$$

Just idea — lated for submit:

Let's iterate over a.
Fix ai. Then you have cube equation aj^3 + Baj^2 + Caj + D ~ 0 (mod p). I assume that at least one root has to be in interval [1..1000] or [p — 1000..p]. Let's say you found that root r. Then you can reduce to square equation. And square equation can be easily solved.

P.S. Sorry for this dumb reply). That was really easier than I assmued

Multiply by (x1-x2). You now have (x1^4 — x2^4) = k(x1 — x2) (mod p) this gives (x1^4 — k(x1)) — (x2^4 — k(x2)) = 0 (mod p)

So you just calculate x1^4 — k(x1) for all indices then just select any two with same values.

This problem is more math than cp.

Look at roots of polynomial :D ($$$a=-b$$$, $$$a=ib$$$, $$$a=-ib$$$) add $$$a=b$$$ for symmetry.

I found it by noticing that

$$$(a + b)(a^{2} + b^{2}) = a^{3} + a^{2}b + ab^{2} + b^{3} = a^{3} \frac{1 - \left(\frac{b}{a}\right)^{4}}{1 - \frac{b}{a}} = a^{3} \frac{1 - \left(\frac{b}{a}\right)^{4}}{\frac{a-b}{a}} = a^{3} \frac{a - \frac{b^{4}}{a^{3}}}{\frac{a-b}{a}} = \frac{a^{4} - b^{4}}{a - b}$$$ by the formula for geometric sum.

That's just a difference of two squares,but why does it be related to the problem?

Well, I think the formula $$$a^2-b^2 = (a-b)(a+b)$$$ is taught at 6'th grade (at least in Azerbaijan). So, $$$(a+b)(a^2+b^2)=\frac{(a+b)(a-b)(a^2+b^2)}{a-b}=\frac{(a^2-b^2)(a^2+b^2)}{a-b}=\frac{a^4-b^4}{a-b}$$$

Grade school math.

The main idea is the beauty won't exceed $$$\frac{100000}{k-1}$$$, then you can use $$$\mathcal O(nkbeauty )$$$ dp to solve it.

I enjoyed staring on the scoreboard.

thanks for the early editorial

please , explain proof.

you can find the sum using seg tree

Note that edge between B and F has odd cost, which is prohibited by problem statement.

With integer weights, it's impossible, note that the problem statement specifies that all numbers are even.

With real weights, add for example

• E to F: $$$9.5$$$
• E to D: $$$0.5$$$
• F to C: $$$-0.5$$$
• F to D: $$$2$$$
• C to D: $$$1.5$$$

I came to that almost immidiately and then kept thinking about making an $$$n*maxBeauty$$$ dp $$$k$$$ times or $$$k*maxBeauty$$$ dp $$$n$$$ times until the end of the contest. And then i look at the solution and see "do $$$n*k$$$ dp $$$maxBeauty$$$ times"...