Въпрос от google интервю


1

Вчера попаднах на една от многото логически задачи давани по интервюта :
Имаме 25  коня с различна бързина. Ако можем да състезаваме по 5 наведнъж ,с   колко най- малко състезания можем да определим първите 3, при условие че можем да следим само кой е по бърз от кой и резултатите им са постоянни?

Не стигнах много по- далеч от това, че за 1вия трябват 6 състезания.  Някой знае ли как се решават тези задачи в общия случай > При n коня , с колко най-малко състезания можем да определим първите x, ако можем да състезаваме по m наведнъж ? Ако няма формула, една програма където я решава как би изглеждала?




Отговори



1

Хм, яка задача.Първото, което ми хрумва е, подреждаш ги в 5 групи - 5 състезания, в шестото състезание взимаш първенците от всяка група, следващата петица е от 4-терите победени коня и втория от групата на победителя, и пак следващата петица е от 4-те победени коня и следващият поред от групата на новия победител,значи общо 8 състезания.




0

Резултатите от първите 5 състезания са:

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

21 22 23 24 25

 От тях взимаме коне с номера

1 6 11 16 21 (като най-бързи от групите си)

Да речем че кон номер 11 е най-бърз, то следващата ни петица е

1 6 12 16 21

и да речем, че кон 6 е бил най-бърз

то полседното ни състезание е

1 7 12 16 21

и ако тука се окаже примерно, че кон номер 1 е бил най-бърз

то имаме 11,6,1 крайно класиране за първите три коня от общо 8 състезания

динамично оптимиране му се вика тва :)




0
5-та задача от C# 2, вечерта на 6-ти, е общо взето това. Така и не я дореших...

от ivo.paunov (991 точки)


0

Трябва да организираш пряка елиминация. Тъй като не можеш да си сигурен дали най-бързите N няма да се окажат в една група, то от всяка група трябва да оставяш поне толкова, колкото ти е заданието.

В конкретния случай правиш 5 групи по 5 коня, като от всяка група оставяш първите 3. Така винаги 3-те най-бързи ще са там, дори и да са в една група.

След първия рунд ти остават 15 коня. Правиш нови 3 групи от 5 коня, от които след състезанието оставяш по 3. Така след втория рунд ще имаш 9.

Трети рунд ще се състои от 2 групи - 5 + 4. Остават ти 6 победителя

Четвърти рунд вече ще е малко по-особен... ще пуснеш само 5 коня в една група и ще вземеш 3-та най-бързи. Може и с 4 + 2.

И в петия рунд ще сложиш 3-та победители плюс онзи който не е участвал (или онези два ако си на варианта 4+2). Първите трима ще са гарантирано най-бързите.

П.С. Хммм... странно... В Интернет се твърди, че трябват поне 7 състезания, а аз не виждам пропуск в моята логика... Някой да вижда къде бъркам? Или да си пускам CV-то за Гугъл направо? :)


от JulianG (5316 точки)


0
за състезание се смята 5 коня, ти само в първи рунд имаш 5 състезания


1

