We will hold AtCoder Beginner Contest 205.

- Contest URL: https://atcoder.jp/contests/abc205
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210613T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: chokudai, kyopro_friends, Kodaman, tozangezan
- Tester: penguinman, tatyam
- Rated range: ~ 1999

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

1 hour until the contest start. Good luck to all participants.

How to solve E?

Just the same way as compute Catalan number.

Origin way：(0, 0) to (n, m)

Baned way：(0, 0) to (n, m) which cross line $$$y = x + k + 1$$$. thus it can be consider as (0, 0) to $$$(n - k - 1, m + k + 1)$$$

So the answer is $$$\binom{n + m}{n} - \binom{n + m}{n - k - 1}$$$.

You need to consider the special case $$$n == k$$$ and $$$n > m + k$$$.

`total number of arrangements = (n+m)!/n! * m! now we have to remove all those failing arrangements`

`for a given arrangement lets move from left to right and stop at the very first index where the arrangement fails (call it i ) than that index must be satisfying w=b+k+1 and the ball at ith position is white and the remaining suffix can have any permutation, now we vary b from 0 to m check the number of permutations with a prefix having b balls and b+k white such that the white ball follows that prefix`

`for each b we must always make sure the wi != bi + k+ 1 for any bi < b , this can be done by storing the sum (2*j + k) /( j! * (j+k)! ) for all j<b and substracting it from (2*b + k ) /( b! * (b+k)! )`

can you explain the ending part a little more??

ok I will Try To explain with an example let N=7 M=4 K=3 Total number of perm = 11!/7!4! Now we will Remove all the Failing case

`Failing Cases are those that satisfy wi = bi + k + 1 for some i and ith ball will be white`

lets break each failing arrangement like this`Failing Prefix`

`W`

`Suffix`

`b=0 w=4`

only possible arrangements of failing prefix is`WWW`

and possible arrangements are`WWW`

`W`

`3B and 3W in any order`

b=1 w=5 ,`the first failing prefix will have 4 W and 1 B but it's prefix is should be distinct from any prefix of b=0 w=4 case to avoid multiple reduction for same case`

thus all permutations of 1 B and 4 W except this WWWWB are valid choice for Failing Prefix . So How can we do this ?? This can be done by follows for every b , any Failing Prefix of b-1 will have z=2*(b-1) + K balls , now while adding one more B and W ball to it can B added to any of the z+1 positions and then W can be added to any of the z+2 positions followed by substraction number of failing prefixes of b-1 beacuse we don't want to add WB and the end of any failing Prefix of b-1can you provide the code. I am subtracting the failing prefix in O(N) time. which makes my code O(N^2).

`sum (2*j + k) /( j! * (j+k)! )`

This is not the complete formula. You are missing the ways you can do the combination of left Black and White balls.`sum(2 * j + k) / (j! * (j + k)!) * C(2 * (i - j) - 1, i - j)`

and

`C(2 * (i - j) - 1, i - j)`

part makes removing the failing prefix O(N) time.How to solve F?

We can transform it into Flow problem：

Hello, can you please provide me some similar problems to this, I have been looking for more problmes like this,but didn't find one....Thanks in advance :)

POJ3281 Dining

POJ3436 ACM Computer Factory

CF546E Soldier and Traveling

GYM The Cool Monkeys

SPOJ IM — Intergalactic Map

you may search for tag

for example 1473F - Strange Set

How to solve F?

Somewhat big gap from D to E

Also in terms of number of solved, E and F seem to be of same difficulty.

D :_(

The same thing happened to me. Then I changed high from 1e18 to 2e18. I got accepted:).

Binary search implementation issue in your code ig.

Check out my solution using binary searchif A is a permutation of 1 to 1e5 and K=1e18. answer would be 1e18+1e5 so set high to 1e18+1e5.

E,F?

I used to treat ABCs as Div. 3 contests.

F's editorial:

This can be boiled down to a maximum flow problem.So I was wrong again? -_-

This is a relatively easy problem for practicing max flow, you should take this as an opportunity to learn it.

Since Maximum flow algorithms are currently excluded from the IOI, I don't think that I want to bother with learning them for now.

I guess this was more kind of educational max flow problem.

how to solve C

You can read the editorial: https://atcoder.jp/contests/abc205/editorial/2078

Why F cant solved by finding maximum matching between tokens and (ri and ci). I tried to solve it using Kuhn's algorithm but getting the wrong answer in one test case. Here is my solution. please find an error.

I also tried something similar. For every piece that can be placed at rows $$$a \le u \le c$$$ and columns $$$b \le v \le d$$$, I added a bidirected edge from each row $$$u$$$ to each column $$$v$$$. Then I computed a maximum matching on this graph with Hopcroft Karp. Since there can be more matches than pieces, I thought we can then match these matchings to the pieces which can be placed on these cells, by adding edges between cells and pieces in a new graph. Since these cells are independent in that no two share a row or a column, I thought these must include the solution. The idea is obviously overkill, but is there a flaw in the idea?