Hi aryanc403! It is not a typo :)

The prize is for users who have never been "red". Good luck in the contest!

I think they don't have the star because they can hack official participants in hacking phase. In regular div 2 rounds the rooms for official and unofficial participants are separated.

I think your comment is overrated

You should seek help

Suppose we take two arrays a,b such that the ascending array ends with number i, and descending array ends with number j. If we count all ascending arrays ending in i and descending arrays ending in j, then we have the answer for this specific i,j.
Once we can do that, we can simply iterate over all i,j (with $$$i <= j$$$) and get the total answer by summing these values.

So the question is, given an ascending array ending in the number i, with length m, how many such arrays can there be? We can see that such an array can be like 11122233...i, or can be 1222333444...i, or iiiiiiii...i. So let $$$a_1$$$ be the number of elements that are 1, $$$a_2$$$ be the number of elements that are 2, and so on till $$$a_i$$$. Then the answer is equivalent to the number of integer solutions to $$$a_1 + a_2 + a_3 ... a_i = m$$$, where $$$a_i >= 1$$$ and the rest are $$$geq 0$$$. The answer to this is through stars and bars $$$C(i + m - 2, m- 1)$$$. Similiarly you can do for j (you need numbers from j to n), and you will get something like $$$C(n - j + m - 1, m - 1)$$$. and then multiply and sum to calculate the answer.

The answer can be proven to be

a[1]<=a[2]<=a[3]<=a[4] .. a[m]
b[1]>=b[2]>=b[3]>=b[4] .. b[m]
and a[i]<=b[i] for every i (1 --> m)
so we can merge the two arrays into one array like that 
a[1] a[2] a[3] ... a[m] b[m] b[m-1] b[m-2] ... b[1]
then we can solve it with dp[last][i] 
and for every element i we can assign any number large than a[i-1] (last) and less than n 

check this 68817461

:)) cin >> n >> m; cout << C(n + 2 * m — 1, n — 1);

Suppose m=6 ,A=[1,2,2,3,4,5] and B=[9,8,7,7,5,5] Now make a new array X of size 2*m whose first m elements are same as A and next m elements are same as B but in reverse direction. So new array becomes- X= [1,2,2,3,4,5,5,5,7,7,8,9] The new array X is non decreasing in nature. So basically for every correct pair of A and B, its X will be non-decreasing in nature. So, you basically have to find number of possible non decreasing array of size 2*m whose elements are between 1 to n. This could be easily calculated using dp.

