How to solve the problem from latest Codechef Long Contest :

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

1 | tourist | 3757 |

2 | jiangly | 3590 |

3 | ksun48 | 3582 |

4 | Um_nik | 3539 |

5 | maroonrk | 3533 |

6 | slime | 3498 |

7 | djq_cpp | 3486 |

8 | Radewoosh | 3442 |

9 | cnnfls_csy | 3427 |

10 | ko_osaga | 3355 |

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

1 | -is-this-fft- | 184 |

2 | awoo | 181 |

3 | dario2994 | 171 |

4 | SecondThread | 169 |

4 | maroonrk | 169 |

6 | Um_nik | 168 |

7 | adamant | 166 |

8 | YouKn0wWho | 165 |

8 | errorgorn | 165 |

10 | antontrygubO_o | 162 |

How to solve the problem from latest Codechef Long Contest :

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/03/2022 20:10:23 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Let's think of a way construct a permutation: Initially, it's empty. One by one, we add an element. Assume, after that we have permutation p1, p2, ..., pk and pi is recent element. So, we must have: p[i-1] + d > p[i], p[i] + d> p[i+1]. If the sequence we add is non-decreasing, then we just care about the condition p[i-1] + d > p[i]. Clearly, the way we add pi equals to the number of element before pi (in sorted non-decreasing sequence) that greater than p[i]-d and plus one for adding at first position. (*) Therefore, we have a solution in O(m * n * log(n)). In order to improve that complexity, in each query, we maintain the number (*) for each element. And in each query, there are O(D) element is affected. Complexity reduce to O((n + m) * d).

But how are we counting the number of valid permutations using the above logic, Could you please elaborate your solution ??

It's the product of them. Example, we have sequence: 1, 3, 4, 7, 9 and d = 3. There is no number less than 1 and greater than 1 — 3. There is one number less than 3 and greater than 3 — 3. There is one number less than 4 and greater than 4 — 3. There is no number less than 7 and greater than 7 — 3. There is one number less than 9 and greater than 9 — 3. So the answer in this case is: (0 + 1) * (1 + 1) * (1 + 1) * (0 + 1) * (1 + 1).

I got the approach, But what is the intuition behind this counting approach ??

Thanx got it :)

My solution is complicated. Let's maintain cnt[i] count the number of sequence equals to i in each query. Because, each element can be large as 10^9, so we must decompress them. After having cnt[i] for each i, we will be able to count the number of way add cnt[i] numbers value 'i' in the above way.

How to solve WRDSUM?

Use inclusive-exclusive principle: Almost always

F(n) =n. So we start with 2 + ... +n. Let's look how to fix our sumwe have to subtract and put instead.

we have to subtract and put instead.

we have to subtract and

and put , and instead.

And so on. If you calculate this properly you will get sth like this

The formula 2

^{d}+ ... +x^{d}is a polynomial of degreed+ 1 so we can use Lagrange interpolation to get coefficients, or precompute Bernoulli numbers and use Faulhaber's formula. Notice that maxDis around .Depending on implementation we should get sth like

O(D^{2}) or even faster solution. Use python or java to avoid bignum implementation.