Уф че съм тъп... Рундовете са 5, обаче състезанията са 5 + 3 + 2 + 2 + 1 = 13... :(

Ето тук има добро обяснение как се решава задачата:

http://www.glassdoor.com/Interview/25-horses-5-race-tracks-How-many-races-you-have-to-run-to-select-top-5-horses-QTN_136645.htm

Накратко: пускат се 5 групи по 5 коня и след това се пуска 1 група с победителите от 5-те първи групи. Въз основа на класирането в това 6-то състезание се елиминират голяма част от участниците, които са били на 2-ро и 3-то място. Така в 7-то състезание могат да участват само 5 коня, от които се взимат 2-та най-бързи. Третия е първенеца от 6-та гонка -той е най-бързия и това е установено още в 6-то състезание.


от JulianG (5316 точки)



1

Според мен след първите 5 състезания в случай, че групите де подредят по сл. начин:

к1, к2, к3, к4, к5

к6, к7, к8, к9, к10

к11 к12 к13 к14 к15

к16 к17 к18 к19 к20

к21 к22 к23 к24 к25  -  на първия ред са най-силните от съответната група, а на последния ред са най-слабите (състезателните групи са подредени по колони)

ще се отделят: к1, к2, к3, к4, к5 като най-бързи в съответната група. Да предположим, че те са подредени и тук по големина (к1>к2>к3>к4>к5)

След състезание между тях к1 е на първо място - до тук станаха 6 състезания.

Да предположим, че групите са подредени и тук по големина (к1>к2>к3>к4>к5)

Тогава само к6 би могло да бъде по-голямо от к2 и само к6, к7, к11 и к12 могат да бъдат по-големи от к3.

Следващото (последно) състезание ще бъде между к2 к3 к6 к7 к11 к12 и от него окончателно се определят вторият и третият победител.

Следователно, необходимият брой състезания е седем :)


от ellapt (6303 точки)


0

Май се получават едни квадратни подматрици от от [0,0] до [3,3] -ти ред (според изискването за първо, второ и трето място), които се намират отляво на съответния победител при посочената по-горе подредба (ако колоните са сортирани според първия ред).

Добавям: За такъв брой състезатели не си струва да се прави рекурсия. За по-голям брой и по-големи групи май си струва :)


от ellapt (6303 точки)

1

ще бъде между к2 к3 к6 к7 к11 к12

--------------------------------------

всъщност без К12 че станаха 6. Иначе съм напълно съгласен с тази логика.





0

След като видях linka от Julian ето как би изглеждал 1 алгоритъм:

705 коня, по 7 коня max на състезание , търсим първите 3.

Стъпка 1 винаги е да намерим 1вия.

Фаза 1 : Разделяме на групи по 7 и състезаваме 705/7 = 101 първенци

Фаза 2: 101/7 = 14 и 3/7; 15 състезания и 15 първенци

Фаза 3: 15/7 =  2 и 1/7; 3 състезания 3 първенци

Фаза 4: Състезаваме последните 3ма;

Вече имаме победител сега търсим всички кандидати за 2и 3то място.

Те са : 

1. 2рия кон от 4та фаза и всички коне в неговата група от всички фази(1,2,3) директно след него.(Ако се търсеха първите 4 , то тогава всички 2 след него и т.н). Това са 3 коня.(Ако в фаза 3 се е паднал сам шанс:) , не виждам причина да ги делим по равно 5/5/5)

2. 3тия кон от фаза 4

3. 2рия и 3тия кон след 1вия  във 1вите 3 фази. 2+2+2 = 8коня(пак при условие че винаги е бил в групите по 7).

Следователно общия брой кандидати е 8+3+1+1 = 13; Връщаме се на точка 1  и търсим първенеца(2рия). Разделяме на 2групи 6 и 7 и взимаме пърите 2ма от всяка(Ако се търсеха 1вите 4 щяхме да взем последните 3 и т.н). Последно състезание на последните 4 и имаме 2ри и 3ти(1ви и втори в състезанието).

Общ брой състезания 101 + 15 +3 +1 + 2+1 = 123;

Забележка:

1.Винаги делим конете, така че в последната група да има възможно най-малко(остатъка), тъй като ако например във фаза 3 ги бяхме разделили 5/5/5, то винаги ще имаме някой след 2рия, а при 7/7/1, ако 2рия е от сам > няма кон. Тук няма значение , тъй като 4 или 5 коня е под лимита 7, но при други числа може да даде отклонение с някое и друго състезание.

2. Ако потенциалните кандидати за 2и 3то място бяха повече от 7, то тогава се връщаме на стъпка 1 и делим докато не останат по малко от 7.

Ами това е:), някой ако има по точен алгоритъм да сподели.


от snippet (7 точки)


1

