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 \lt = 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 \gt = 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 !

......

Find number of pairs: X and 9, X and 99, X and 999..

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.

If $$$n \geq 2\sqrt{d}$$$ then the answer is always YES.

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