Recent actions
Created or updated the text

Can you please explain the transition formula a bit more.

Created or updated the text

Yes, $$$dp[k][3][5] == dp[k][4][6]$$$.

We just use $$$i$$$ and $$$j$$$ to check if the range is non-empty, $$$dp[k][i][j] = 0, \text{if }i > j$$$.

You can also think that we will always normalize the range so that $$$i = 1$$$, eg [6, 10] -> [1, 5]. As $$$i$$$ is constant it can be remove from the state.

hey excellent transition. Could you provide a little explanation on why i , j dont matter just length j-i+1 enough . did u mean dp[k][3][5] == dp[k][4][6] ?

Well spotted. Turns out that in every problem I tested my code on, either the cost didn't matter (only the flow along each edge in an optimal flow did) or the capacity of every edge with nonzero cost was 1 :Dd

I submitted the fixed code to min-cost max-flow on kattis, so it should definitely now work.

Hey in the function minCostCirc() shouldn't the line: if (edges[ei].ru & h) res += incEdge(ei, h);

be changed to: if (edges[ei].ru & h) res += (h*incEdge(ei, h));?

(Since the new cost = previous cost + (flow added * cost of the negative cycle ).)

How did you think. Nice solution :)

I got invited eventually!

Hm. I can see how to reduce it to $$$O((nm + 3^m) \log \max a)$$$ (for each bit position, there are three valid pairs of bits), but not $$$... 2^m ...$$$

Yeah, even the editorial uses the exact approach described by you. No dp at all.

Will we get to know who won the prize?

what is 'x' in that comment ? I saw that comment but did not understood it. If you have understood can you explain it to me .Thanks

what is 'x' ?

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

Thanks a lot for your insightful explanation to D ! I learnt a lot from this beautiful problem !

Editorials?

Refer this comment for the solution approach of Problem E

If you know basic segment tree but do not know how to find range distinct queries, then you can see the accepted answer of this stackoverflow question. Its explained in very easy to understand language.

Ratings updated guys :) Finally...

old submission wrong on test case 50 which was Input

2

63242 999919263

63242 999919264

Participant's output

YES

YES

Jury's answer

NO

NO

new submission

this i used long double which solved the error

can anyone tell me why.

the ranges were 1<a,b<10^9 for which i think float would have worked fine

can some one explain how to solve problem E . I have knowledge of segment trees and BIT . But i have not solved much problem on them .

