Как стать автором
Обновить

Комментарии 56

Последняя задача вроде просто неверно решена, отсутствует доказательство оптимальности решения, сортировка по убыванию, даёт неплохое решение подобных задач, но не всегда лучшее.
Дан например список 11, 10,7,7,7,
получится по приведенному алгоритму:
11,7 — в первой группе и 10,7,7 — во второй. Хотя, верным будет 11 ,10 в первой группе и 7,7,7 во второй
Бедные дети
Для равных по кол-ву команд, все равно неверно, например список 11,10,7,7,7,1: алгоритм выдаст 11,7, 1и 10 ,7,7 хотя верно 11,10,1 и 7,7,7
А так да видимо она оказалась сложной не для школьников, а для организаторов.
Жадный алгоритм относительно просто базовое решение, которое можно втолковывать школьникам и не отбить у них желание заниматься. Я видеоразбор давно записывал, точно не помню, но кажется упоминал, что предлагаемое решение обеспечивает приемлемый уровень оптимальности при так скажем трудозатратах на написание решения.
А вообще мы бы приняли даже менее оптимальные решения, лишь бы участники приложили усилия.
Задачи раскроя — это NP задачи. А формулировать задачи нужно корректно.
В данном случае нужно было упомянуть в условии субоптимальность возможного решения
Вот кстати про очень важный момент говорите — формулировка условий задач — реально важный момент, посмотреть на составленные задачи сторонним взглядом ученика, а не педагога, совсем непросто и надо держать с участниками олимпиады оперативную связь, чтобы отвечать на вопросы, давать пояснения.
Мы так делали — было полезно.
Я прочитал условия некоторых задач. Ощущение что брали иностранные задачи и переводили гуглом.
Приходится по 2-3 раза перечитывать чтобы точно понять суть.
Точно их нельзя нормально переформулировать для детей?
Не показывать детям оптимального решения — это очень плохая практика.
Лучше посмотрите, как готовят задачи ко ВСоШ по информатике: там для каждой подзадачи (ну почти) есть отдельное решение с его доказательством.
Ещё хуже, когда проверяющие студенты не принимают верного решения, потому что видят неверное референсное. У меня такое было.
Опять же, автоматизированные тесты — наше все.
Соглашусь, но с точки зрения организатора — есть ли на это время и трудоресурсы. Как пример организаторы олимпиады “Играем в программистов” про которую я упоминаю в статье, только в этом году(а проводят её очень-очень давно) нашли время на автотесты. Потому что реально не хватает сил, времени и людей на этот момент, когда речь идёт об организации местного уровня. И то добрались до автотестов потому что наконец-то, впервые за чуть ли не 15 лет, один из ВУЗов стал соорганизатором.
А вот по scratch всё равно ручная проверка и никак больше…

Зачем это делать самому? Есть готовые платформы, такие как codility

Вы серьёзно?
Платная рекрутинговая платформа для проведения некоммерческой местной школьной олимпиады?

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


Если не умеют работать с файлами — можно дать куски готового кода.


Правда не знаю, может ли работать с файлами scratch.

Стандартный ввод-вывод тоже часто используется в автотестах, особо разницы нет, что использовать, как удобнее.
В Scrtatch или Snap можно импортировать только списки, таким образом давать через файл входные данные, что довольно полезно в части предварительной подготовки к переходу обучения на тот же pytthon, но выходные экпортить автоматом никак, причём там не всегда возможен(отчасти, что это сложнее для ребёнка) текстовый результат, чаще визуальный.
Меня честно говоря оттолкнула от автотестов история коллег муниципалов, которые для своей олимпиады сделали десятки наборов данных на каждую задачу)) Это круто, но показалось, что будет очень трудозатратно.
Да это действительно отличный пример и предварительная подготовка решения с доказательством очень поможет, особенно когда проверкой решений занимается много разных людей.
Главная проблема дистанционного проведения подобных олимпиад — это то, что участник может нагуглить алгоритмы, необходимые для решения задач, либо попросить помощи.
Мы так и переживали, решая проводить в таком формате или нет, но в жизни немного иначе оказалось. Я делюсь как это по факту вышло, вообще даже на той же дистанционнной скретч олимпиаде Роббо, три года уже смотрю победившие проекты, судя по ним — помощь детям оказывают так себе.
Я точно знаю, что ученики моей же школы пытались гуглить, искать похожие задачи, но что-то не смогли совсем. Не умеют школьники гуглить алгоритмы видимо.
Чтобы гуглить, нужно знать, что гуглить. А если знаешь что, то и гуглить не надо.
Вот и я также подумал и не прогадал)) Тем более, если задачи описывать по-своему, а не брать готовые чужие, у которых решений тьма выложена, то даже найти похожую трудно будет.

