Дърти Хари

johnfound

А бе, какво стана със задачата. Решихте ли я аналитично? Че ми е интересно да си проверя интуицията.

Ми аз имам решение с брут форс ама е 13 гонки и е гарантиран репродуцируем резилтат. Сигурно не е най-оптималния.

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

Остават 20.

Групираме ги в 4 групи, 4 гонки плюс една за подреждане плюс една за крайната елиминация

13.

Варианта на mergesort, които пусна Омега го прави за 10.

Добре бе, ето решение за 10 гонки, обяснено подробно:

Правим 5 гонки в 5 групи и така ги сортираме. След това вземаме първите от групите и правим от тях една група. Най-бързият е задължително в нея.

Правим гонка (6-та) и го разбираме кой е.

Вторият е или вторият от 6-тата гонка, или един от 4-мата втори в останалите 5 групи (без тази група от която идва 2) правим гонка от тези 5-ма и намираме вторият (7-ма).

Третият е или третият гонка 6, или вторият от гонка 7, или един от тримата поредни от голямата група (без групите от които идват първите двама).

И така нататък, общо 10 гонки.

За излъчване на N най-бързи (N>0), от общо X бегача, трябват X/N+N гонки. (но това не е точно )

|

Дърти Хари

johnfound

А бе, какво стана със задачата. Решихте ли я аналитично? Че ми е интересно да си проверя интуицията.

Ми аз имам решение с брут форс ама е 13 гонки и е гарантиран репродуцируем резилтат. Сигурно не е най-оптималния.

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

Остават 20.

Групираме ги в 4 групи, 4 гонки плюс една за подреждане плюс една за крайната елиминация

13.

Варианта на mergesort, които пусна Омега го прави за 10.

Кравар, глей си там калемчетата с ученическите проекти и не ми хвърляй киййворди.

Също така щом те е срам да си пуснеш простотиите под собствено име, поне измисли малко по-интересен чорапо акаунт. My link

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

Дърти Хари

|

Дърти Хари

johnfound

А бе, какво стана със задачата. Решихте ли я аналитично? Че ми е интересно да си проверя интуицията.

Ми аз имам решение с брут форс ама е 13 гонки и е гарантиран репродуцируем резилтат. Сигурно не е най-оптималния.

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

Остават 20.

Групираме ги в 4 групи, 4 гонки плюс една за подреждане плюс една за крайната елиминация

13.

Варианта на mergesort, които пусна Омега го прави за 10.

Кравар, глей си там калемчетата с ученическите проекти и не ми хвърляй киййворди.

Също така щом те е срам да си пуснеш простотиите под собствено име, поне измисли малко по-интересен чорапо акаунт. My link

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

Абе, говедо, ти програмист ли си? Знаеш ли как работи merge sort? Решението на Омегата е прецизно и ти дава първите 5 винаги с 10 сравнения.

johnfound

Добре бе, ето решение за 10 гонки, обяснено подробно:

Правим 5 гонки в 5 групи и така ги сортираме. След това вземаме първите от групите и правим от тях една група. Най-бързият е задължително в нея.

Правим гонка (6-та) и го разбираме кой е.

Вторият е или вторият от 6-тата гонка, или един от 4-мата втори в останалите 5 групи (без тази група от която идва 2) правим гонка от тези 5-ма и намираме вторият (7-ма).

Третият е или третият гонка 6, или вторият от гонка 7, или един от тримата поредни от голямата група (без групите от които идват първите двама).

И така нататък, общо 10 гонки.

За излъчване на N най-бързи (N>0), от общо X бегача, трябват X/N+N гонки. (но това не е точно )

Обяснението на Омега е много по-разбираемо. След първите 5 гонки имаш 5 групи.

От там нататък съвсем унифицирано взимаш най-бързия останал от всяка от 5-те групи и ги сравняваш. Махаш най-бързия и на негово място слагаш останалият най-бърз от същатата група.

Елементарен merge sort. Въпросът е дали може с по-малко сравнения от това.

johnfound

Третият е или третият гонка 6, или вторият от гонка 7, или един от тримата поредни от голямата група (без групите от които идват първите двама).

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

Дон Реба

johnfound

Третият е или третият гонка 6, или вторият от гонка 7, или един от тримата поредни от голямата група (без групите от които идват първите двама).

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

Чакай да измисля по-лесно обяснение:

1. Строяваме всички в каре 5х5

2. Правим гонки във всяка колона и я подреждаме така че най-бързите да са най-отпред, а най-бавните най-отзат (5 гонки общо)

3. Първият ред, съдържа най-бързия от всички в строя.

4. Провеждаме гонка на хората в първият ред, намираме най-бързия и го махаме от строя.

5. Неговата колона прави крачка напред, за да запълни дупката.

6. Ако има празна колона, приключваме. Ако няма goto 3

johnfound

Дон Реба

johnfound

Третият е или третият гонка 6, или вторият от гонка 7, или един от тримата поредни от голямата група (без групите от които идват първите двама).

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

