arkirakosyan
BAN USERtatura I think you don't need 13th race. By 11th race you can determine 2,3,4 places by choosing set of horses which contains 2,3,4(you can do it so I don't detail it :)) so first 3 places would be our 2,3,4 places and then by the 12th race you can determine 5th and 6th places. So totaly by the 12 races 6 best hources can be choosed.
- arkirakosyan May 12, 2011Yes, I agree it would be faster ;)
- arkirakosyan May 05, 2011yes algo will run O(logn) if there is 1 ocurance the worst case is O(n). but I don't think it is posible to find O(logn) for the worst case
- arkirakosyan May 04, 2011<pre lang="" line="1" title="CodeMonkey8647" class="run-this">public static int FindOccurance(int[] arr, int n, int left, int right)
{
if(left > right) return 0;
int p = (left + right) / 2;
if (arr[p] > n)
return FindOccurance(arr, n, left, p - 1);
if(arr[p] < n)
return FindOccurance(arr, n, p + 1, right);
return 1 + ((p > left) ? FindOccurance(arr, n, left, p - 1) : 0) +((p < right) ? FindOccurance(arr, n, p + 1, right) : 0); }
int[] arr = { 1,2,3,4,4,4,4,4,5,6,7,8,9,10 };
Console.WriteLine(FindOccurance(arr, 4, 0, arr.Length - 1));
</pre><pre title="CodeMonkey8647" input="yes">
</pre>
I am sorry 5 and 6 places cannot be determined by 1 race, you are right 13 races needs :)
- arkirakosyan May 12, 2011