Hi Joe, Thanks for the explanation, though I think it does not explain the issue raised by Ricola. Yes, we need to guarantee that "rare" high degrees are properly accounted for. I think that part of the official analysis is very good.
What Ricola was asking is about the details of the "importance sampling". As Ricola pointed out, the method described in the official analysis cannot produce a different outcome than what we get when we only use 'T' steps and estimate the average degree by simply using the average of our random sample. And we already agreed on that only using a random sample is not enough when the degree distribution is skewed towards low-degree nodes. Maybe the formula for the weights is incorrect? /dev/joe a következőt írta (2022. április 6., szerda, 2:27:14 UTC+2): > If, like me, you ignored walking and just teleported to a random sample of > the rooms, you would have found that you got a perfect score on the cases > in the local testing tool, but wrong answer on the real data. > > What the analysis is trying to say is that practically the only cases > where you will fail are where a very small number of rooms have a very high > degree, so few that you are likely to miss them in random sampling. > Suppose, for instance, that rooms 1, 2, and 3 are connected to every other > room (of 100,000). The other rooms are only connected to these three. When > you randomly sample 8% of the rooms, the most likely result is you miss all > these, think the average number of passages is 3, and estimate a result of > 150,000 passages. In fact, the average is about 6, and the number of > passages is near 300,000, and your estimate will be too low. What's worse, > if you hit one of the high-degree rooms during your random sample, your > 8000 rooms will have a total of about 124,000 passages and you will > estimate the average is 15 and submit an estimate of 750,000, which is too > high! The random sampling strategy is guaranteed to fail on this case! > > The sample doesn't make sense because the small number of rooms in it > isn't enough to throw off the estimate the way the example I gave does. > Hopefully that helps. Both strategies in the analysis are meant to help you > correctly solve cases like these, while not messing up your average for > normal cases. > > And, yes, I think this is rather in the dirty tricks department. They > probably put it here in the qualification round, where there were three > easy-to-medium problems and a fourth with an easy small case, so that > nobody would feel they unfairly lost a round because of it. Either that, or > it's a harbinger that all the rounds this year are going to have a problem > with even more bizarre edge cases than usual that we are going to have to > figure out. > > > > On Mon, Apr 4, 2022 at 10:46 AM Ricola <[email protected]> wrote: > >> In the analysis of Twisty Little Passages, In the "importance sampling >> solution" it is said that we could give a weight of A/B of the sample got >> with "W". But that sample value (degree) is B! So sample * weight gives B * >> A/B = A. >> >> 1. Why do we even need that sample as we don't even use its value, why >> should we even query the degree of R2? We don't even need to walk. >> 2. This just ends up that instead of querying K rooms, we query K/2 of >> them and count each degree twice. How is that even different than computing >> the average degree of K/2 rooms? >> If we look at the example given, 8/6 is the exact same result we get if >> we take the average degrees of the rooms we got with the T queries(R1 : 1, >> R2 : 1, R3 : 2 => avg 4/3) >> >> Either I misunderstood the explanation or something is wrong there, as >> implementing that solution gives wrong answer, which is normal as it's the >> same than using the average degree of the samples. >> >> -- >> -- You received this message because you are subscribed to the Google >> Groups Code Jam group. To post to this group, send email to >> [email protected]. To unsubscribe from this group, send email to >> [email protected]. For more options, visit this group at >> https://groups.google.com/d/forum/google-code?hl=en >> --- >> You received this message because you are subscribed to the Google Groups >> "Google Code Jam" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/google-code/6d8b752e-17e7-4eda-8049-25a38dfe9b46n%40googlegroups.com >> >> <https://groups.google.com/d/msgid/google-code/6d8b752e-17e7-4eda-8049-25a38dfe9b46n%40googlegroups.com?utm_medium=email&utm_source=footer> >> . >> > -- -- You received this message because you are subscribed to the Google Groups Code Jam group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at https://groups.google.com/d/forum/google-code?hl=en --- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/5a262986-716c-4ab0-824f-d760d851154en%40googlegroups.com.