Знание алгоритмов — хорошо, а знание алгоритмов + доступ к e-maxx (или что там сейчас популярное) — лучше :)

Это у вас или не попались, или не спалились с вариантом "папа/мама программист" :-)

У вас ошибка в решении 10 задачи.
И она просто на порядок сложнее всех остальных. Решение 10 сложнее чем всех остальных вместе взятых. И вообще Dp школьникам явно рано.

Самая сложна это 8 задача. Но, да, вы правы, задачи 8-10 оказались непосильными.
А решение жадным алгоритмом не является ошибкой. Это приближенный быстрый метод решения задачи NP-задачи. Мы рассказывали решение в контексте проходимой с учениками темы, не углубляясь в дебри точных решений, которые кстати неприменимы для рюкзаков, так скажем: больших размеров.
Лучше пропустить материал к которому не готовы, чем научить неправильным вещам. Переучиваться сложнее.
Лучше пропустить материал к которому не готовы, чем научить неправильным вещам

научить неправильным вещам

Ехидный комментарий про "griby", "vozmojnost", "stolb", "stroka", "vvod", "kolvo", "summa1", "summa2"

Вы в ответах даете неверное решение. В условиях нет ни слова не про приближение.
Правильное решение безумно сложно для школьника. Вы сами попробуйте его написать понятным языком. И понятным кодом. Все сразу сами поймете.

Вы обманываете детей. Так нельзя делать. Никогда.

8 — непонятные условия. Я 3 раза перечитал. Посмотрел ответ и все равно не понял что надо делать.
10 — все понятно. Но dp. Для школьников нерешаемо. И неверный ответ от организаторов сверху.
И то и то демотивирует и ставит огранизаторов на роль неких шутов. Которые хотят чтобы ответ подогнали под их понимание правильности. Или разобрались а что же они хотели сказать этим вопросом.

Не выдумавайте сами. Берите условия с любых проверенных олимпиад. Там все четко и без нерешаемых задач люди сделали.
Восьмая задача — заполнение квадратной матрицы зигзагом начиная с верхнего правого угла. По примеру понятно, а сформулировано коряво, но задача несложная. Примерно как здесь:
www.mathworks.com/matlabcentral/fileexchange/56332-zigzag-scan-any-n-n-matrix-bloc-of-image
Десятая задача — элементарная и легко решается полным перебором. Порядок сложности -факториал.
Вот её оптимизации — очень нетривиальны. И не для школьников.
8 — перечитал еще раз. Посмотрел ответ. Понял. Не зигзагом там. Там наискосок надо квадрат заполнить. Так формулировать задачи нельзя.

К факториалу претензий по сути нет. Хотя все равно слишком сложно по сравнению с остальными. Тогда надо зарубать все решения сделанные по другому. И обязательно нужно примечание в задаче. «Супер сложно. Не беритесь пока все остальное не сделали.» Для отделения первого места от второго может пригодится.

Претензия к 10 это неверный ответ организатора. Участник должен угадать что у организатора в голове. Не надо решать верно, надо просто угадать о чем думал тот кто это придумывал. Так делать нельзя. Это дискредитирует всю идею олимпиад по программированию.
Ну я хотел поправиться — это скан называется. Только диагональный.
А с неверным ответом на 10, вы когда пишете, сначала читайте комментарии. Уже в первом комментарии написано, что решение неверное. А так я с Вами полностью согласен.
И кстати, если было в условии сказано, что решить нужно полным перебором, то задача была бы как раз для школьников.
Да, сорри. Писал раньше чем читал.
Да не, все нормально, просто мы с вами полностью повторили претензии к автору. И я согласен, что задачи нужно брать проверенные. Впрочем мне и в учебнике попадались неверно решённые задачи. Особенно по статистике и теории вероятностей.
Мне тоже. И на олимпиадах в детстве мне такие же организаторы попадались. Во времена тервера я уже философски к такому относился. А вот в школе обидно было.
Да, это точно. Было очень обидно.

