Intel® Software Network

В переводе третьего задания пропущена очень важная фраза, возможный перевод которой следующий: Число студентов в файле будет четным, меньшим 2^28-1, так, чтобы все входные данные могли вместиться в основную память избранной компьютерной платформы.

Фраза очень обтекаемая: "избранная (target) платформа" кем? - Вами или судьями?!Важность этой фразы станет очевидной, если попробовать прикинуть количество гигабайт дискового пространства для входного файла: на каждую строчку 10 байт на имя студента+ 1 пробел(=1 байт)+50 байт на анкетные данные и умножить на 2^28...(точнее - на 2^28-2)... 

Умножили? А теперь прикиньте, сколько памяти нужно Вашей задаче, чтобы хранить это все, может, в более экономном виде, но все же...

Легче от того, что студентов четное число, иначе нужен был бы дополнительный код для выселения оставшегося студента в "одиночку" - не сложно, но все же...

Желаю успеха!

 

Перед тем как сделать перевод, я долго спорил с ребятами из штатов по поводу формулировки этого задания. Как вы, наверное, понимаете, формулировка подобного рода заданий вещь очень тонкая.

В частности, фраза «The number of students within the file will be an even number less than 2^28 - 1 and all input data will fit within the main memory of the target platform.» была изменена мной, т.к. изначально слово «input» было пропущено, что еще более обтекаемо :).

А в первоначальной версии перевода моя окончательная версия этого предложения «Объем входных данных позволяет разместить их в основной памяти системы; N является четным числом, меньшим, чем 2^28 – 1» просто потерялась из-за ошибки копи-пасте, и я поправился почти сразу же.

Я тоже беспокоился о гигантском числе 2^28, явно противоречащим с ограничением по времени исполнения. Могу сказать, что при тестировании будут использованы разумные входные данные, а 2^28-1 является лишь намеком на использование переменных соответствующего типа… Уже подсчитали, какого?

---

Дмитрий Оганезов
Intel® Software Network

Ok! Спасибо! Надеюсь на реальную "общагу" не более 5 тыс. человек. Хотелось бы, чтобы испытания проводились для нескольких наборов данных разного размера (например, 500, 1000, 5000 и 10000) и по несколько раз (нужно брать среднее для каждого набора) - иначе стохастический алгоритм для виртуальных студентов превратится в лотерею для реальных участников.

мы учтем ваши пожелания по мере возможностей :)

---

Марианна Светлосанова
Intel® Software Network

MAD\msvetlos:

мы учтем ваши пожелания по мере возможностей :)

Спасибо!

Могу добавить, что по собственному решению вижу, что маленькое число студентов (например, 10), может привести к интересным коллизиям в программе: 10 потоков пытаются растащить решения для 5 комнат и т.д. Так что если судьи захотят усложнить жизнь участников, они могут расширить испытательную выборку в меньшую сторону. Хотя лично мне все равно, я на всякий случай принял меры в своем решении :)

Михаил.

Если честно, мне жюри уже немножко жалко, это задание очень сложное в судействе будет...  Слишком много условностей накручено и анализ результатов тоже не шутка.

---

Дмитрий Оганезов
Intel® Software Network

MAD\doganezo:

Если честно, мне жюри уже немножко жалко, это задание очень сложное в судействе будет...  Слишком много условностей накручено и анализ результатов тоже не шутка.

Я полностью согласен с Вами – бедные судьи!

 

-- Михаил.

А, по-моему, судить это задание очень просто -

берем и запускаем задачу на одном процессоре и смотрим

финальное значение TD; затем, запускаем задачу последовательно

на 2, 3, ..., 8 процессорах и смотрим как убывает

(если убывает [;)] ) это значение.

В заключение, можно глянуть размер кода ...

Сравниваем полученные данные с данными другой задачи

и выбираем лучшее ...

Так-то оно так, а "проверка качества"? А как быть с ограничением по времени? А ограничение по алгоритму? А "элегантность"?

В любом случае, я вижу что вы получили неплохие баллы, меня немного смутила оценка за элегантность... Но, спорить с судьями не могу даже я :).

---

Дмитрий Оганезов
Intel® Software Network

MAD\doganezo:

Но, спорить с судьями не могу даже я :).

А надо бы -

наши решения в первом туре за производительность получили 0 баллов.

После этого, нам стали приходить письма от жюри

"мол, не можем запустить ваши задания".

Т.е., наши решения 1-го тура реально не запускались [:(]

У меня тоже было 0 баллов за скорость в первом туре, но никаких писем, объясняющих это хоть как-то, я не получал :(

YurySerdyuk:

MAD\doganezo:

Но, спорить с судьями не могу даже я :).

А надо бы -

наши решения в первом туре за производительность получили 0 баллов.

После этого, нам стали приходить письма от жюри

"мол, не можем запустить ваши задания".

Т.е., наши решения 1-го тура реально не запускались [:(]

Я стал следить за начисляемыми баллами. Кроме того, я постараюсь внедрить "своего человека" в состав жюри... А пробовали ли вы задать вопрос насчет писем счастья про "не можем запустить" непосредственно американцам?

Марианна, надо бы нам обсудить это между собой :)

---

Дмитрий Оганезов
Intel® Software Network