Re: олимпиада ABBYY
Хм, а когда ближайшая? )
на ярмарке вакансий
на ярмарке вакансийВсе бежим на ярмарку!
Она в середине дня. Очень неудобное для трудоустроенных время 
А конкретнее? Время, место...
может, кто-нибудь ответит по-существу: задачи с прошлых олимпиад у кого-нибудь есть? Понятно, что на сайте Abbyy задачи, потенциально предназначенные для собеседования, не публикуют.
На память то что было в прошлом году:
Мат. задачка - 100 заключенных могут немного поговорить, после чего их разведут по камерам и они больше не встретятся. Затем каждые n минут выбирают случайного заключенного, и заводят его в комнату с рычагом. Он может его переключить, если хочет (у рычага 2 состояния - вкл. и выкл.). После этого его отводят обратно в камеру. Ясно, что в следующий раз могут снова выбрать его же - рандом, так сказать. Опять же, у рандома есть такое замечательное свойство: каждый заключенный обязательно в комнату с рычагом попадет (когда-нибудь). И, очевидно, если процесс будет продолжаться долго - то попадет не один раз.
Ну дак вот. На сборе, что был в начале, заключенным все это объявили, а также сказали, что при выходе из комнаты с рычагом выходящий может сказать "все 100 уже побывали в этой комнате". Если это действительно так, то всех отпускают, иначе казнят. Надо разработать план действий заключенных в 2-х случаях:
а. Изначально рычаг выключен, и это известно заключенным.
б. Изначальное состояние рычага неизвестно.
Еще было 2 элементарных задачи по программированию - надо было описать алгоритм. Одна была на использование бора, другая - на динамику на дереве, условия точно сейчас не воспроизведу.
И еще была задачка на шифрование - дано несколько зашифрованных сообщений, некоторые из них тут же на месте расшифрованы, надо рюхнуть метод и расшифровать оставшиеся. Для меня это был самый гроб, на ее решение убил почти все время. Опять же, условие на память не воспроизведу.
Думаю, если спросите у mkal'а, он может и поделится условиями (хотя не факт).
Мат. задачка - 100 заключенных могут немного поговорить, после чего их разведут по камерам и они больше не встретятся. Затем каждые n минут выбирают случайного заключенного, и заводят его в комнату с рычагом. Он может его переключить, если хочет (у рычага 2 состояния - вкл. и выкл.). После этого его отводят обратно в камеру. Ясно, что в следующий раз могут снова выбрать его же - рандом, так сказать. Опять же, у рандома есть такое замечательное свойство: каждый заключенный обязательно в комнату с рычагом попадет (когда-нибудь). И, очевидно, если процесс будет продолжаться долго - то попадет не один раз.
Ну дак вот. На сборе, что был в начале, заключенным все это объявили, а также сказали, что при выходе из комнаты с рычагом выходящий может сказать "все 100 уже побывали в этой комнате". Если это действительно так, то всех отпускают, иначе казнят. Надо разработать план действий заключенных в 2-х случаях:
а. Изначально рычаг выключен, и это известно заключенным.
б. Изначальное состояние рычага неизвестно.
Еще было 2 элементарных задачи по программированию - надо было описать алгоритм. Одна была на использование бора, другая - на динамику на дереве, условия точно сейчас не воспроизведу.
И еще была задачка на шифрование - дано несколько зашифрованных сообщений, некоторые из них тут же на месте расшифрованы, надо рюхнуть метод и расшифровать оставшиеся. Для меня это был самый гроб, на ее решение убил почти все время. Опять же, условие на память не воспроизведу.
Думаю, если спросите у mkal'а, он может и поделится условиями (хотя не факт).
> И еще была задачка на шифрование - дано несколько зашифрованных сообщений, некоторые из них тут же на месте расшифрованы, надо рюхнуть метод и расшифровать оставшиеся.
Шифрование, как это принято в информатике (ну там, грубо говоря, DES или лингвистические задачи, где надо по фразам на незнакомых языках и их переводам понять принцип?
Шифрование, как это принято в информатике (ну там, грубо говоря, DES или лингвистические задачи, где надо по фразам на незнакомых языках и их переводам понять принцип?
по идее там стандартные задачи с собеседования.
несколько простых мат. задач - раскраска, шифрование и т.д. Типа олимпиалных задач класс за 6.
несколько по алгоритмам - проверить есть ли цикл в списке, за линейное врнемя и память. Есть 2 строки которые содержат последовательность чисел разделенных запятой без повторения надо найти все общие числа и их позиции за линейное время и память.
Это что было у меня и моего начальника )
несколько простых мат. задач - раскраска, шифрование и т.д. Типа олимпиалных задач класс за 6.
несколько по алгоритмам - проверить есть ли цикл в списке, за линейное врнемя и память. Есть 2 строки которые содержат последовательность чисел разделенных запятой без повторения надо найти все общие числа и их позиции за линейное время и память.
Это что было у меня и моего начальника )
лингвистические
дано несколько зашифрованных сообщений, некоторые из них тут же на месте расшифрованы, надо рюхнуть метод и расшифровать оставшиеся.А на практике оно зачем надо? Есть доставшийся в наследство код который по ситаксису вообще не должен работать, но работает правильно, и нужно рюхнуть как он работает? %)
ну, вообще-то Абби занимается распознаванием текста и словарями. Почему бы кандидату не предъявить способность легко разбираться в языковых трудностях?
Есть 2 строки которые содержат последовательность чисел разделенных запятой без повторения надо найти все общие числа и их позиции за линейное время и памятья правильно понимаю, что есть две строки:
char str1[] = " 12, 15, -90, 2, 11"
char str2[] = "0, 89991, 2, 929, 15, 144"
и нужно за линейное время вывести инфу:
Общие числа:
2 , позиция в str1: 4, позиция в str2: 3
15 , позиция в str1: 2, позиция в str2: 5
так?
Не уверен, что эта задача решается за линейное время.
я тоже не уверен, поэтому и решил уточнить условие задачи
и нужно за линейное время вывести инфуда, верно. За O(n) - время и O(m) - памяти, где n, m - длинны строк, n>m, если быть точным
Решается.
Решение фстудею, а то я уже моск сломал.
я пытался рассуждать так:
если бы речь шла о массивах чисел размера x и y, то решение несложно получается сложности xlog(x).
теперь попробуем перейти от m и n к x и y.
гипотеза:
зачет того, что все числа разные в строке, то эта строка может содержать m/log(m) чисел.
получаем x ~ m/log(m y ~ n/log(n) и получаем итоговую сложность O(x*log(x = O(m).
но основательно свою идею додумать не смог еще.
если бы речь шла о массивах чисел размера x и y, то решение несложно получается сложности xlog(x).
теперь попробуем перейти от m и n к x и y.
гипотеза:
зачет того, что все числа разные в строке, то эта строка может содержать m/log(m) чисел.
получаем x ~ m/log(m y ~ n/log(n) и получаем итоговую сложность O(x*log(x = O(m).
но основательно свою идею додумать не смог еще.
Если учитываешь длину чисел, то операция сравнения никак не O(1 а O(log l где l — длина числа.
Поэтому не получится сложности O(x logx) для массивов.
Поэтому не получится сложности O(x logx) для массивов.
угу
это не единственная нестыковка в моих рассуждениях
так что я тоже не осилил задачку =\
зы: если l длина стринги, то сложность сравнения ее с такой же стрингой O(l) ? откуда логарифм?
это не единственная нестыковка в моих рассуждениях
так что я тоже не осилил задачку =\
зы: если l длина стринги, то сложность сравнения ее с такой же стрингой O(l) ? откуда логарифм?
для строки, которая накладывает ограничение по памяти, строим дерево, начало которого символизирует начало числа, от него идут ветки с цифрами, с которых начинаются числа. Для каждой цифры поддерево - вторые цифры в числах, начинающихся с этой цифры, и т.д. т.е для строки 1234,1235,6789 это будет
x - терминальный символ.
потом идем по второй строке, и сопоставляем сичтанные с неё числа. там ещё где-нибудь можно хранить позиции чисел. Как-то так. Сам когда-то на этой задаче срезался =/
x - терминальный символ.
потом идем по второй строке, и сопоставляем сичтанные с неё числа. там ещё где-нибудь можно хранить позиции чисел. Как-то так. Сам когда-то на этой задаче срезался =/
красивая задачка) теперь всех буду мучать )
)ну что какие задачи были? Кто что решил?
ps гоу все в abbyy. Отличная зп. Супер коллектив умных люде.
ps гоу все в abbyy. Отличная зп. Супер коллектив умных люде.
ps гоу все в abbyy. Отличная зп. Супер коллектив умных люде.Вот фигню только не надо пороть.
Вот фигню только не надо поротьИ с какой радости это фигня?
Это там студенты пашут 40 часов в неделю за 15 тыров на испытательном?
когда я искал работу, там платили 900 без опыта на испытательном.
когда я искал работу, там платили 900 без опыта на испытательномэто ближе к правде.
а за 15 вроде вообще без знания с++, не обязательно 40 часов, ты просто ботаешь аттестационные экзамены и сдаешь назначному преподу, а когда сдал, то зп повышают. Эти экзамены дадут сразу хорошую подготовку по с++/winapi/com.
Экзамены вроде сдают все, даже если с опытом.
Я, например, получаю там зп на одном уровне с лучшими зп людей, которые закончили вмк со мной и работаю прогерами + она вся белаа + соц пакет.
Хотя это все мое мнение, но мне там нравиться и я советую попробывать всем и если кого-то обидел, то сорри.
Аватарка тоже хороша =)
ух захвалили! 
я уволился оттуда после полутора месяцев работы из-за нездоровой хуйни которая там была (в плане коллектива) (правда это было в 2003 году)
чел с текущей работы работы работал там начальником проекта - тоже говорит, что херня полная во многих отношениях...
ЗЫ во избежание непонимания - я именно уволился, а не был уволен
чел с текущей работы работы работал там начальником проекта - тоже говорит, что херня полная во многих отношениях...
ЗЫ во избежание непонимания - я именно уволился, а не был уволен
И с какой радости это фигня?Потому что, зарплата там маленькая и люди никаким особенным умом не выделяются.
Я и сам туда заходил и мне лично говорили, что больше 2-х штук не светит, поскольку у них там типа грейды, и на больше 2к уже надо мощные заслуги иметь. И начальники, с которыми говорил особого впечатления не произвели, большей часть фигню пороли.
Моего друга еще оттуда уволили из-за оффисной войны между двумя начальниками. Он тоже жаловался на грейды и интриги вокруг них.
Но для студентов вариант, может, и неплохой. Критерий приема на работу довольно прозрачный - простые задачи и небольшие знания С++. Поработать годик и свалить - самое то.
Я лично получаю больше 2-х, при стаже менее года в abbyy ( ~ полтора года вообще на с++).
Насчет знаний вообще судить не имеет смысла не поработав и не пообщавщись с людьми. Но работая в нескольких местах до abbyy могу сказать, что тут люди умные и не занимаются производством поделак, как львиная доля наших ит контор.
Система грейдов вполне вменяемая, если ты действительно нормальный специалист. Хотя наверно можно без них, но формальность во многих вопросах может быть только на пользу.
У меня, например, грейд затянулся по необъяктивным причинам, но потом повышение зарплаты выплатили задним числом.
Наверно твоего друга уволили потомо-что он нихера не делал
. Я видел товарищей которые к нам приходят без знания с++ и т.д. и без желания учиться, а только с неимоверными запросами так как они мгушники. И когда начинаются экзамены, то не могут выдовить из себя нихера, так наверно такие уходят, а потом говорят мол виноват во всем начальник, который воевал с другим начальником .
Насчет знаний вообще судить не имеет смысла не поработав и не пообщавщись с людьми. Но работая в нескольких местах до abbyy могу сказать, что тут люди умные и не занимаются производством поделак, как львиная доля наших ит контор.
Система грейдов вполне вменяемая, если ты действительно нормальный специалист. Хотя наверно можно без них, но формальность во многих вопросах может быть только на пользу.
У меня, например, грейд затянулся по необъяктивным причинам, но потом повышение зарплаты выплатили задним числом.
Наверно твоего друга уволили потомо-что он нихера не делал
. Я видел товарищей которые к нам приходят без знания с++ и т.д. и без желания учиться, а только с неимоверными запросами так как они мгушники. И когда начинаются экзамены, то не могут выдовить из себя нихера, так наверно такие уходят, а потом говорят мол виноват во всем начальник, который воевал с другим начальником .Просто может невписался такое бывает 
.
.сначала мне мой непосредственный начальник сказал забить на экзамен и писать одну хуйню (2-3 недели заняло) а потом стал удивляться, чего это я экзамен не сдаю...
потом он и его начальник стали мне вешать лапшу на уши, при чем говорили взаимоисключающие вещи, что меня оч напрягло и я всех послал
PS еще порадовало, как начальник дал code convention в котором написано что нельзя юзать макросы и reinterpret_cast, а потом написал огромный макрос с адресами полей структуры и этими самыми кастами
потом он и его начальник стали мне вешать лапшу на уши, при чем говорили взаимоисключающие вещи, что меня оч напрягло и я всех послал
PS еще порадовало, как начальник дал code convention в котором написано что нельзя юзать макросы и reinterpret_cast, а потом написал огромный макрос с адресами полей структуры и этими самыми кастами
Моя мечта — чтобы сделали свободный аналог фаинридера и Абби сдохла.
Контора реально живёт на 2-3 технологиях распознавания. Живет потому что конкуренции нет никакой вообще, и все кому надо что-то распознать вынуждены иметь дело с Абби.
В Абби денег дохуя, это факт, но так как я не знаю никого из Абби, то не могу судить ни об умности коллектива, ни о зарплате. Сдохнуть желаю исключительно из нелюбви к 100%-виндузятникам.
Контора реально живёт на 2-3 технологиях распознавания. Живет потому что конкуренции нет никакой вообще, и все кому надо что-то распознать вынуждены иметь дело с Абби.
В Абби денег дохуя, это факт, но так как я не знаю никого из Абби, то не могу судить ни об умности коллектива, ни о зарплате. Сдохнуть желаю исключительно из нелюбви к 100%-виндузятникам.
Сдохнуть желаю исключительно из нелюбви к 100%-виндузятникам.Ну сдохни.
> Контора реально живёт на 2-3 технологиях распознавания.
подавляющее большинство контор живет вообще на одной убогой чужой технологии, и что?
> В Абби денег дохуя, это факт
Это не факт, это домысл. Абби - классический изучающийся у менеджеров пример фирмы, провалившей перспективный проект в Штатах: не хватило денег на раскрутку.
> из нелюбви к 100%-виндузятникам
ну я же говорил
подавляющее большинство контор живет вообще на одной убогой чужой технологии, и что?
> В Абби денег дохуя, это факт
Это не факт, это домысл. Абби - классический изучающийся у менеджеров пример фирмы, провалившей перспективный проект в Штатах: не хватило денег на раскрутку.
> из нелюбви к 100%-виндузятникам
ну я же говорил
В той самой инструкции написанно, что нельзя использовать такие вещи неопытными программистами так как они опасны и это неоспоримый факт.
мне кажется, пианист тотально не любит виндузятников не по той причине, о которой ты говорил.
так как они опасны и это неоспоримый фактХрабрый босс не зассал
Честно, я ничего об Абби не знаю. Объяснил почему не люблю — виндузятники-проприетарщики.
Хорошо распознают — это есть, но я ихними программами пользоваться не могу, мне банально жалко денег на покупку, и на моем компьютере их программы не работают.
Хорошо распознают — это есть, но я ихними программами пользоваться не могу, мне банально жалко денег на покупку, и на моем компьютере их программы не работают.
Я лично получаю больше 2-х, при стаже менее года в abbyy ( ~ полтора года вообще на с++).Ну ну
Насчет знаний вообще судить не имеет смысла не поработав и не пообщавщись с людьми. Но работая в нескольких местах до abbyy могу сказать, что тут люди умные и не занимаются производством поделак, как львиная доля наших ит контор.
Система грейдов вполне вменяемая, если ты действительно нормальный специалист. Хотя наверно можно без них, но формальность во многих вопросах может быть только на пользу.
У меня, например, грейд затянулся по необъяктивным причинам, но потом повышение зарплаты выплатили задним числом.
.
Ты поработай годика полтора-два, а уж потом втирай другим про рай в Абби. Сколько уже таких пионеров было - работают меньше года в фирме, а уже все знают, все понимают и на все ответ есть. Только потом куда-то сливаются.Ода грейдам тебя вообще не красит, сразу видно, что ты еще не знаешь, что все такие схемы - это инструмент не поощрения, а порабощения.
Наверно твоего друга уволили потомо-что он нихера не делал
Следует подавлять в себе склонность п**ть о том, о чем не имеешь понятия. Он раза в три дольше тебя там проработал.
Снала ты говоришь, что там получают все очень мало, я опровергаю, тут сразу новая притензия, мне кажется ты просто беспочвенно наезжаешь.
А если твоего кореша после 3-х лет проста так уволили, то он видимо совершенно не ценный сотрудник.
Я не говорил, что грейды это супер. Просто это не совсем и зло, формально ты всегда знаешь когда тебе поднимут зп. И к слову, в abbyy по статистике 80 % проходят с первого раза аттестацию.
Короче не одного довада против одну хуйню порешь.
подавляй
А если твоего кореша после 3-х лет проста так уволили, то он видимо совершенно не ценный сотрудник.
Я не говорил, что грейды это супер. Просто это не совсем и зло, формально ты всегда знаешь когда тебе поднимут зп. И к слову, в abbyy по статистике 80 % проходят с первого раза аттестацию.
Короче не одного довада против одну хуйню порешь.
Следует подавлять в себе склонность п**ть
подавляй
Мат. задачка - 100 заключенныхответ плз!
все - решил! но возможно есть другое решение.
напиши плз свое
но возможно есть другое решение.напиши плз свое
Про 100 заключенных.
Если известно, что изначально рычаг выключен:
Выбирают "счетчика".
Алгоритм действия счетчика:
если рычаг включен - выключить, прибавить к счетчику 1.
если выключен - ничего не делать.
если счетчик дошел до 99 - сказать что все побывали в комнате.
Алгоритм действия остальных:
если рычаг выключен - включаем и переходим в разряд "ничего не делающих"
если включен - ничего не делаем
Ничего не делающие, очевидно, ничего не делают.
Для случая, когда изначальное положение неизвестно - просто каждый должен дернуть не по разу, а по два. Когда счетчик дошел до 197-198 - все, все побывали.
Если известно, что изначально рычаг выключен:
Выбирают "счетчика".
Алгоритм действия счетчика:
если рычаг включен - выключить, прибавить к счетчику 1.
если выключен - ничего не делать.
если счетчик дошел до 99 - сказать что все побывали в комнате.
Алгоритм действия остальных:
если рычаг выключен - включаем и переходим в разряд "ничего не делающих"
если включен - ничего не делаем
Ничего не делающие, очевидно, ничего не делают.
Для случая, когда изначальное положение неизвестно - просто каждый должен дернуть не по разу, а по два. Когда счетчик дошел до 197-198 - все, все побывали.
Оставить комментарий
afo-aLLa1
Ежегодно 1-2 раза в год проводится олимпиада ABBYY по программированию. Имеется в виду разработка алгоритмов для решения конкретных задач, а не скоростное кодирование.Так вот, если у кого-то есть задачи с прошедших туров, please, выложите их здесь