Kaleab_Asfaw's blog

Unoffical Announcment of Atcoder HHKB Programming Contest 2020
By Kaleab_Asfaw, history, 4 years ago, In English

Hi!

Solution Discussion for HHKB Programming Contest 2020

I created this blog, because I couldn't find an announcement in Codeforces (where usually there would be) and want to have a discussion about the solutions to the problems after the contest ended.

The contest is being held on Atcoder. Link to the problems in the contest: https://atcoder.jp/contests/hhkb2020/tasks.

Hope this will help people who didn't get a solution for problems.

Sorry for the bad English.

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

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

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

Summary for participant like noob like me : Solve ABC fast and take rest the remain time !!

How to solve D and E ???

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

    A hint for E — For each tile, consider how many configurations will light it up

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

      Do you mean calculating the number of tiles in each direction that will light up? Or did I made a mistake in understanding.

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

        I mean, for a given tidy tile, I want to find out, in how many configurations this is lit up? For instance, in the second sample, there are 12 configurations that light up the top left of the grid (I'll leave it to you to figure out why). If you do that for every single tile on the grid and sum them up, you will get the answer.

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

how to solve E ?

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

    For each tidy cell, find from how many tidy cells it can be lit. It can be lit up by continous line tidy cells in all 4 directions. Lets say the count of such cells is lit and total number of tidy cells is tidy.

    Then that particular tidy cell, can be lit up in2 ^ tidy - 2 ^ (tidy - lit) combinations.

    Submission

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

IDK why I got wrong answer in F. I derived the result using integration. Like for each continuous interval having bounds as discrete points, I do integral of V dP. Any ideas?

V : Value assumed by the maximum P : Probability function for that range for all the overlapping intervals

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

    how did you found expectation, i was getting 117 as my answer for second sample. How should one calculate expectations in these type of problems??

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

      I just noticed that in a bounded range, say for Value V, my change in probability function is contributed by the value that I just assumed.

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

How to solve D?

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

how to solve D?

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

How do you go about doing F? The way I tried is $$$P({x_1,x_2...} < z) = \prod \frac{z-l_i}{r_i-l_i}$$$ and the denominator removes the rightmost term of our answer. But the integration yields a polynomial I can't calculate (and I somehow have to handle that the probability maxes out at 1). If this is the right direction, how do you proceed from here?

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

    To overcome this, I thought about fixing Li's but idk if this is right

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

    Can you tell if this is true,

    Expected value when there are N ranges, all having same range[L,R] is : L + (R-L)*(N/(N+1))

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

      I think that's true if all assume same probability function?

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

        Can we do it like this then ? (just assuming R_min >= L_max for ease)

        sort all the pairs by R[i].

        consider these N ranges now :

        L_max to R[0] R[1] to R[2] R[2] to R[3] ... R[N-2] to R[N-1]

        For each range, we find contribution of that range in the expected value, where we consider (N — i) i.i.d. RVs.

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

          Yeah, I was doing the same thing, but got WA with it :(

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

    Yes this is the right direction, I was not getting correct but to multiply this you need to do FFT(n*log^2(n)). This gives you a polynomial of the form

    $$$a_0 + a_1*z+a_2*z^2....+a_n*z^n$$$

    . Then you need to differentiate this, multiply by z and then integrate it in suitable range. I will try to get AC and then share the code. Hoping this helps.

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

      so what should be the range of integration? min(Li) to max(Ri) ryt??

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

        No, consider the ranges [1, 3] and [3, 5]. Note that [1, 3] is of no use.So here we use the range [3, 5] only. But now consider the ranges:[1, 4], [2, 6], [3, 9]. You can't simply consider the range [3, 9] since in [5, 9], the first range has no contribution. So you need to split between points:

        $$$L_{max}, R_1, R_2,....R_{max}$$$

        and delete ranges which are of no use(division of polynomials).

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

    Sort all L and R to find the "fundamental intervals" [fL, fR]. We'll assume the maximum is on each of these interval and calculate the expected values.

    Fix an interval [fL, fR].

    If fR <= L_i for some i, there's 0 probability that the max lies in the interval [fL, fR], so just skip.

    Otherwise, let A_k be the probability that k of these variables lies in the interval [fL, fR]. The generating function F(X)=A_0 + A_1 X + A_2 X^2... can be found by multiplying following polynomials for each variable i.

    If fL >= R_i, simply multiply the constant polynomial 1 to the polynomial. Otherwise, multiply (fL - L_i) / (R_i - L_i) + (fR - fL) / (R_i - L_i) X to the polynomial.

    After we've obtained the generating function, we can recover the answer using the fact that if we have N random variables with uniform distribution on [L, R], the expected maximum value is (L + R * N) / (N + 1).

    Code

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

      Thanks! I have some reading to do to understand how all this works

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

      You don't need that fact. Let $$$P(x)$$$ be the probability of $$$x$$$. We need to find

      $$$\displaystyle\int_{0}^{\max(R)} xP(x) dx$$$

      This can be rewritten as

      $$$\displaystyle\int_{0}^{\max(R)} P(>x)dx = \int_{0}^{\max(R)} 1-P(<x)dx $$$

      $P(<x)$ is the same. We have $$$\displaystyle\prod_{x \le R_i} \dfrac{x - L_i}{R_i - L_i}$$$. We know that the polynomial changes when $$$x = R_i$$$. Now we iterate in decreasing order of $$$R$$$, as in sort the ranges in decreasing order of $$$R$$$. Then we get

      $$$\displaystyle\sum_{R_{i+1} \ge max(L_i)}\int_{R_{i+1}}^{R_i} 1 - \prod_{j \le i} \dfrac{x - L_j}{R_j - L_j}$$$. There is still some part missing, which is till $$$max(L)$$$. That can be added seperately, and we get $$$O(n^2)$$$.

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

      I'm confused about the time complexity. It seems that it's $$$O(N^3)$$$?

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

How to solve D? I tried to solving it by finding in how many cases squares will overlap and subtract that from (n - a + 1) * (n - a + 1) * (n - b + 1) * (n - b + 1). But finding formula was too hard for me. :(

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

when you get AC on E 5 sec after contest because your hands were shaking too much while submitting lol.

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

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

Can anyone share the approach for solving D and E.

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

for C, we can use DSU

source code

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

    Ok, but a simple idea is to insert first 200005 numbers in a set and for each 'i', remove the element from the set and output the smallest element.

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

      Or you can mark visited elements in a vector and increment the index until the next unvisited using the fact that the answer is always a non-decreasing sequence

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

for D, we use exclusive.

the total number can be easily given by sqr(n-a+1) * sqr(n-b+1), then we subtract the number in three different overlapping cases.

source code

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

for E, it's also exclusive

source code

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

m(at)ths(coder)

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

Can Anyone Share the Logic/Hint (Not the Code) to Approach D and E?

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

    E was easier than D, at least to me. A quick explaination Let's try to find for each '.', in how many cases it will contribute.

    Spoiler

    We can also say, left+right and up+down information is also good enough, we don't want seperate left, right and so on. How do we find this information for each '.'

    Spoiler

    For right most elements or element left to '#' we have correct information, but for rest, we need to do something.

    Spoiler

    Repeat same for top-bottom. How to use the information we have stored ?

    Spoiler
    Spoiler

    Take sum over all '.' . That's your answer

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

Here's one of the solution to D.

Let us find the number of ways such that there is no overlap in x-axis. Let us put A to the left and B to the right, such that on x-axis, now we have N-(A+B) blank space. Can you guess the number of ways to distribute these blank spaces between A and B ?

Spoiler

Now that x-axis is covered, what about y-axis ?

Spoiler

We fixed left and right for A and B, but it can be other way too. So multiply above calculation with 2.

We can do a similar thing in Y-axis, and since everything remains same, we can multiply the above calculation with 2

Are we repeating any cases ?

Spoiler
Spoiler

We have actually done the hard work already, the cases are

Spoiler

Last up is, how to find number of integral solutions to a+b+c = n

Spoiler

To wrap up 

 p = N - (A + B)
 res = C(p+2,2) * (N-A+1) * (N-B+1)
 res = res*2 
 res = res*2 
 
 res2 = C(p+2,2)*C(p+2,2)*4

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

    Where there is no overlap in x-axis and y-axis. Can you please elaborate ? Thank you.

    Edit: I figured it out.

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

      Could you please tell me how to sovle your problem ? thanks.

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

        This might help...

        Now we multiply by 2 because we can flip the image and exchange the positions of A and B.

        Now again multiply by 2 because we can rotate the image by 90 degrees for a new configuration.

        Now there are cases when we are overcounting. Example: when A is on top right of B, now this is already counted again in a case when the image is rotated. So we need to subtract these kind of cases.

        How to find those cases ? It is explained in the OP's comment.

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

          Can you please explain what are we over counting and why is that the case? And how do we tackle it?

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

          Thanks，i understand it！

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

        go out to practice

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

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

Can someone please explain how to solve D?

Seems like a straight forward solution in which we subtract the overlapping cases. But how does it work, I am not able to wrap my head around it? Can someone please explain?

Submission link : https://atcoder.jp/contests/hhkb2020/submissions/17295052

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

    Okay, I think I can explain... One thing to notice that if two square overlaps then there length and breadth of one rectangle must cross the breadth and length of the other rectangle so we need to discard those and we should count only the where the dimension don't overlap as mentioned i.e solution of the integral equation above which is shows the conditions of non-overlapping squares and subtract those which were counted twice due to rotations if u need further explanation u can ask

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

      Thank you. I understand the integral equation above which calculates the conditions of non-overlapping squares. Can you please elaborate how do we calculate cases that were double counted (as in what to subtract) and how it works? (As in how do we account for repeating cases?)

      → Reply