Там будет 100!/(50!*50!) при максимальном числе участников. Ради интереса залез в wolfram alpha — это порядка 10^29. На процессоре частотой 1 GHz — 10^20 секунд или 10^12 лет. Я бы это не считал решением.

Формально говоря это все равно верное решение. Время то ограничено не было. Другое дело, что тут явный прокол организаторов.
Формально, максимум участников там неизвестен: (1 ≤ wi ≤ 100) это уровни персонажа. Но решения там, там конечно нет.

Опс, и правда это уровни, а не макс. количество.

Вот она geeksforgeeks Даже условие у автора задано почти корректно.
Спасибо за метод, я его упустил. Числа то небольшие целые.

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

А потом расстроиться что менее умный школьник сделал попроще и выиграл. Хотя тот кто выиграл даже не понял что он дал неверный ответ.

Нельзя так делать. Нельзя обманывать детей. Тем более что есть выверенные задачки, с верными и доступными школьникам решениями. Надо просто взять их.

А почему такая старая версия java? Даже не восьмая. И не хватает IDE от jetbrains что для java, что для пайтона.

Хороший вопрос без stream api и лямбд тяжело.
Версию компилятора C++ и C# вообще не указали (msvc/dmsc).

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

Да вроде нет, к каждой задаче было по 5 тестов, всё чётко — программа прошла тесты или нет.

Отдельно по 10 задаче мы планировали смотреть подробно решение, если оно не будет проходить тесты, но алгоритм будет давать значения приближенные к оптимальным.
Но смотреть было нечего, потому что никто 8-10 задачи не решил.

Не вникая в задачи как таковые, хочу поддержать автора в его начинании. Приятно смотреть на завершенную работу

Спасибо на добром слове!
только одна олимпиада в которой могут участвовать питонисты — “Играем в программистов”


Очень странное утверждение, а как же Всероссийская олимпиада школьников? В Иркутске её не проводят?
НЛО прилетело и опубликовало эту надпись здесь
Я именно про местные олимпиады говорю, тем паче, что на Всерос в школах жёсткий отбор, так как школам выставляют лимиты на количество участников. Примерно так: от обычной СОШ на районный этап могут пройти 1-2 ученика, от лицея/гимназии 4-5 учеников.
Плюс — только 5-11 классы.
VisualStudio 2019

Вот так детей и подсаживают на проприетарщину

Вы специально включили в статью код картинками, чтобы хитрому ученику потом было сложнее нагуглить или скопипастить решение, а осилив это задание, потом обнаружить, что среди них есть тупо неправильные? Или же таков был уровень подготовки к низкобюджетной олимпиаде?
Заголовок спойлера
Задача 9
file = open('input.txt')
animal = []
kolvo = []
for stroka in file:
    data = stroka.split()
    animal.append(data[0])

for i in animal:
    kolvo.append(animal.count(i))

maxi = 0
pos = 0
for i in range(len(kolvo)):
    if kolvo[i] > maxi:
        maxi = kolvo[i]
        pos = i
print (animal[i], maxi, end=" ")

$ cat input.txt 
Shark White
Shark White
Turtle Caiman
Shark zebra
Turtle Caiman

$ python a.py 
Turtle 3 


А он разве картинками?
У меня текстом показывается


А в коде да, ошибка. Последняя строка должна быть
print (animal[pos], maxi, end=" ")
Автоматичекую проверку решений сделать достаточно просто.
Для подготовки задач можно использовать Полигон polygon.codeforces.com, а для проведения соревнований — ЯндексКонтест contest.yandex.ru
Если интересно — пишите, поделюсь опытом.
Спасибо за совет, и сам посмотрю на будущее и надеюсь кому поможет!
Мне интересно, почему сишные компиляторы ограничены платформой windows?
Вы не представляете, сколько школьников интересующихся IT вообще и программированием в частности тусуется в телеграм чатах linux направленности. У них и винды-то, зачастую, вообще нет.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории