chokudai's blog

AtCoder Beginner Contest 205 Announcement
By chokudai, history, 4 years 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

Comments Comments (31)
| Write comment?
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    4 years 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$$$.

    → Reply
  • »
    »
    4 years 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)! )

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

      can you explain the ending part a little more??

      → Reply
      • »
        »
        »
        »
        4 years 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

        → Reply
        • »
          »
          »
          »
          »
          4 years 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).

          → Reply
    • »
      »
      »
      4 years 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.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

How to solve F?

→ Reply
»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

How to solve F?

→ Reply
»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Somewhat big gap from D to E

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

D :_(

→ Reply
  • »
    »
    4 years 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:).

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Binary search implementation issue in your code ig.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Check out my solution using binary search
    → Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

E,F?

→ Reply
»
4 years 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? -_-

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it -9 Vote: I do not like it

how to solve C

→ Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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?

    → Reply
»
5 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

abc205_c: Test cases do not have the case where both A and B are negative. Thus, one of my Wrong codes got ACCEPTED! 

→ Reply