• Как студенты становятся продвинутыми программистами
    0
    Дело в том, что интервью в гугл на 90% — олимпиадка, причем довольно несложная. Поэтому если человек хоть немного олимпиадник, добыть оффер в гугл для него совершенно проблемой не является. Если же он предпочитает гугл вашей фирме — вряд ли он вообще к вам заглянет. В этом случае реального личного опыта у вас на самом деле нет. Вот за этим и представлять.

    П.С. в середине 90-х я проходил на всерос за 11 класс в 9-ом на основе знаний школьной информатики. Не поехал, потому что предпочел поехать на математику. Думаете, это что-то говорит о моих навыках или о моей школьной информатике? Нет, это всего лишь следствие очень слабого региона. Поэтому ваш П.С. мне ни о чем не говорит, расскажите что-нибудь действительно интересное.
  • Как студенты становятся продвинутыми программистами
    0
    П.С. мое личное мнение основанное на моем же личном опыте…

    Мне вот любопытно стало. Я, к сожалению, не знаю вашей компании и специфики работы в ней, поэтому судить очень трудно. Но есть такой важный критерий: давайте представим, что у кандидата одновременно есть офферы в вашу компанию и в гугл. Если кандидат в 99% случаев выберет гугловый оффер, скорее всего вы ни одного олимпиадного программиста не видели.
  • Простой алгоритм определения пересечения двух отрезков
    +2
    Если вы видите предложение, в котором обозначена некоторая группа людей, это не значит, что это обращение. Строго говоря, нет никакой четкой зависимости между этим предложением и этим постом: вы нигде не утверждали, что вы олимпиадник и что вы считаете задачу простой (да, там есть утверждение о тривиальности, но я считал, что это относится к формулировке). Причина существования этого предложения в том, что задача про пересечение отрезков имеет огромное количество простых и неправильных решений, а придумать правильное решение без разбора кучи случаев не очень тривиально, поэтому начинающие олимпиадники пишут первый вариант решения за 10 минут и только через 4 часа двадцать пятый вариант оказывается верным во всех случаях. Я видел столько подобных случаев, что очередное частное решение в виде статьи на хабре не может не вызывать у меня улыбку. Очень жаль, что такое невинное предложение вас обидело, я этого сделать не пытался.
  • Простой алгоритм определения пересечения двух отрезков
    +1
    Поэтому такая конфигурация подходит под условие и той задачи которая ставилась мне.


    Ну собственно поэтому я Вам и ответил, что я не учитывал случай отрезков лежащих на одной прямой.


    На этом я, пожалуй, покину это обсуждение.
  • Простой алгоритм определения пересечения двух отрезков
    0
    Попробуйте в следующий раз прочитать собственную статью перед тем, как упрекать других в том, что они ее не читали.
  • Простой алгоритм определения пересечения двух отрезков
    +2
    Когда я говорил «Лежащих на различных прямых» я имел в виду «Не лежащих на одной прямой», а вовсе не «Существуют две различные прямые такие, что на них можно уложить по отрезку».

    Если вы внимательно посмотрите на свой алгоритм, вы поймете, что он не отличает точку лежащую на отрезке и точку, лежащую на прямой, но не на отрезке. Эту разницу просто нельзя вычислить векторными произведениями, которые всегда нулевые, если все лежит на одной прямой.

    Строго говоря вычисления более менее одни и те же. Решение системы лучше более простым доказательством и четким пониманием, где оно работает, а где — нет (то, чего так не хватает вашей статье). Ну и бонусом оно нормально работает с отрезками и с многомерными случаями.
  • Простой алгоритм определения пересечения двух отрезков
    +2
    Ну во-первых то что вы описали не является алгоритмом

    Является в предположении, что мой собеседник знает, как решается система из двух линейных уравнений с двумя неизвестными с предельно щедрой добавкой о ненулевом детерминанте системы. Лично я это проходил в седьмом классе примерно. Поэтому я предположил, что вам будет неинтересно читать о том, как это делается. Но если интересно, скажите, я объясню, там все довольно тривиально.

    Является ли пересечением отрезок нулевой длины лежащий на другом отрезке

    Является, если принимать во внимание википедийное определение отрезка. Правда он внезапно целиком лежит на прямой другого отрезка, а значит не очень подходит под условие задачи.
  • Простой алгоритм определения пересечения двух отрезков
    +2
    Соответственно, правильным заголовком будет: «Простой алгоритм пересечения двух интервалов, лежащих на различных прямых». И эта задача решается куда проще.

    Первую прямую мы зададим, как A + (B — A) * x, где x — действительное число. Вторую соответственно C + (D — C) * y. Теперь найдем такие x и y, чтобы A + (B — A) * x = C + (D — C) * y. Это и будет точка пересечения, а для проверки принадлежности отрезку (интервалу) надо лишь проверить, принадлежат ли x и y отрезку (интервалу) от нуля до единицы. Доказательство тривиально.
  • Простой алгоритм определения пересечения двух отрезков
    0
    Если Вы математику помните, то обозначения вроде (a, b), [a, b], и их комбинации Вам что-то об этом должны напомнить.

    Ни разу не слышал, как (a, b) называют отрезком. Википедия относит к отрезку только [a, b], а (a, b) википедия называет промежутком. Я слышал, как (a, b) называют интервалом, а [a, b) и (a, b] — полуинтервалами, но никогда — отрезками. Но указание вашего учебника математики, в котором это называют отрезками, меня вполне убедит.

    Если что, совпадающие отрезки имеют точки пересечения не только в конечных точках, так что очень бы хотелось услышать сколько-нибудь формальное определение пересечения отрезков в котором совпадающие отрезки не пересекаются. Будет совсем здорово, если в этом определении несовпадающие отрезки, которые имеют больше одной общей точки, также не пересекаются.
  • Простой алгоритм определения пересечения двух отрезков
    +1
    Понятно, простота вашего алгоритма заключается в упрощении задачи. Никогда бы не подумал, что бывают люди, считающие совпадающие отрезки непересекающимися…

    Уж простите, что не читал, я увидел вот это:
    (|a| |b| sin(ab))

    и совсем забил на чтение статьи сосредоточившись на коде.
  • Простой алгоритм определения пересечения двух отрезков
    +11
    Каждый начинающий олимпиадник в какой-то момент считает, что пересекать отрезки просто. В вашем случае, например, проблема в том, что один из концов отрезка может лежать на другом отрезке, тогда векторные произведения будут нулевые, однако отрезки будут пересекаться. Попробуйте исправить ваш код так, чтобы он проходил все тесты тут: http://informatics.mccme.ru/mod/statements/view3.php?id=1156&chapterid=280#1.
  • Удивительная техника, которую пока не купишь: бронированные носки, магниты для сражений, виртуальный космический шлем
    +1
    Не очень понятно. Камера на орбите снимает во все стороны (ставить камеру ради всего одного пользователя как-то странно), это все пересылается на сервер на земле, сервер пережимает картинку и отправляет на компы пользователей сразу всю сферу в реальном времени (примерно как 3d видео на ютубе), после чего компы пользователей ответственны за задержку. До компа будет лаг в минуту, на компе будет видео во все стороны на 10 секунд вперед, есть пространство чтобы убрать лаг на поворот головы.
  • Удивительная техника, которую пока не купишь: бронированные носки, магниты для сражений, виртуальный космический шлем
    0
    Я всегда думал, что речь шла о задержке между поворотом головы и поворотом изображения в шлеме. Кому может помешать минутный лаг между камерой на станции и шлемом?
  • Новая краудфандинговая платформа обещает поделиться прибылью с инвесторами
    0
    Можно. Принципиально это будет ничем не отличаться от финансовой пирамиды, живых примеров уже довольно много :).
  • Беспилотники трижды помешали посадке самолетов в JFK
    +1
    «This is crazy,» Baer said. «You can take these drones and, with a 3D printer, make them out of explosives. They're very dangerous and they're advancing pretty quickly.»
  • 90% патентных исков в ИТ подают патентные тролли
    +6
    Вот бы кто-нибудь запатентовал рисовать гистограммы от 17 до 25 и брал бы за это много много денег…
  • Простое суффиксное дерево
    0
    Я вскользь просмотрел алгоритм, но похоже у него есть еще один недостаток по сравнению с Укконеном — он оффлайновый, т.е. ему надо знать строку заранее в то время как в Укконене мы можем за амортизированное O(1) добавить символ к концу строки и обновить дерево.

    К слову, я бы не сказал, что сам Укконен очень сложный, поначалу в нем сложно разобраться, но если понимать, как он работает, написать его не очень сложно и уйдет не очень много строк кода. Моя реализация лежит вот тут например: e-maxx.ru/algo/ukkonen (в самом низу).
  • Доказательство некорректности алгоритма сортировки Android, Java и Python
    +1
    Понятно, спасибо. Я больше по части C++ и для меня все наоборот: в util дофига утилит, поэтому его надо назвать utils, от utilities, что является довольно распространенным сокращением. Функции, заведующие списком я бы сделал статическими методами класса List, а для Array сделал бы класс только со статическими методами для единообразия.
  • Доказательство некорректности алгоритма сортировки Android, Java и Python
    +2
    Кто-нибудь объясните человеку, далекому от Java, есть ли какой-то принцип, по которому выбирают, будет ли имя модуля в единственном числе или во множественном? Почему util в единственном, а Arrays во множественном?
  • Интерфейсы в реальном мире (ещё примеры)
    0
    Не очень понятно, как это помогает? От нее провода только вниз идут. Рядом лежит мобильник и не похоже, что его смахнут на пол во время игры.
  • Интерфейсы в реальном мире (ещё примеры)
    0
    А штука над полем следит, чтобы все делали правильные ходы?
  • Онлайн-фотоконкурсы запатентованы: тролль требует выплат
    +6
    Стоит зарегистрировать патент на проведение конкурса на самый дурацкий патент месяца. Он по-любому выиграет этот конкурс.
  • Подведены итоги Олимпиады по программированию среди школьников
    0
    Я не понимаю, откуда такое мнение. 70% задач на геометрию — тупые построения, как обе задачи из этой темы. Из оставшихся задач 95% решаются сканлайном либо выпуклой оболочкой. Оставшиеся задачи используют геометрические примитивы только для формулировки: они либо основаны на вытаскивании чисел и запихивании их в структуру данных, либо очень технические и не требуют думать, а просто аккуратно реализовать 9000 шагов, описанных в условии. Последние тяжело назвать геометрическими, это все равно что считать задачи с домами задачами на архитектуру. Это все дополняется тем, что ответ часто дробный и можно одним тестом проверить весь код сразу с очень неплохим шансом. Если задачи на геометрию решаются плохо — обычно это значит, что кто-то перегробил геометрию в туре.
  • Разбор задачи «Зеркало в коридоре» и негодование
    +1
    Глядя на тся/ться ошибки в текстах условий могу предположить наличие на туре более простой задачи с косяком составителей, на поиск которого ушло много времени (ну или просто хорошо спрятанной подставой). Никак иначе я не могу объяснить существование серебрянного призера межнара, не решившего эту задачу.
  • Разбор задачи «Зеркало в коридоре» и негодование
    0
    Мой скептицизм основан на личном опыте. Задачи на геометрию в большинстве своем довольно простые, т.к. ошибаться там особо негде и двумя тестами можно покрыть 90% возможных проблем. Сэкономленное на потенциальной отладке время достаточно велико, чтобы аккуратно посмотреть на задачу и понять, как она решается.

    В данном случае трехмерный случай решается так: чертим перпендикуляр к зеркалу в точке касания луча, опускаем на него перпендикуляры исходных точек, получаем два подобных треугольника, которые кажется в 9 классе проходят. Их отношение найти довольно легко по расстояниям до зеркала, затем надо в проекции на плоскость зеркала отрезок между двумя исходными точками поделить в той же пропорции и проверить на принадлежность кругу. Все операции описанные выше довольно тривиальны и любой школьник их легко выведет прямо на туре, если вдруг по какой-то причине он их не помнит.
  • Разбор задачи «Зеркало в коридоре» и негодование
    +2
    Автор делает ту же ошибку, что и типичный студент, освоивший началы матана и пытающийся доказать, что следующая задача нерешаема для школьников: «Взяли стакан молока и чашку чая. Набрали ложку молока из стакана, кинули в чай и размешали. Набрали ложку смеси из чашки, кинули в стакан и размешали. Чего больше: молока в чае или чая в молоке?», в то время, как многие школьники могут дать ответ моментально. Школьники, которые хоть немного решали геометрические задачи в олимпиадном программировании прекрасно умеют пересекать круг с прямой. Некоторые могут даже в восьмимерном пространстве пересечь.
  • Подведены итоги Олимпиады по программированию среди школьников
    +1
    Зачем ехать на межнар не умея писать довольно простой перебор с комбинаторикой — мне не очень понятно, но это не важно. Попасть на финал из неизвестного вуза довольно легко и я слышал об энтузиастах, которые поступают в неизвестный вуз, чтобы проделать этот трюк.

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

    Называть олимпиаду международной можно только формально и инициатива выглядит, как попытка косить под почти идентично зовущийся IOI, в которой уровень слова «международный» совершенно иной. Но это тоже неважно.

    Что важно — так это отношение организаторов. Глупые орфографические ошибки в условиях; картинки, которые даже на хабре всех путают, закрытые задачи и результаты; список победителей лежит на бывшей странице регистрации и у нее все еще неверный заголовок, призеров называют победителями, победителей — призерами и не дают им диплом первой степени, как это обычно принято; олимпиада не ориентирована на уровень ниже, чем у московских спецшкол, но серебряный призер IOI все равно участвует и еще миллион мелочей, явно показывающий, что на образовательные и рекламные цели олимпиады всем пофиг, а людей с прямыми руками, которые могут сделать все по-нормальному в вузе нет совсем.

    Все это очень напоминает воронежскую олимпиаду: esci.ru/ttb/vserossiyskaya_studencheskaya_olympiada_in_informatics.htm. Когда я был школьником, я прочитал этот текст и точно знал, в какой вуз я никогда не пойду даже заглянуть внутрь.
  • Подведены итоги Олимпиады по программированию среди школьников
    +1
    Приглашаем на олимпиаду школьников из Беларуси, называем ее международной. Признак международной олимпиады — наличие школьников из по крайней мере двух стран, проверять тексты задач на ошибки уровня тся/ться для этого вовсе не обязательно. Мне вот интересно, откуда у неизвестных в олимпиадном программировании вузов такое стойкое желание организовать олимпиаду с как можно более громким названием?
  • Делить на ноль — это норма. Часть 1
    0
    Квантовая суперпозиция на мой взгляд — вопрос вполне себе физический.
  • Делить на ноль — это норма. Часть 1
    0
    Волновая функция например.
  • Максимальное XOR
    +2
    L не равно нулю в общем случае. Но даже для L=0 это неверно. Пусть R=4, тогда оптимальные a и b — это 3 и 4: 3^4 = 7.
  • Максимальное XOR
    0
    Забавно смотреть на ваши оптимизации, расположенные по соседству со считыванием через cin :)
  • Максимальное XOR
    +2
    Все-таки стоило прочитать статью перед написанием этого комментария…
  • Максимальное XOR
    +5
    Шта???

    Давайте я код напишу, чтобы было понятно: ideone.com/Po4JgL. У того, что я описал сложность — O(log n).

    O(n) не равно nlogn
  • Максимальное XOR
    +25
    Ээм… А чего так сложно?

    Берем L и R, находим у них самый старший бит, который различается, с битами выше ничего сделать нельзя, биты ниже легко сделать единицами, т.к. если у нас L вида xy...z0..., а R вида xy...z1..., то очевидно, что в промежутке есть числа xy...z011...1 и xy...z100...0.
  • Gangnam Style сломал переменную количества просмотров
    +2
    Я чего-то не знаю? Как связаны YouTube и Java?
  • Максимально реалистичная анимация
  • В США испытали боевой лазер — на литий-ионных батареях и с контроллером от Xbox
    +10
    Сначала в зеркало летит разрывной патрон, а потом придется как-то мотивировать трату 36 миллионов долларов на уже ненужный лазер :)
  • Две красивые задачи по алгоритмам
    +1
    Это неверно. Мы не можем уйти в стек больше, чем на O(n). Кроме того, можно аккуратно раскрыть хвостовую рекурсию и гарантировать O(log n) для глубины стека в худшем случае.
  • Две красивые задачи по алгоритмам
    +1
    А еще Quicksort требует O(log n) дополнительной памяти