### chokudai's blog

By chokudai, history, 2 years ago, We will hold AtCoder Beginner Contest 205.

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

We are looking forward to your participation! Comments (30)
| Write comment?
 » 1 hour until the contest start. Good luck to all participants.
 » How to solve E?
•  » » 2 years ago, # ^ | ← Rev. 2 →   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$.
•  » » 2 years ago, # ^ | ← Rev. 3 →   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
•  » » » 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-1
•  » » » » » can you provide the code. I am subtracting the failing prefix in O(N) time. which makes my code O(N^2).
•  » » » 2 years ago, # ^ | ← Rev. 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.
 » 2 years ago, # | ← Rev. 2 →   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 :)
•  » » » »
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   you may search for tagfor 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 searchfrom bisect import bisect_left n, q = map(int, input().split()) a = list(map(int, input().split())) for __ in range(q): k = int(input()) low, high = 1, 2*10**18 while low + 1 < high: mid = (low + high)//2 i = bisect_left(a, mid) #lower bound of mid if mid - i > k: high = mid else: low = mid print(low) `
•  » » if 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.
•  » » 2 years ago, # ^ | ← Rev. 2 →   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?