Comments: |
Расширяем ли набор задач? Если да, то 1) хочу мазу и задачи в классы студентам 2) готова делать задачи (т.е. перевести часть задач классических задач cs на эту мазу забесплатно и придумать новые на разные разделы; я это могу и могу много)
Причина: даже если человек олимпиадник-международник по математике, то это еще не значит, что он прекрасно начинает писать программы на формальном языке (а если не олимпиадник-международник, а просто умный мальчик, то еще менее значит). Я готова согласиться, что часть народа в студенческие годы, как и среднюю школу, нужно учить через "программирование в картинках". Особенно, если это первый язык программирования. 3-5% на математических специальностях обучаются либо туго, либо очень туго.
Программирование, как написано в заголовке лучшего учебника по программированию это алгоритмы + структуры данных. Где в этой игре данные? Возможно эта игра развивает алгоритмическое мышление, но это не программирование.
Данные используются в 10 уровне.
Надо будет сегодня же на сыне опробовать.. ;)
да, очень интересно. в конце автор рассуждает о том, что в США проблема с компетентными учителями CS, при этом умалчивает о том, откуда они взялись во Вьетнаме. что удивительно, учитывая его же слова о том, что в тамошних университетах не так всё впечатляет, т.к. CS пришли в страну недавно. ну и по поводу нёрдов, по-моему, у него устаревшая информация. с тех пор как супергерои и звёздные войны завоевали попкультуру (последние 7-10 лет), ботаны вышли из подполья. сам этот факт уже вполне обыгрывается в фильмах, см. к примеру 21 Jump Street (2012).
Очень интересно, спасибо. По забавному совпадению я сейчас во Вьетнаме отдыхаю, а один из моих коллег-разработчиков в сиднейской компании, где я работаю, - вьетнамец и один из лучших программистов в компании. Правда, акцент его ну очень сложно бывает понимать.
Во Вьетнаме были одни из самых лучших аутсорс программистов, которых мы нанимали.
Интересно, что эта его игра сделана на базе Scratch ( http://scratch.mit.edu/). Мы с Юлей с ним как раз последние пару недель играем. С одной стороны, язык для детей, но с другой, вполне мощный и интересный. Можно делать мультики и игры. Это не то же самое, как в детстве Фортран учить...
Задача непростая, да — не сразу понятно, что же обозначают единицы и нули в данных.
Это сарказм, или не вполне понятный мне смысл?
![[User Picture]](https://l-userpic.livejournal.com/61874993/12965091) | From: aivean 2013-03-21 08:23 pm
в чем сложность задачи? | (Link)
|
Правильно ли я понимаю, что вся «сложность» заключается в поиске в ширину? Вначале он запускается при проходе по периметру, затем при проходе за N*M по всей площади лабиринта. Ассимптотическая сложность O(N*M).
![[User Picture]](https://l-userpic.livejournal.com/81048954/111931) | From: avva 2013-03-21 09:33 pm
Re: в чем сложность задачи? | (Link)
|
Это один из возможных подходов, да. По-моему, проще делать поиск (неважно, в ширину или глубину), обходя весь лабиринт, разбить таким образом его на связные компоненты, а потом идентифицировать открытые компоненты тем, что они касаются периметра.
Сложность заключается в следуюшем: - понять, как решается задача - написать код на бумаге или доске без ошибок, или уметь найти и исправить собственные ошибки - сделать это в стрессовой обстановке интервью, уложиться в заданное время - в данной конкретной задаче есть также серьезная проблема, которую вы не заметили: правильно вернуть площадь наибольшей замкнутой области (надо учесть, в каких единицах определана площадь, это не кол-во нулей - см. правильный ответ в условии задачи). У меня на "честное" решение этой части ушла минимум треть всего времени на задачу.
В Гугле на интервью задают в принципе три разных вида задач: 1. algo 2. coding 3. system design
Для алгоритмической задачи эта слишком проста. Для задачи на написание кода она в самый раз или даже сложнее средней.
В школьном тесте я бы решал задачу в лоб, не заботясь об эффективности и общности: 1. Заменить в матрице все «висячие» единицы (т.е. граничащие с не более чем одной единицей) на 0. Итерировать, пока таковых не останется. 2. Удалить из матрицы (скажем, заменить на «-1») все пограничные нули. (Ноль – пограничный, если с одной из 4 сторон касается границы матрицы или ранее удаленного нуля). Итерировать, пока пограничных нулей не останется. 3. (общий шаг) Выбрать какой нибудь «0» и удалить из матрицы. Затем итеративно удалить все другие нули, граничащие с ранее удаленными. При удалении накапливать суммарную площадь по правилу: если не граничит с единицами, добавить 1; если граничит с одной единицей, добавить ½; если с двумя – добавить ¼. Когда не остается нулей для удаления, накопленная сумма есть (16-кратная) площадь соответствующей области. Продолжаем процесс, считая области и сравнивая их площади, до тех пор пока остаются нули.
У меня чистое программирование с отладкой в С++ заняло около 40 мин, но перед этим я потратил некоторое время на обдумывние алгоритма и структуры программы. Это время я не засек; это могло быть от 5 до 20 мин.
Но на интервью я бы, наверное, решал иначе, сведя к более общей задаче. Какие-то усилия заняло бы написание процедуры перевода матрицы в плоский граф (вершины с координатами и ребра), но зато потом решать легче и приятнее. Достаточно трех-четырех операторов, чтобы удалить все висячие ребра; при обходе контура элементарно считается площадь многоугольника через координаты вершин, и т.п.
А нельзя просто сжульничать с казать,, что площадть -- это floor(s/12), где s -- это площадь в единицах измерения файла?
Когда речь идет об обучении детей программированию, понятно, что могут представлять ценность разнообразные надумано-искуственные задачи с заранее заказанными надуманно-искуственными способами решения. Но за пределами этой области надуманость и искуственность никакого смысла не имеют.
В данном случае, я вижу, что публика решала ярко выраженную _векторную_ задачу (именно как векторная она сформулирована в исходной абстрактной постановке) как _растровую_ задачу. Для детишек в школе, которым учитель сказал, что требуется именно растровое решение, это приемлемо - они учатся искать и считать клеточки в матрице
Готовый программист же, будучи ознакомлен с исходной абстрактной постановкой задачи, должен сделать большие глаза, увидев, что входные данные вдруг с какого-то бодуна представлены растром. Для любого job interview (если интервьюирующий не идиот) в такой ситуации правильным ответом является: ткнуть пальцем во входные данные и сказать "вы что, с дуба ляснулись?!". Садиться же тихо строчить растровое решение "за 40 минут" в такой ситуации является ярко выраженным признаком непрофессионализма.
Если же "заказчик" таки настаивает на растровом задании входа, то правильным решением будет все таки разработать собственный векторный формат входа и решение именно для векторной задачи. А затем просто написать "преобразовалку" растрового входа к вектороному, т.е. свести решение растровой задачи к уже решенной векторной задаче. Да, это может занять больше, чем 40 минут. Но это продемонтирует тот факт, что программист умеет разделять поствленную задачу на осмысленое ядро и малозначительную интерфейсную шелуху. Последеняя существует лишь потому, что "заказчик" еще сам не понял, что ему нужно.
Edited at 2013-03-25 17:48 (UTC)
Поскольку я один в этой дискуссии упомянул 40 минут ( Avva решил за 35), то Ваши слова -
Садиться же тихо строчить растровое решение "за 40 минут" в такой ситуации является ярко выраженным признаком непрофессионализма -
очевидно, относятся ко мне.
В свою защиту процитирую свой комментармй выше:
Но на интервью я бы, наверное, решал иначе, сведя к более общей задаче. Какие-то усилия заняло бы написание процедуры перевода матрицы в плоский граф (вершины с координатами и ребра), но зато потом решать легче и приятнее и т.д.
Но говорить на интервью "вы что, с дуба ляснулись?!" я бы все-таки воздержался.
Edited at 2013-03-25 23:25 (UTC) | |