Sorry for u :( I start my for loop from 0 instead of 1 to get AC .. But the good thing i solved it afer the contest(it is not rated for me) :D

Finally, ratings got updated!

My rating has been updated!

Actually your code is right..You just have to calculate ceil value before if condition..I am not getting why this works.Maybe overflow

now

Me too. Added a +7 to my infinity and i got accepted. Feels bad man.

When it will be rated ?

At least, someone please tell the reasons behind the delay.

when will rating changes come out ?

Yes Its fixed

Isn't it already too late for results?

But sometimes its prediction is a little bit wrong.

Actually, it has already finished several hours ago.

System Testing is finished I got a wrong answer on D and it was Ac yesterday ! But idk why the rating didn't update yet .

System testing finished.If you have any confusion check test cases of AC solution.(Like: problem A run 68 test cases)

The system testing actually finished at about 7 hours ago! <D

when will be the rating updated

yeah you've got a point ,lets hope they start system testing soon enough

system testing is done ig

Oh, my bad. I didn't realize that! Thanks for informing me!

There was systesting

You are absolutely correct! But those ratings are not accurate. Some people may fail system testing! Lets hope that codeforces starts system testing very soon.

meanwhile we could check our ratings here https://cf-predictor-frontend.herokuapp.com/

Before rating changes, there is system testing. So all the hacks would be added to the main tests. System testing didn't even start!!

Why didn't the rates changed till now?

Maybe Mike had been busy fixing Codeforces SSL Certificate issue. Looks like its fixed now.

It has been more than 6 hours until open hacking finished. System testing didn't even start yet! I feel like codeforces is having a problem with something!

I'm also waiting. It's too hard.

Hi,can you explain detailedly? I can't understand it.

what is wrong in codeforces system?

1288A - Deadline can be solved using the first derivative of f (x) = x + d / (x + 1) because when this is 0 it is because this point is a minimum, here we see the third case of the example:  the derivative gives us: 1 — d / (x + 1) ^ 2 and if we equal it to zero it gives us x = sqrt (d) — 1, if we substitute this in the original function it results in (2 * d — sqrt ( d)) / sqrt (d), if this value is less than n then we print "YES" or else "NO". My submission is 68818558

68861515 please help me optimize my code for problem E(Messenger simulator) in educational round 80. It gives TLE on testcase 9.Thanks in advance

During and after the contest there were no signs of any issues with the tests or whatsoever, so we should keep our faith strong.

Why is the rating changes not published even after 6 hours of completion of open hack phase?

When the new ratings will be available? Can anyone tell that?

okay,i just check sqrt(x) and accept

How on earth happens with codeforces rating calculating system?

Are the ratings even going to update??

should be sqrt(x) or sqrt(x)+1, and just to be save, better check all x from sqrt(x)-3 to sqrt(x)+3 for optimal value.

choose x to be n/2 or (n + 1) / 2

Yes, here's a $$$O(1)$$$ solution. $$$x + \lceil \dfrac{d}{x + 1} \rceil \leq n \iff \lceil \dfrac{d}{x + 1} \rceil \leq n - x \iff d \leq (n - x)(x + 1) \iff x^2 + (1-n)x + (d-n) \leq 0.$$$ This inequality has solutions in real nonnegative numbers if and only if $$$(n - 1)^2 \geq 4(d - n)$$$. Actually, working under assumptions of the problem, it has nonnegative integer solutions if and only if it has nonnegative real solutions, so we just need to check the inequality $$$(n - 1)^2 \geq 4(d - n)$$$ to obtain the answer. https://codeforces.com/contest/1288/submission/68780664

Is there a better way to do A other than binary search?

I tried binary search but it fails on test 50.

Waiting for 4 hours already !!

To be honest, I haven't met such situation. So who can tell me what's the matter with codeforces?

yep, I had the same question. Too long :(

Me too, buddy ^.^

It seems like they have written dp as there is a small dp modification which can reduce the comp to (nm+2^m)(log(max))

Should've set the constraints higher :^) It's ok I guess but minimum cost circulation was the intended solution.

Soo... Is it ratted?

EDitorial Please of Educational Round 80

Couldn't it be the case that 2√d <= n but a + d/a > n?

can you explain how to do that . I have only read theory of fenwick tree .

Fenwick tree+PBDS solution: Code

Ok.Got it. Thanks

it can be solved using dp in O(n^4*m)

This can be done with dp, instead of formuales directly. ( Maybe it could be done with formulaes, but I can't think of it ).

Let $$$dp[i][j]$$$ be number of ways to choose both $$$a[i]$$$ and $$$b[i]$$$ with $$$a[i] = j$$$

So, we must use $$$dp[i-1][x]$$$ where $$$ x >= j $$$ to make this result, and when $$$a[i]=j$$$, $$$b[i]$$$ can take $$$n-j+1$$$ values ( $$$j, j+1, j+2, ... n$$$ ). ( Note, $$$b[i]$$$'s are independent of each other ).

Because $$$ a_i >= 1$$$, as the sequence ends in i. Therefore we can make $$$a_i >= 0$$$ and take m = m — 1.

The no of integer solutions of a1+a2+a3+...+ai=m is given C(m+(i-1),m) but why did you write C(i+m−2,m−1)? I think you took m=m-1, but why?

System testing is finished :D

The system testing seems to be ended!

Does anyone know when the system testing starts?

Can't wait so long to become Master :/

I did it without the ceil and got AC.

rated for div2!

It is very irritated !

$$$b$$$ cannot be anything. $$$a_i <= b_i$$$ for all $$$i$$$ has to still hold for the inclusion-exclusion calculation to hold. P.S. Thanks for the link.

$$$(a,D)$$$ is number of ways of choosing array $$$a$$$ of length $$$m$$$ with values between $$$1$$$ and $$$n$$$, such that it's elements are in descending order, ( and $$$b$$$ can be anything, so we must multiply a factor of $$$n^{m}$$$ ).

Now, number of descending depends a lot on your exact definition of "descending". Is it "strictly descending"? Is $$$[5,3,3,2,2]$$$ descending?

If you want only strictly descending, then you just need $$$m$$$ distinct values ( because "strictly" forces no repitition of values ). So final $$$(a,D)$$$ will be $$$ choose(n,m) * n^{m} $$$. ( $$$choose(n,m)$$$ chooses $$$m$$$ distinct values from $$$n$$$ possible values, and there is only one "strictly descending" ordering of these $$$m$$$ chosen values. )

If your definition of descending array allows equal values, then we have the following equation to solve:

$$$x_n + x_{n-1} + x_{n-2} + .... + x_3 + x_2 + x_1 = m$$$

$$$x_{i}$$$ denotes number of $$$i$$$s that we take in our array. We must find all non negative ( $$$x_i >= 0$$$ ) solutions of the equation, which is given by $$$choose(n+m-1,n-1)$$$. You can read more about Stars and Bars.

So, answer in this case would be, $$$(a,D) = choose(n+m-1,n-1)*n^{m}$$$.

$$$a + \dfrac{d}{a} \ge 2 \sqrt{d}$$$ is of course right, and $$$a + \left\lceil\dfrac{d}{a} \right \rceil \ge 2 \sqrt{d}$$$ is also obvious (Because $$$\left\lceil\dfrac{d}{a} \right \rceil \ge \dfrac{d}{a}$$$ ). But I can't proof $$$a + \left\lceil\dfrac{d}{a} \right \rceil \ge \left \lceil 2 \sqrt{d} \right \rceil$$$ .

I'm wondering it. That's just the reason I post this comment. But it seems that I have passed the system test?

Why the rating hasn't changed?There is always change in two hours,but now is after the open hacking about five hours?

How would you solve $$$(a, D)$$$? This is precisely where I was stuck.

Tags only imply that it's possible to use a technique to solve the problem, and not necessarily that the technique must be used to solve the problem. I'm not exactly sure how to use DP to approach this problem though.

The only thing I came up with is the following. Let $$$dp[i][j][k]$$$ be the number of such arrays of size $$$i$$$ with $$$j$$$ and $$$k$$$ being the last elements of $$$a$$$ and $$$b$$$ respectively. Then $$$dp[i][j][k] = \Sigma dp[i-1][x][y]$$$ for all $$$1 \leq x \leq j$$$ and $$$1 \leq y \leq k$$$. We can maintain these sums using prefix sums. The total runtime will be $$$O(mn^2)$$$.

For solving the new question that you have raised,

We need to find number of arrays $$$(a,b)$$$ such that $$$a$$$ is not descending ($$$ND$$$) and $$$b$$$ is not ascending ($$$NA$$$).

Simple inclusion exclusion gives,

number of ways $$$(a,ND,b,NA)$$$ = $$$all(a.b)$$$ — $$$(a,D)$$$ — $$$(b,A)$$$ + $$$(a,D,b,A)$$$

$$$(a,D)$$$ denotes $$$a$$$ is descending. ( note $$$b$$$ can be anything here ).

$$$(a,D,b,A)$$$ denotes $$$a$$$ is descending AND $$$b$$$ is ascending.

Now, $$$all(a,b)$$$ is straightforward. So is $$$(a,D)$$$ and $$$(b,A)$$$. And, for $$$(a,D,b,A)$$$ we can use the method that was required to solve Original $$$C$$$ of the contest.

I've tried binary search + bitmask solution and it got accepted. Then I see the dp tag on this problem. Is there any dp involved here? or there is another dp solution?

How to solve c if both arrays are non decreasing?

For me, the wait is worth it! :D

Thanks for replying. This helped.

I understand the term "sorted ascending" as every element is bigger than the previous one, and "sorted non descending" as every element is not smaller that the previous one.

But basically it is the same, it works to simply see both as one and the same.