chokudai's blog

By chokudai, history, 7 weeks ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +77
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

How to solve E?

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    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$$$.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it +7 Vote: I do not like it

    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)! )

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain the ending part a little more??

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          can you provide the code. I am subtracting the failing prefix in O(N) time. which makes my code O(N^2).

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

»
7 weeks ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

How to solve F?

»
7 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

How to solve F?

»
7 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

Somewhat big gap from D to E

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

D :_(

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Binary search implementation issue in your code ig.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My code also get killed by the killer testcase:(

  • »
    »
    7 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    D Solution
    here we go --solution of D(already present at geeks for geeks).

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Check out my solution using binary search
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    if A is a permutation of 1 to 1e5 and K=1e18. answer would be 1e18+1e5 so set high to 1e18+1e5.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what a unluck, i could'n think of it in hurry but now when i changed the limit to 2e18, it got me AC.

»
7 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

E,F?

»
7 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

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? -_-

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +7 Vote: I do not like 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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

how to solve C

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.