adityagamer's blog

[HELP] Edu round 86 Problem E
By adityagamer, history, 11 months ago, In English

Whats wrong with my solution for problem E : https://mirror.codeforces.com/contest/1342/problem/E?

Let c = n-k. Number of ways such that c columns are filled = (Number of ways such that <= c columns are filled) — (Number of ways such that <= c-1 columns are filled)

So formula is $$$ \binom{n}{c}c^n - \binom{n}{c-1}(c-1)^n $$$

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This comment is to bring this blog in recent and actions.

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

I guess that you got the formula for the number of ways such that $$$\le c$$$ columns are filled is $$${n \choose c} \cdot c^n$$$ as follows: you're trying to choose the columns you can use (this is $$$n \choose c$$$), and then you slot each rook into one of the chosen columns (this is the $$$c^n$$$ part).

Unfortunately, it counts some of the rook placements multiple times. For example, suppose $$$n = 3$$$, $$$c = 2$$$. Then you count the placement "put all rooks in the first column" twice: once for choosing the columns $$$1$$$ and $$$2$$$, once for choosing the columns $$$1$$$ and $$$3$$$.

→ Reply