### chokudai's blog

By chokudai, history, 11 months 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!

• +77

 » 11 months ago, # |   +13 1 hour until the contest start. Good luck to all participants.
 » 11 months ago, # |   +14 How to solve E?
•  » » 11 months ago, # ^ | ← Rev. 2 →   +12 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$.
•  » » » 11 months ago, # ^ |   0 Can anyone help explain how we get the number of banned ways here? I'm still confused while reading the editorial. Will update if I can think of a beginner friendly explanation.
•  » » 11 months ago, # ^ | ← Rev. 3 →   +7 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
•  » » » 11 months ago, # ^ |   0 can you explain the ending part a little more??
•  » » » » 11 months ago, # ^ |   0 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
•  » » » » » 11 months ago, # ^ |   0 can you provide the code. I am subtracting the failing prefix in O(N) time. which makes my code O(N^2).
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 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.
 » 11 months ago, # | ← Rev. 2 →   -9 How to solve F?
•  » » 11 months ago, # ^ |   +27 We can transform it into Flow problem：
•  » » » 11 months ago, # ^ |   0 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 :)
•  » » » » 11 months ago, # ^ |   0
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   0 you may search for tagfor example 1473F - Strange Set
 » 11 months ago, # |   -10 How to solve F?
 » 11 months ago, # |   +27 Somewhat big gap from D to E
•  » » 11 months ago, # ^ |   +4 Also in terms of number of solved, E and F seem to be of same difficulty.
 » 11 months ago, # |   +6 D :_(
•  » » 11 months ago, # ^ |   +3 The same thing happened to me. Then I changed high from 1e18 to 2e18. I got accepted:).
•  » » 11 months ago, # ^ |   +2 Binary search implementation issue in your code ig.
•  » » 11 months ago, # ^ |   0 My code also get killed by the killer testcase:(
•  » » 11 months ago, # ^ | ← Rev. 4 →   0 D Solutionhere we go --solution of D(already present at geeks for geeks).
•  » » 11 months ago, # ^ |   0 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) 
•  » » 11 months ago, # ^ |   +8 if A is a permutation of 1 to 1e5 and K=1e18. answer would be 1e18+1e5 so set high to 1e18+1e5.
•  » » » 11 months ago, # ^ |   0 what a unluck, i could'n think of it in hurry but now when i changed the limit to 2e18, it got me AC.
 » 11 months ago, # |   -8 E,F?
 » 11 months ago, # |   +34 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? -_-
•  » » 11 months ago, # ^ |   +5 This is a relatively easy problem for practicing max flow, you should take this as an opportunity to learn it.
•  » » » 11 months ago, # ^ |   +7 Since Maximum flow algorithms are currently excluded from the IOI, I don't think that I want to bother with learning them for now.
•  » » » » 11 months ago, # ^ |   0 Well, good luck with IOI!
•  » » 11 months ago, # ^ |   +5 I guess this was more kind of educational max flow problem.
 » 11 months ago, # |   -9 how to solve C
•  » » 11 months ago, # ^ |   0
•  » » 11 months ago, # ^ |   0 You can read the editorial: https://atcoder.jp/contests/abc205/editorial/2078
•  » » 11 months ago, # ^ |   0 if c is even, negative a or b will not matter, so you just had to make them positive and the rest is simple mathematics. implementation here
•  » » 11 months ago, # ^ |   0
•  » » 11 months ago, # ^ |   0 This problem can be solved using the fact that if ac > bc => a2 > b2 when c is even and => a > b when c is odd. The same holds true for < sign also. My Code int a, b, c; cin >> a >> b >> c; if (c & 1) { c = 1; } else { c = 2; } int x = pow(a, c); int y = pow(b, c); if (x == y) { cout << "="; } else if (x < y) { cout << "<"; } else cout << ">"; 
 » 11 months ago, # |   0 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.
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 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?
 » 11 months ago, # |   0 In problem D, I tried to frame the problem like K-th Number in union of segments. I tried to divide the given array in array of ranges` that were absent from the given array and later applied binary search. but failed miserably. here is the implementation of the same. I yet not able to figure out where i am going wrong, could you please guide me a little.
 » 8 months ago, # |   -8 wrong