Can someone explain me how can i solve the C problem (round 53) because i have no ideea better than O(N^2)? Thx

Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3567 |

3 | Um_nik | 3527 |

4 | ecnerwala | 3458 |

5 | maroonrk | 3409 |

6 | 300iq | 3317 |

7 | Petr | 3272 |

8 | LHiC | 3229 |

9 | Benq | 3226 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 197 |

2 | antontrygubO_o | 188 |

3 | pikmike | 183 |

4 | Ashishgup | 182 |

5 | vovuh | 179 |

6 | Radewoosh | 167 |

7 | Um_nik | 165 |

8 | tourist | 163 |

9 | McDic | 162 |

10 | Geothermal | 157 |

Can someone explain me how can i solve the C problem (round 53) because i have no ideea better than O(N^2)? Thx

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/02/2020 13:13:24 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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[0] which is 1

and 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 equivalently

x1[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.

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