olymp.nstu.ru
Добро пожаловать, Гость! Чтобы использовать все возможности Вход или Регистрация.

Уведомление

Icon
Error
ACM 2019
Опции Просмотр
Предыдущая тема Следующая тема
Павел Хаустов
#1 Оставлено : 26 октября 2019 г. 15:03:04(UTC)
Ранг: Advanced Member

Группы: Coaches, Registered
Зарегистрирован: 10.10.2010(UTC)
Сообщений: 74
Мужчина
Откуда: Томск
Добрый день!

Скажите пожалуйста, как на тест №11 в задаче №10 (n = 6, k = 2) получить ответ 20 / 15? У нас получается только 18 / 15, если взвешивать две половины монет.
Вверх
Ветров Алексей
#2 Оставлено : 26 октября 2019 г. 15:26:22(UTC)
Ранг: Newbie

Группы: Registered
Зарегистрирован: 18.10.2013(UTC)
Сообщений: 1
Откуда: Томск
Ещё вопрос по поводу задачи 8. 16 тест выглядит так:
Цитата:
100 100
65 100 63 100
86 0 36 0


Видно, что тут есть окно с x=63 до x=65 ширины 2, в которое можно положить ковёр, значит ответ 2. Но ответ жюри 1.957

И ещё один случай, кажется, не учтённый жюри. Тест 10 выглядит так:

Цитата:
100 1
73 1 49 1
53 0 45 0


У жюри ответ 1.940, глазами явно видно окно с x=49 до x=53 ширины 4, а можно ещё лучше: направить ковёр так, чтобы он был перпендикулярен отрезку ((49, 1), (53, 0)), тогда его ширина будет равна sqrt(17)=4.123
Вверх
 |  Отредактировано пользователем
Павел Хаустов
#3 Оставлено : 26 октября 2019 г. 15:50:54(UTC)
Ранг: Advanced Member

Группы: Coaches, Registered
Зарегистрирован: 10.10.2010(UTC)
Сообщений: 74
Мужчина
Откуда: Томск
Автор: Павел Хаустов Перейти к цитате
Добрый день!

Скажите пожалуйста, как на тест №11 в задаче №10 (n = 6, k = 2) получить ответ 20 / 15? У нас получается только 18 / 15, если взвешивать две половины монет.


