### ciprianfarcasanu's blog

By ciprianfarcasanu, 11 years ago, Can someone explain me how can i solve the C problem (round 53) because i have no ideea better than O(N^2)? Thx  Comments (4)
 Let A be the set of all arrays of length n in non-decreasing order with entries from the set {1,..,n}.Let B be the set of all arrays of length n in increasing order with entries from the set {1,...,2n-1}.Let f be a function such that f : A->B and f(x)=y, where y [ i ] = x [ i ] + i, for all i in {0, ..., n-1}.First let us show that y=f(x) is in B. y is of length n and minimum of y[i](i in {0,...,n-1}) is minimum of x which is 1and maximum of y[i](i in {0,...,n-1}) is x[n-1]+n-1 which is n+n-1=2n-1. So y is in B.Let us show that f is bijective.First let us show that f is injective.Let x1, x2 be in A and x1!=x2. x1!=x2 implies that there is an i in {0, .., n-1} such that x1[i]!=x2[i] or equivalentlyx1[i]+i!=x2[i]+i or f(x1)!=f(x2). So f is injective.Now let us show f is surjective.Given y in B and we take x such that x [ i ] = y [ i ] - i, for all i in {0,...,n-1} we can notice that x is in A(x is of length n and x[i] is in {1,...,n} for al i in {0,...,n-1} because minimum of x[i] is 1 and maximum is n ( don't forget that y is increasing )).So f is surjective.Thus f is bijective.A and B are finite so they have the same number of elements.We need to find the number of elements in A because the answer we are looking for is the cardinal of the set of arrays A union with the set of all arrays in A in reverse order(let's denote it by R).Notice that |A|=|R| and that |A union R| = |A|+|R|-|A intersection R|. A intersection R is the set of constant arrays and |A intersection R| is n.So the answer is 2*|A|-n.But |A| = |B| and B is the set of all increasing arrays of length n with entries from{1,..,2n-1}.So the answer is the binomial number. So |A|=|B|=((2n-1)!)/((n!)*((n-1)!)).Thus the final number is 2*(((2n-1)!)/((n!)*((n-1)!)))-n. Notice that you need modular arithmetic inverse to compute the binomial number.The computation of the modular inverse can be done in O(log n) by using Fermat theorem or gcd properties.
•  Very interesting solution, thank you for the detailed explanation:)
 I read once the part with the bijective function in combinatorics book written by Ioan Tomescu and it stuck to my mind. You are welcomed!
 » Why B has numbers from 1 to 2*n -1 ? The problem says only from 1 to n . I didn't understood use of C(2*n-1 , n) .. Any response are welcome . Thanks