Mynavi Programming Contest 2021（AtCoder Beginner Contest 201）Problem C Problem Link

I read the editorial it used brute force approach

Is it possible to do this question using math? (without checking for 10^4 possible passwords)

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

1 | Benq | 3796 |

2 | tourist | 3722 |

3 | Radewoosh | 3719 |

4 | ecnerwala | 3578 |

5 | ksun48 | 3462 |

6 | Um_nik | 3456 |

7 | maroonrk | 3445 |

8 | jiangly | 3431 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

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

1 | 1-gon | 207 |

2 | awoo | 186 |

3 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 177 |

5 | Radewoosh | 177 |

7 | -is-this-fft- | 176 |

7 | maroonrk | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 170 |

Mynavi Programming Contest 2021（AtCoder Beginner Contest 201）Problem C Problem Link

I read the editorial it used brute force approach

Is it possible to do this question using math? (without checking for 10^4 possible passwords)

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/16/2021 03:51:54 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Yes you can solve this problem with combinatorics.

Can you tell me about your approach

If the pins were of unique elements, you would solve it with basic combinatorics. But since that's not the case, you should still iterate over the elements to subtract those overlaps, considering many cases.

Still, that's my opinion, I am very interested if some, not complicated formula exists for this.

yes me too

you can use combinatorics:

if an element is fixed ('o') you can use polynomial: $$$exp(x) - 1 = \frac{x}{1!} + \frac{x^2}{2!} + ... $$$

in other case ('?'): $$$exp(x) = 1 + \frac{x}{1!} + \frac{x^2}{2!} + ... $$$

The answer consists first of multiplying all these polynomials and answering the coefficient 4 multiplied by 4!

Using the fact that $$$exp(x) ^ c = exp(c * x)$$$ you have 6 cases for each number of characters 'o'.

code

answer $$$= \sum\limits_{i=0}^b (-1)^i \binom{b}{i} (a + b - i)^4$$$

where a = #'?' and b = #'o'.

In general you need to calculate the coefficients of $$$(x - 1)^k$$$, which can be achieved in $$$O(k)$$$.