Я поясню нашу стратегию в таком случае. Просто разделяем на две равные части все монеты и надеемся, что вес будет разный. Если разный, то берём ту половину, что тяжелее. Иначе -- нам не повезло :( Рассмотрим все возможные распределения по чашам весов (0 -- нормальная монета, 1 -- фальшивая):

Код:
000 011 (+)
000 101 (+)
000 110 (+)
001 001
001 010
001 100
010 001
010 010
010 100
011 000 (+)
100 001
100 010
100 100
101 000 (+)
110 000 (+)


Получается, что 6 комбинаций из 15 дают нам три настоящие монеты. Наше математическое ожидание равно (3 * 6) / 15 = 18 / 15.

Кроме того, в тесте 16 (n = 21, k = 4) можно узнать стратегию, которая позволяет получить математическое ожидание 45 / 133 (около 0.33834586466)? Наше решение выдаёт 34 / 105 (около 0.32380952381), здесь кроме взвешивания случайной пары монет, мы ничего не смогли придумать.
Вверх
Павел Хаустов
#4 Оставлено : 26 октября 2019 г. 17:11:06(UTC)
Ранг: Advanced Member

Группы: Coaches, Registered
Зарегистрирован: 10.10.2010(UTC)
Сообщений: 74
Мужчина
Откуда: Томск
Жаль, что мы так и не дождались ответа на вопрос по задаче 10, но уже сами разобрались. Пожалуйста, исправьте решение жюри и тесты в задаче 8, это теоретически может повлиять на состав выходящих на полуфинал команд.
Вверх
Михаил Эммануилович Рояк
#7 Оставлено : 26 октября 2019 г. 19:19:50(UTC)
Ранг: Administration

Группы: Administrators, Registered
Зарегистрирован: 15.09.2010(UTC)
Сообщений: 85
Мужчина
Откуда: Новосибирск
Добрый вечер. Прошу прощения, что сразу не ответил, к сожалению, только сейчас добрался до дома и прочитал форум. Про задачу 8 сразу скажу, что да, косяк в тестах очевиден, похоже, что жюри решало какую-то другую задачу. Постараемся за воскресенье разобраться и принять меры.
Вверх
Михаил Эммануилович Рояк
#8 Оставлено : 26 октября 2019 г. 21:34:39(UTC)
Ранг: Administration

Группы: Administrators, Registered
Зарегистрирован: 15.09.2010(UTC)
Сообщений: 85
Мужчина
Откуда: Новосибирск
Действительно, эти 2 теста неверные, получены неверным решением жюри. Выкинули 10 и 16 тесты, поскольку считаем, что если по вине жюри команде задача была засчитана, то это так и должно остаться.
Провели перетестирование, положение в таблице ни у одной команды не поменялось, ошибка в тестах повлияла только на внеконкурсную команду, которая теперь сдала эту задачу с четвертой попытки.
В очередной раз благодарю Павла за бдительность.
Вверх
Павел Хаустов
#9 Оставлено : 27 октября 2019 г. 12:12:35(UTC)
Ранг: Advanced Member

Группы: Coaches, Registered
Зарегистрирован: 10.10.2010(UTC)
Сообщений: 74
Мужчина
Откуда: Томск
Спасибо, что исправили. Также спасибо за благодарность, но бдителен был Алексей Ветров, который большую часть контеста не понимал, почему у него неправильное решение, а также почему чем больше багов он исправляет, тем раньше падает его решение.
Вверх
zaic
#5 Оставлено : 28 октября 2019 г. 14:27:13(UTC)
Ранг: Newbie

Группы: Coaches, Registered
Зарегистрирован: 14.10.2010(UTC)
Сообщений: 8
Автор: Павел Хаустов Перейти к цитате
Жаль, что мы так и не дождались ответа на вопрос по задаче 10, но уже сами разобрались.


Какая получилась стратегия?

Может, я не правильно понял задачу, но при n=6,k=2 поведение "взвесим две случайные монеты с двумя другими случайными" и дальше:
* Если одна из кучек окажется тяжелее, то берём её.
* Если обе кучки равны, то берём вообще две другие монеты.
Почти всегда даёт нам 2 настоящие монеты с МО 28/15 - ошибаемся только в том случае, когда все 4 выбранные монеты оказались настоящими.
Вверх
Павел Хаустов
#6 Оставлено : 28 октября 2019 г. 16:30:16(UTC)
Ранг: Advanced Member

Группы: Coaches, Registered
Зарегистрирован: 10.10.2010(UTC)
Сообщений: 74
Мужчина
Откуда: Томск
Автор: zaic Перейти к цитате
Автор: Павел Хаустов Перейти к цитате
Жаль, что мы так и не дождались ответа на вопрос по задаче 10, но уже сами разобрались.


Какая получилась стратегия?

Может, я не правильно понял задачу, но при n=6,k=2 поведение "взвесим две случайные монеты с двумя другими случайными" и дальше:
* Если одна из кучек окажется тяжелее, то берём её.
* Если обе кучки равны, то берём вообще две другие монеты.
Почти всегда даёт нам 2 настоящие монеты с МО 28/15 - ошибаемся только в том случае, когда все 4 выбранные монеты оказались настоящими.


Как раз при такой тактике (убираем в сторону две монеты, взвешиваем по две монеты на каждой чаше) математическое ожидание равно 20 / 15. Нас не устраивают ровно 5 комбинаций из 15, в которых чаши весов уравновешены. В любом таком случае мы вообще без малейшего понятия, где находятся хорошие монеты: они могут быть обе рядом на столе, а могу быть по одной на каждой из чаш. Во всех остальных случаях мы просто берём две монеты с той чаши, что перевесила. Результат: (10 * 2) / 15 = 20 / 15 = 4 / 3.
Вверх
zaic
#10 Оставлено : 28 октября 2019 г. 18:39:06(UTC)
Ранг: Newbie

Группы: Coaches, Registered
Зарегистрирован: 14.10.2010(UTC)
Сообщений: 8
Ааааа, т.е. банк-то тут и вовсе ни при чём. И надо максимизировать не мат.ожидание того, что мы можем получить от банка, а мат.ожидание числа монет, про которые мы можем гарантированно сказать, что они все на 100% настоящие. Спасибо, теперь разобрался :)
Вверх
zaic
#11 Оставлено : 28 октября 2019 г. 18:52:29(UTC)
Ранг: Newbie

Группы: Coaches, Registered
Зарегистрирован: 14.10.2010(UTC)
Сообщений: 8
Ещё интересно узнать как решать третью задачу.

Граф немаленький, а у меня кроме как переборных идей больше нет никаких. Здесь же, так понимаю, ожидается какое-то кубическое решение.
Вверх
Бабий Дмитрий
#12 Оставлено : 29 октября 2019 г. 8:30:09(UTC)
Ранг: Newbie

Группы: Registered, Administrators
Зарегистрирован: 18.05.2011(UTC)
Сообщений: 6
Откуда: Новосибирск
Автор: zaic Перейти к цитате
Ещё интересно узнать как решать третью задачу.

Граф немаленький, а у меня кроме как переборных идей больше нет никаких. Здесь же, так понимаю, ожидается какое-то кубическое решение.


Строим в графе максимальные паросочетания.
Если хоть в одной компоненте находится свободная вершина, то выигрывает первый (Вася): Вася ходит на сводобную, второй (Петя) на несводобную, далее Вася ходит на парную и т.д
Если ни в одной из компонент графа нет свободной вершины, то выиграет Петя, всегда делая ход на парную вершину.
Вверх
 |  Отредактировано пользователем
Пользователи, просматривающие эту тему
Guest (2)
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.

Форум YAF | YAF © 2003-2011, Yet Another Forum.NET