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/CAMAzhzjYQJW8WtHfJUm1hcWu%3DhOo_Gj78QCm4sMmW4jh5%3Drm-A%40mail.gmail.com.
