Unoffical Announcment of Atcoder HHKB Programming Contest 2020

4 года назад, # ^ |

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

→ Ответить

hardy_9795

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

Bojack_human

4 года назад, # |

how to solve E ?

→ Ответить

dush1729

4 года назад, # ^ |

← Rev. 2 →

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

→ Ответить

4 года назад, # |

← Rev. 2 →

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

→ Ответить

mike1729

4 года назад, # ^ |

← Rev. 2 →

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

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

pritishn

4 года назад, # |

+10

How to solve D?

→ Ответить

4 года назад, # ^ |

-27

I used inclusion exclusion and combinatorics.

→ Ответить

Nurss

4 года назад, # ^ |

← Rev. 3 →

→ Ответить

pulsatio

4 года назад, # |

+14

how to solve D?

→ Ответить

4 года назад, # |

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?

→ Ответить

4 года назад, # ^ |

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

→ Ответить

nishant403

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

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

→ Ответить

nishant403

4 года назад, # ^ |

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.

→ Ответить

4 года назад, # ^ |

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

→ Ответить

Samarth12

4 года назад, # ^ |

← Rev. 2 →

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.

→ Ответить

mike1729

4 года назад, # ^ |

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

→ Ответить

Samarth12

4 года назад, # ^ |

← Rev. 2 →

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

→ Ответить

Savior-of-Cross

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

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

→ Ответить

Everule

4 года назад, # ^ |

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

→ Ответить

gdgzoi471

4 года назад, # ^ |

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

→ Ответить

Savior-of-Cross

4 года назад, # ^ |

It is, but it has the constant factor low enough to AC.

→ Ответить

dush1729

4 года назад, # |

+12

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. :(

→ Ответить

iabhishek15

4 года назад, # ^ |

same here.

→ Ответить

bestin_1

4 года назад, # |

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

→ Ответить

akash19061

4 года назад, # |

→ Ответить

The_blue_penguin

4 года назад, # |

Can anyone share the approach for solving D and E.

→ Ответить

4 года назад, # |

← Rev. 2 →

for C, we can use DSU

source code

→ Ответить

Samarth12

4 года назад, # ^ |

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.

→ Ответить

WitchOfTruth

4 года назад, # ^ |

← Rev. 2 →

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

→ Ответить

4 года назад, # |

← Rev. 2 →

-8

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

→ Ответить

AM_I_Learning

4 года назад, # ^ |

Idea?

→ Ответить

4 года назад, # ^ |

Can you please explain your approach?

→ Ответить

4 года назад, # |

← Rev. 2 →

for E, it's also exclusive

source code

→ Ответить

jiteshrao

4 года назад, # ^ |

Can you please use spoilers or links to show your code? Thanks!

→ Ответить

4 года назад, # ^ |

i'm very sorry, because i'm in a hurry then.

→ Ответить

jiteshrao

4 года назад, # ^ |

No problem :)

→ Ответить

grindharderthantheyparty

4 года назад, # |

m(at)ths(coder)

→ Ответить

pranshukas

4 года назад, # |

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

→ Ответить

Suri429

4 года назад, # ^ |

+11

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

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

→ Ответить

Suri429

4 года назад, # |

+35

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

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

→ Ответить

hetp111

4 года назад, # ^ |

← Rev. 2 →

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

Edit: I figured it out.

→ Ответить

hunxuewangzi

4 года назад, # ^ |

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

→ Ответить

hetp111

4 года назад, # ^ |

← Rev. 3 →

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.

→ Ответить

4 года назад, # ^ |

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

→ Ответить

hunxuewangzi

4 года назад, # ^ |

← Rev. 2 →

Thanks，i understand it！

→ Ответить

TheBest

4 года назад, # ^ |

go out to practice

→ Ответить

dush1729

4 года назад, # ^ |

+11

→ Ответить

4 года назад, # |

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

→ Ответить

abhirock753

4 года назад, # ^ |

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

→ Ответить