Чакай да измисля по-лесно обяснение:

1. Строяваме всички в каре 5х5

2. Правим гонки във всяка колона и я подреждаме така че най-бързите да са най-отпред, а най-бавните най-отзат (5 гонки общо)

3. Първият ред, съдържа най-бързия от всички в строя.

4. Провеждаме гонка на хората в първият ред, намираме най-бързия и го махаме от строя.

5. Неговата колона прави крачка напред, за да запълни дупката.

6. Ако има празна колона, приключваме. Ако няма goto 3

тоя дето прави крачка напред може да е всъщност деветия по бързина.

Дърти Хари

тоя дето прави крачка напред може да е всъщност деветия по бързина.

Кой имаш предвид. Крачка напред прави цялата колона, а не един човек.

johnfound

Дон Реба

johnfound

Третият е или третият гонка 6, или вторият от гонка 7, или един от тримата поредни от голямата група (без групите от които идват първите двама).

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

Чакай да измисля по-лесно обяснение:

1. Строяваме всички в каре 5х5

2. Правим гонки във всяка колона и я подреждаме така че най-бързите да са най-отпред, а най-бавните най-отзат (5 гонки общо)

3. Първият ред, съдържа най-бързия от всички в строя.

4. Провеждаме гонка на хората в първият ред, намираме най-бързия и го махаме от строя.

5. Неговата колона прави крачка напред, за да запълни дупката.

6. Ако има празна колона, приключваме. Ако няма goto 3

Това е абсолютно същото като решението на Омега.

johnfound

Дърти Хари

тоя дето прави крачка напред може да е всъщност деветия по бързина.

Кой имаш предвид. Крачка напред прави цялата колона, а не един човек.

Втория от най-бързата група може да е най-бавния от останалите от първите две колони. Внася се случаен елемент в алгоритъма. Не е лош, но не ми харесва. И да това е мердж шита на краваря дето се крие зад омегата.

|

Това е абсолютно същото като решението на Омега.

Да напомням ли, че постнах отговора на първата страница на темата, при това със кратко, но по същество вярно описание на алгоритъма – интуицията си е интуиция, не можеш я пропи.

Дърти Хари

johnfound

Дърти Хари

тоя дето прави крачка напред може да е всъщност деветия по бързина.

Кой имаш предвид. Крачка напред прави цялата колона, а не един човек.

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

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

johnfound

|

Това е абсолютно същото като решението на Омега.

Да напомням ли, че постнах отговора на първата страница на темата, при това със кратко, но по същество вярно описание на алгоритъма – интуицията си е интуиция, не можеш я пропи.

Постнал си 10, не решение. Все още не знаем дали 10 е вярното число.

|

Постнал си 10, не решение. Все още не знаем дали 10 е вярното число.

Постнал съм и решение. И то отговаря на подробното описание, което направих преди малко. Ама ти нали не можеш да четеш с разбиране...

johnfound

|

Постнал си 10, не решение. Все още не знаем дали 10 е вярното число.

Постнал съм и решение. И то отговаря на подробното описание, което направих преди малко. Ама ти нали не можеш да четеш с разбиране...

Не. Решението ти е надбягване на всички редове и надбягване на всички колони. Това не е същото.

Дърти Хари

Внася се случаен елемент в алгоритъма. Не е лош, но не ми харесва. И да това е мердж шита на краваря дето се крие зад омегата.

Никакъв случаен елемент не се внася.

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

1	6	11	16	21
2	7	12	17	22
3	8	13	18	23
4	9	14	19	24
5	10	15	20	25

1 ясно че е сред 5 най-бързи, а като махнем всички за които има 5 по-бързи остава това:

1	6	11	16	21
2	7	12	
3	
4	
5	

Правим гонка между 3,4,5,7 и 11 (7 гонка) Ако 7 и 11 са първи и втори - най бързи са 1, 2, 6, 7 и 11. Поправка: Трябва да се направи гонка между 11 и 12 или между 2, 11, 7, 16 и 21 - значи пак 8 гонки

Ако първите трима са 3, 4 и 5 тогава трябва да се направи гонка с тях и 2 и 6. И да се вземат първите 4

Аналогично за останалите варианти може да се намери подходяща гонка за да ги доподреди.

Айде кажете къде бъркам :)

7 гонки. Първите 5 са ясни. Втората е с първенците и тогаз ни интересуват: 1А 1Б 1С 2А 2Б 3А

където (1-3)А са от групата на победителя, (1-2)Б са на втория, 1С е третия. Правим гонка с тез без победителя и сме ги намерили.

janbird

7 гонки. Първите 5 са ясни. Втората е с първенците и тогаз ни интересуват: 1А 1Б 1С 2А 2Б 3А

където (1-3)А са от групата на победителя, (1-2)Б са на втория, 1С е третия. Правим гонка с тез без победителя и сме ги намерили.

Не разбрах какво ще направиш, ако всички най-бързи коне са събрани в една от първите пет гонки (1-5А например)