Да, но е възможно вторият и/или третият от 101-те първенци да е по-слаб от някой втори/трети на групите от първото състезание :)


от ellapt (6303 точки)

0
Да сега погледнах бях пропуснал ,че може д е 2ри и 3ти след 1вия. Относно коментара може, но трябва да е бил в групата на 1вия. Иначе щеше да победи.

от snippet (7 точки)


0
Пичове, прочетете пак условието : Пита се - с   колко най- малко състезания можем да определим първите 3, при условие че можем да следим само кой е по бърз от кой и резултатите им са постоянни?

Като никъде не се казва, че от всяко състезание се взимат първите 3. Като заблуждаващото и то е ключово в случая, че можем да следим само кой е по бърз от кой и [резултатите им са постоянно]

Щом се търси с колко най малко - правилата ги определяме ние с цел оптимизация на състезанията - Т.е извода е не да се изпада в разсъждения, а това е хипер елементарен въпрос.

Обяснение: Най малко гонки може да се направият 6 - > защото от първите 5 гонки с по 5 коня (25 коня общо) се вземе само победителя, защото резултатите са постоянни например кон 1 е по бърз от кон 2,3,4,5 и се взима кон 1 / по същата логика и другите се взимат/ и ти остават 5 коня, които са точно за 1 гонка. От тях ако искаш да вземеш първите три да ги наградиш ги вземи, ако искаш да вземеш 1 вия само и него вземи ако искаш всичките и тях награди. Търсят се гонките ... Затова мисля, че отговора е 6 независимо какво пише в интернет, Щом изрично не е казано, че на всяка гонка има класиране, то правилата се определят от теб не може да гадаеш и да си измисляш правила, как взимаш първите 3, после ти оставали 15 коня / от 1,2,3 място и т.н 


от a.sideriss (450 точки)


0

Ако втория (или третия) кон от някоя гонка е по-бърз от първия от друга, няма да си избрал трите най-бързи.

Пример:

Най-бързите от всяка група:        12км/ч 15км/ч 25км/ч 30км/ч 100км/ч

Втория най-бърз от всяка група: 6км/ч     6км/ч     6км/ч    10км/ч   30км/ч

...........................................................

другите нямат особено значение.


от nasko717 (180 точки)


1

За първите 5 състезания е ясно - 5 групи /А, Б, В, Г, Д/ по 5 коня и имаме класиране в групите.

6 състезание - победителите от петте групи. Да предположим, че победителят на победителите е от група А, вторият от група Б.

От класирането в 6-тото състезание можем да отделим победителя /очевидно той е най-бърз от всички коне/ и да махнем конете на 4 и 5 място, защото нямат шанс да са в крайната тройка. Остават конете на 2 и 3 място от състезанието на победителите.

За последния, 7-ми кръг към конете на 2 и 3 място от състезанието на победителите  добавяме конете на 2-ро и 3-то място от групата на победителя А /защото е възможно трите най-бързи да са били в една група/, добавяме и втория по бързина кон от групата на втория - Б.

Така след края на 7-мото състезание се определя второ - трето място в крайното класиране.




1

Ако нарисуваме една матрица ще стане по-ясно защо със 7 състезания се намират първите 3 коня:

horse races

Първо се правят състезания по редовете на матрицата, като от всяко състезание се взима първият кон, който да участва в шестото състезание.

От шестото състезание се определя кой е шампиона, но също така се следи кои коне завършват втори и трети в него.

Вторият кон в крайното класиране ще е или вторият кон от шестото състезание, или вторият кон от първото състезание, в което е участвал шампиона.

Третият кон в крайното класиране аналогично ще е един от следните три коня: третия в шестото състезание; втория в първото състезание на коня, който се е класирал втори на шестото състезание; третия от първото състезания на шампиона.

За 2ро място имаме два кандидата, за 3то място имаме три кандидата. Следователно можем да ги пуснем в едно последно 7мо състезание за 2ро и 3то място.