Code- (http://mirror.codeforces.com/contest/1288/submission/68824571)

Use bit masks to know for each line the minimum value of each mask of it, then combine the best mask and ((1<<m)-1 ^ mask) to find the answer

You do a binary search on the answer. Then for checking if an answer $$$x$$$ is valid, you can make a $$$m$$$ bit mask for every array in which $$$i$$$th bit is $$$1$$$ if $$$a[i]$$$ is greater than $$$x$$$. The problem now is to find two arrays so that bitwise or of the mask of two arrays is equal to $$$2^m - 1$$$. For that you can just fix one array and brute force all possible masks which complement current mask (which are less than $$$2^m$$$) and find if the mask is among the mask of all arrays. If there is one then the answer $$$x$$$ is valid otherwise no.

For each array and for each mask (out of $$$2^m$$$ of its indexes) calculate a minimum value. Then go through the input and for each array $$$i$$$ enumerate all masks $$$M$$$. Between all masks $$$M$$$ calculate maximum value of minimum(calculated minimum for mask $$$M$$$ of array $$$i$$$, maximum of calculated minimums for mask $$$2^m - 1 - M$$$ of all already processed arrays). The second value can be updated on the fly.

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

The answer for a given pair (A, B) is A * the count of numbers of the form 9, 99, 999, 9999, 99999.... that are less than or equal to B.

Basically a pair (a,b) is valid if and only if b is of the form 99...9. Therefore, you just need to count the number of numbers of this type between 1 and B and multiply by A.

a*b+a+b=a*10^p+b ==>b+1=10^p

Fix the length of $$$b$$$ and name it $$$i$$$. It can be between $$$1$$$ to $$$10$$$. Then we have $$$a \times b + a + b = a + 10^i \times b$$$. It simplifies into $$$b = 10^i - 1$$$. So no matter what $$$a$$$ is, $$$b$$$ is $$$10^i - 1$$$. So just check if $$$10^i - 1$$$ is between $$$1$$$ and $$$B$$$ and if it is add $$$a$$$ to the answer.

Whould you be so kind to explain what is going on in your solution?

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

Math shows that $$$b$$$ in the formula has to be of the form 999999...9, and $$$a$$$ doesn't matter.

a*b+a+b=conc(a,b). Let number of digits in b be d,then conc(a,b)=a*(10^d)+b. a*b+a+b=a*(10^d)+b a*b=a*(10^d-1), a!=0. b=10^d-1. hence b=9,99,999,.....99999999,as b<=10^9. So find the number of b's less than B,call it temp. Answer is temp*a.

Because when n > O(sqrt(d)), It always success. so that code must done O(sqrt(d))

The reasoning isn't wrong at all. Choosing $$$2*m$$$ elements that satisfy that condition would work. But $$$n^{2*m}$$$ is not the way to count that, since you are counting sequences that are invalid. This number is the total number of sequences of lenght $$$2*m$$$ some of which doesnt satisfy that condition.

You are overcounting.Say for eg if the $$$a_i$$$ and $$$b_i$$$ are $$$1,1,2,2$$$ then you count this as number.Then you also count $$$1,2,1,2$$$ and all permutation of it when you shouldnt be.To count the desired number we have to use stars and bars.

no ...i also did the same

Me too, and also KrK. Though it was a very easy formula :(

nope

Can you please share your approach ?

I solved using suffix sum. My relation came dp[i][j]= dp[i-1][j] + suffix_sum[i][j].

Me too, buddy ^.^

I just made sure to check the area +/-1 of sqrt(d) just to be safe.

Can you explain why did you take the ceil of sqrt(d)*2 ?

a + (d/a) >= 2*sqrt(d)

so, a + ceil(d/a) >= 2*sqrt(d) ?

Minimum position is 1 or i, we only need to calculate max now. Let's find first position of i, before i becomes first every number larger than x changes position by one, so it's 1 + number of distinct integers larger than i before this position. Now between 1st position and 2nd, 2nd and 3rd, and so on, it's position is just 1 + number of distinct integers in range. This stuff can be calculated with segment trees.

Also, you could simulate the whole process.

In the beginning, $$$min_i = max_i = i$$$. When some element moves to the front, you set $$$min_i = 1$$$ and $$$max_i = max(max_i, a)$$$, where $$$a$$$ is its current position (because it is the element's rightmost position before it will be moved to the front). In the end, you update $$$max_i$$$ for every $$$i$$$ again, based on the positions of the elements in our sequence.

The insertion/deletion operations can be done with ordered_set, treap in $$$O(n + m \log n)$$$, or with split-rebuild sqrt decomposition in $$$O(n + m \sqrt n)$$$, 68820376, if you want to have fun.

P.S. This approach is quite structure-heavy, less thinking, more implementing (which makes it not really beautiful).

Fenwick tree+PBDS solution: Code

If you optimize for 7 days it will take 88/(7+1)+7=18 days.

take x=9

Also for 8 days it would be 8 + ceil(88 / (8 + 1)) = 8 + 10 = 18

You can count how many arrays start with $$$i$$$, are length $$$j$$$, and are non-decreasing by using

and how many arrays start with $i$, are length $$$j$$$, and are non-increasing by using

The answer is then

dp state could be dp[i][j] , i the curent position in the array we are placing integers on, j curent difference between the numbers on i-1 position

Go to submissions tab of the user and hack from there by opening the link (and not the popup).

How you arrived at this solution?

It might be convenient to use 1e9 + 7 when modulo = 1000000007, as it's both easier to read and less prone to mistakes :)

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 ).)

AM>=GM, https://mirror.codeforces.com/blog/entry/73061?#comment-573250

i also did it this way

It's not correct. Function f(x)=n/(x+1)+x has the smallest value in point sqrt(n)-1

Its not possible to hack this, because it is always correct.

Proof: We need $$$x + \lceil \dfrac{d}{x+1} \rceil <= n$$$. Since $$$ \lceil \dfrac{d}{x+1} \rceil <= \dfrac{d}{x+1} + 1$$$, we try to solve $$$x + \dfrac{d}{x+1} + 1 <= n$$$.

$$$ y + \dfrac{d}{y} <= n $$$,

$$$ y^2 - n*y + d <= 0 $$$

$$$ ( y - a ) ( y - b ) <= 0 $$$, which means $$$y$$$ must be between both roots, so that we get negative sign.

i.e. $$$x+1$$$ should be between both roots. Also, both roots are centered around $$$\dfrac{n}{2}$$$, so this will always be true, if you take few possibilities around $$$\dfrac{n}{2}$$$ for values of $$$x$$$.

It says "sorted in non-ascending order" not just "non-ascending".