dush1729's blog

Atcoder Beginner Contest 202 Unofficial Editorial ( A — E )
By dush1729, history, 4 years ago, In English
A
B
C
D
E
  • Vote: I like it
  • +36
  • Vote: I do not like it

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

To avoid overflow in D you could use the formula $$$\binom{n}{r}= \binom{n-1}{r} + \binom{n-1}{r-1}$$$

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

    The other trick to avoid overflow is to go horizontally across 1 row of Pascal's triangle.

    ll ncr(int n, int r) {
    if (n < 0 || r < 0 || r > n)
        return 0;

    ll ans = 1;
    for (int i = 1; i <= r; i++) {
        ans *= (n + 1 - i);
        ans /= i;
    }

    return ans;
}
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Can you explain why we do k-- at the start? Thank you in advance!

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

        I'm not sure which implementation you're referring to, but probably because you want the number to be 0-indexed, but the input format is 1-indexed.

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

          Sorry for the vague question, I was referring to your submission. Thank you nonetheless. Love your streams btw, hope you do more in the future.

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

            Ah, okay, then yes, it's because of the indexing thing I mentioned. I generally prefer zero-indexing, so I almost always translate things while performing the input to avoid issues later.

            As for why it works in this problem, I think you should just trace through exactly how the code/logic works, and then you'll basically see that you reach the wrong answer if you don't do k-- (but I think you would get the right answer if you didn't do k-- and you replaced count_if_a <= k with <). So basically it's "because it gets the right answer", haha.

            (My submission for reference/convenience to anyone else reading this.)

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

Auto comment: topic has been updated by dush1729 (previous revision, new revision, compare).

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

BRUUH, how didn't I think of binarysearching for the number of occurences. :(

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

For problem E,

"So we can use binary search in depth vector above at given depth d to find how many values it has from start_time[u] to end_time[u]."

How this will work?

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

    Because we are adding start time of every node in the depth vector, it help us find count of how many values are there from start_time[u] to end_time[u] at depth d.

    Don't know if this will help, but here's a what I made during contest.

    Image
    → Reply