On Sun, May 8, 2011 at 2:17 PM, Josh <[email protected]> wrote: > This doesn't make sense too me. It seems like the case of sorting some > of the numbers with a hit is not accounted for. > > For example, with 3 numbers to sort, there is a 1/6 chance it is > sorted on the first shot. And a 3/6 chance exactly one is sorted. > If exactly 1 is sorted, then there is a 1/2 chance of sorting the > rest. > So doesn't that mean the chance of sorting it is 1/6 + (3/6 * 1/2)?
Remember you need to look at the expected value. If you want to see it with numbers it goes something like this: Lets assume that the expected value of sorting two elements is 2. This comes from the example. So to sort three elements you have x(a)= (Expected number of hits to sort A) 1/6 * 1 (i.e: Chance of sorting in one hit) + 3/6 * (1+2) (i.e: first hit sorts 1 element + expected value of sorting 2 elements) + 2/6 * (1+x(a)) (i.e: Nothing gets sorted but you made a hit) x(a)=1/6+9/6+2/6+2/6*x(a) 2/3*x(a)=2 x(a)=3 > > > > On May 8, 4:31 am, "Alfonso J. Ramos" <[email protected]> wrote: >> ... >> >> If you have 2 elements, then there is 1/2 chance of getting them right >> [in one hit], and 1/2 of not. Of those last 1/2 you have 1/2 (that is >> a 1/4 of the whole) to get it right [in two hits] and 1/2 (that's the >> other 1/4 of the whole) not. Of that 1/4 you have 1/2 (that is a 1/8 >> of the whole) to get it right [in three hits] and the other 1/2 (that >> is 1/8 of the whole) not. >> >> So, you do the pondered sum of the N first iterations and you will see >> that it converges to 2 (that's the average number of hits). >> See: >> first iteration = 1/2 * 1 hit = 1/2 hits >> second iteration = 1/2 * 1 hit + 1/4 * 2 hits = 1 hit >> third iteration = 1/2 * 1 hit + 1/4 * 2 hits + 1/8 * 3 hits = 1 hit + 3/8 >> hits >> fourth iteration = 1/2 * 1 hit + 1/4 * 2 hits + 1/8 * 3 hits + 1/16 * >> 4 hits = 1 hit + 5/8 hits >> >> No finite number of iterations is right because they only get as close >> to cover all the posibilities, but you see the form: sum (i/2^i), you >> may find that it converges to 2. I did ask wolfram alpha. >> >> Now... >> >> if you have 3 elements, then there is a 1/6 chance of getting them >> right [in one hit], 3/6 of getting one element right, since Goro holds >> those that are right, you can take this as a two element escenario so >> it becomes a 3/6 chance of getting it right in three hits (the one he >> did to the three elements plus the two average for the two element >> case). And lastly the other 2/6 you get nothing right. Of those 2/6... >> well you get the idea, when you do the pondered sum of the N first >> iterations and you will see that it converges to 3 (that's the average >> number of hits). I had to use excel for that. >> >> I did trust that that would work for the rest of cases, it took me a >> long time... bad for me. >> >> You may be wondering, how comes the pondered sum is the average? well, >> the classic average is the sum of the values over the total: [(A + B + >> C) / Total], you can also express it like this: [(A / Total) + (B / >> Total) + (C / Total)]. In a grouped average you multiply the values by >> the number of times they appear [(A * timesA / Total) + (B * timesB / >> Total) + (C * timesC / Total)]. >> >> In our case the total is 1 (that is the 100% of cases) the number of >> times it appears is the probability and the value is the number of >> cases. So you see that I don't need to divide by 1 as it gives me the >> same value... so as it turns out the pondered sum of the number of >> hits by it's probability is the group average of the number of hits. >> >> 2011/5/8 Lei Huang <[email protected]>: >> >> >> >> >> >> >> >> > Including the 2-elements array. >> > There is 50% possibility that no elements will land in its position, >> > and 50% possibility both of the elements are in the right position. >> > So the expected is 50% * 2 + 50% * 0 = 1 >> >> > 2011/5/8 Jin Mingjian <[email protected]>: >> >> "So we can expect that in any random permutation, one element will land in >> >> its correct sorted pos." except for the 2-elements array? >> >> >> On Sun, May 8, 2011 at 3:20 PM, rajatag12 <[email protected]> wrote: >> >> >>> Yes. First thing to see is that Goro would never hit the table with open >> >>> elements that *could not* land in their correct position for any >> >>> permutation. Once it is understood, it will be easy to see that solving >> >>> the >> >>> prob for each permutation cycle is an independent one. Answering the main >> >>> question, observe that each element in a sequence of N elements appears >> >>> in >> >>> its correct place (N-1)! times out of the N! permutations. So we can >> >>> expect >> >>> that in any random permutation, one element will land in its correct >> >>> sorted >> >>> pos. So after each hit, Goro should include the last element placed >> >>> correctly in his set of elements to hold before he hits. Hence, expected >> >>> number of hits = n. >> >>> Formal proof has already been provided above. >> >> >>> On Sunday, May 8, 2011 7:22:39 AM UTC+5:30, Balajiganapathi wrote: >> >> >>>> I meant: Is n the expected number of hits to sort a n-element *cycle*. >> >> >>> -- >> >>> You received this message because you are subscribed to the Google Groups >> >>> "google-codejam" 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 >> >>>http://groups.google.com/group/google-code?hl=en. >> >> >> -- >> >> You received this message because you are subscribed to the Google Groups >> >> "google-codejam" 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 >> >>http://groups.google.com/group/google-code?hl=en. >> >> > -- >> > You received this message because you are subscribed to the Google Groups >> > "google-codejam" 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 >> > athttp://groups.google.com/group/google-code?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "google-codejam" 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 > http://groups.google.com/group/google-code?hl=en. > > -- You received this message because you are subscribed to the Google Groups "google-codejam" 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 http://groups.google.com/group/google-code?hl=en.
