yeputons's blog

Debugging graphs with ease: experimental Visual Studio plugin
By yeputons, history, 5 months ago, In English,

Hi everyone!

I'd like to present you a prototype of Visual Studio plugin which was developed by a student from my university as a coursework. Yielding floor to her:

GraphAlgorithmRenderer is an experimental Visual Studio extension for debugging and visualizing graph algorithms. It takes a description of graph nodes, edges and their properties, such as color and label, and renders a corresponding graph. The graph is refreshed automatically when you step in debugger. Graph config can be serialized to JSON and deserialized back.

Read more »

 
 
 
 
  • Vote: I like it
  • +142
  • Vote: I do not like it

Are Codeforces pages sometimes rendered blank during fast browsing with Firefox?
By yeputons, history, 3 years ago, translation, In English,

In the last few weeks or even months I've noticed that my use scenario for Codeforces became broken. Here it is:

  1. Open the main page.
  2. Scan "Recent actions" for interesting posts.
  3. Open all of them in new tabs with mouse.
  4. Go and read posts and comments.

The problem is: approximately half of 5-10 opened tabs is rendered empty. Empty in the following sense: there is tab's title, one can see source HTML (e.g. the page is loaded), but the page itself is completely blank. DOM tree contains something (not too much), but <body>'s height is zero:

For comparison, here is the same page, rendered correctly (note that now we have several new scripts and a <div id="body">):

Steps to reproduce:

  1. Take Firefox on Windows. My version is 52.0.2 (32 bit). I was unable to reproduce the problem in Chrome.
  2. Take arbitrary ISP — I was able to reproduce the problem both directly and via encrypted proxy.
  3. You don't have to log in — I was able to reproduce the problem in a fresh Firefox session (firefox -P -no-remote and create a new profile; this guarantees no strange cookies on external websites). However, I was unable to reproduce the problem in "Private Browsing".
  4. Open the main Codeforces' page.
  5. Hold down Ctrl and click link to an arbitrary user's profile from "Top rated". Click it fast: 10-20 times during several seconds.
  6. Check all tabs one-by-one:
  • Expectation: after loading indicator stops spinning, page is rendered and I can see Codeforces' logo and user's profile.
  • Reality: some tabs, even after loading indicator disappears, remain completely blank.

I suspect that this is caused by some cookies set by either Codeforces or its analytics/like scripts (e.g. VK/Facebook).

Read more »

 
 
 
 
  • Vote: I like it
  • +123
  • Vote: I do not like it

Interning/working at Samsung?
By yeputons, history, 3 years ago, translation, In English,

Hello everyone.

Is there anybody who interviewed/interned/worked at Samsung (Seoul or any other office) for software engineering-related positions? I think it's more probable to find such people among All-Siberian Open Olympiad in Programming participants, as Samsung sponsored it for some time.

If there is, would you mind sharing your experience or thoughts? Extra bonus points if you compare it with your European/American experience.

Read more »

 
 
 
 
  • Vote: I like it
  • +73
  • Vote: I do not like it

Online judge with IOI problem went public
By yeputons, 3 years ago, In English,

Hello everyone.

Two years ago there was a post titled "Submitting IOI problems" and my comment there. I offered everyone to contact me via PM on Codeforces to get the access and be able to solve problems from past IOIs (starting with IOI 2003). What was important here is that PavelKunyavskiy and me took effort and made the system as similar to what was used on particular IOI as we could, including:

  1. Original tests from archives
  2. Tests grouping and correct subtasks scoring where applicable — you won't get 54 points if there are subtasks for 40 and 60 points — just like on IOI.
  3. Interactive problems with interactive I/O (say, "Aliens" from IOI 2007 or "Maintain" from IOI 2003)
  4. Partial scoring where you can get only a fraction of points per test, like "Reverse" from IOI 2003 or "Hotter Colder" from IOI 2010.
  5. "Encode-decode" problems, where your solution is executed several times in separate processes, like "Parrots" from IOI 2011.
  6. Open test problems where you submit answers only instead of solution, like "Forbidden subgraph" from IOI 2006 or "Maze" from IOI 2010.
  7. Graders like on IOI 2010 and further. Unfortunately, the "Black box" problem from IOI 2006 was also implemented as a problem with graders instead of running a real "black box" on our server which you can access remotely.
  8. "Odometer" problem from IOI 2012 where you had to submit a program on a specially invented language.

So far it was a closed judge available upon request only. As far as I remember, I've granted access to everyone who've asked — 150+ persons. Time flows and the judge eventually migrated to Yandex.Contest (the system used for Yandex.Algorithm) with help of lperovskaya. It still supports all of the above, but the registration is open for everyone and IOI 2015 is available there. Feel free to join!

Unfortunately, it's still a beta version and there are still some issues: no problem statements are visible in the interface, some labels may be in Russian only and graders for Pascal and Java may be non-working in some problems (C++ should work everywhere, though). Note that we use slightly different conventions for graders from what was on IOI (for the sake of consistency among all IOIs). You can download an archive with example solutions by clicking on the "Download" button right to the "Jury messages" link. If the button is not here, there is no archive with example solutions yet, but the format of graders should be very similar among all problems and we didn't change signatures of functions from IOI, so it should be fairly easy to "restore" the format.

I hope that will help all of you who are preparing for upcoming IOIs! By the way, if you have not advanced to IOI this year, I would highly recommend you to avoid reading several IOIs so you will have good problems preparing for IOI next year. It's hard to find good IOI-like problems.

Read more »

 
 
 
 
  • Vote: I like it
  • +352
  • Vote: I do not like it

What is the story behind your username?
By yeputons, 4 years ago, In English,

I've just discovered this question on Quora: What is the story behind your username at CodeForces?. I guess it'd be pretty interesting to hear stories from top participants. For instance, my handle's history is already described there.

This blog is dedicated to everyone who don't have Quora account, so you can share your histories and comments here.

I personally would love to hear stories from tourist, rng_58 and WJMZBMR from current top-10.

Read more »

 
 
 
 
  • Vote: I like it
  • +508
  • Vote: I do not like it

APIO 2011 test data and reference solutions
By yeputons, 5 years ago, In English,

Hello everyone.

Right now I'm settings up APIO 2011 contest for training purposes. It seems to me like test data (answers, to be precise) in problems 'Guess My Word' and 'Table Coloring' are broken. I have three solutions from three different people for the latter problem and they produce the same answers for tests 10, 12, 14, 16 and 18 — zero, while the reference answer is non-zero. For the 'Guess my Word' problem I have two solutions: one fast and one brute-force with memoization which I wrote by myself several minutes ago. These two solutions produce same output on tests 1-16, but they both produce 'No' on some test cases where official test data says 'Yes'.

Does anyone have information about validity of this test data or some solutions which I can test with too?

Thank you.

Read more »

 
 
 
 
  • Vote: I like it
  • +17
  • Vote: I do not like it

Testexe for testing systems: say 'no' to extra large static arrays!
By yeputons, 5 years ago, translation, In English,

Everyone knows a problem with native executables on Windows: if it tries to allocate very large static arrays (or something similar that causes problems during the loading), then the testing system may mark the submission as 'it killed our system' and report nothing to the participant. Say, in Testsys it caused Failed To Test (and no feedback to the participant), on Codeforces it caused Denial of Judgement, and PCMS2 still has this problem. Example submission:

int data[(int)2.1e9 / sizeof(int)];
main() {}

If one is familiar with process creation on Windows, it's obvious what to do: try to run the solution right after compilation and report Compilation Error with report in case of invalid executable. It looks like noone except me have the time to do this and here is my utility, which already serves on Codeforces. If you have your own testing system, you're welcome to run this application after compilation to check an executable for validness (you can just copy-paste the code directly into your judging module, too). After that you will be able to report incidents to the user and drop hints about extra large arrays existance.

No user code is being running during the check: process is fully suspended by the OS after successfull loading and before any instructions are run (it's what the CREATE_SUSPENDED parameter is responsible for).

Read more »

 
 
 
 
  • Vote: I like it
  • +107
  • Vote: I do not like it

Стратегия и тактика на контестах: запись лекции
By yeputons, 6 years ago, In Russian,

Всем добрый день.

На прошлой неделе в Санкт-Петербурге начались традиционные учебно-тренировочные сборы школьников перед Всероссийской олимпиадой. Когда-то они выполняли отборочную роль, сейчас это лишь тренировки и учёба вместо школы. В пятницу я решил повторить свою прошлогоднюю лекцию про то, как вести себя на контестах и что может помочь/мешать решать задачи/набирать баллы, кроме знания алгоритмов. Алгоритмы рассказывают везде: и на e-maxx.ru, и в ЛКШ, и на Хабре, и на Codeforces. А вот никакой общедоступной информации на тему "а как организовать себя на контесте" я не видел. Когда я был школьником, разве что иногда кто-нибудь из преподавателей мимолётом замечал, что неплохо бы читать все задачи в первые минуты и писать заглушки когда-нибудь в течение контеста, потому что "напишете заглушки по каждой из шести задач — будет второй диплом на Всеросе".

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

Read more »

 
 
 
 
  • Vote: I like it
  • +281
  • Vote: I do not like it

Поддержка задач марафонского типа с динамической системой оценки в тестирующих системах: предложения по стандартизации
By yeputons, 7 years ago, In Russian,

В этом посте речь пойдёт о тестировании еще одного типа нестандартных задач. Они иногда встречаются на Всероссийских сборах школьников, а также на каждом Codechef Long Contest. Я говорю о неточных задачах, в которых участник оценивается относительно лучшего в некотором смысле решения среди жюри и всех участников. Обычно тесты оцениваются независимо, а оценка за тест — некая функция от "хорошести" решения участника и лучшего результата на этом тесте.

На данный момент поддержка таких задач в известных мне системах (Testsys, PCMS2, eJudge) возможна лишь костылём. Например, используется ровно один judge/invoker и на нём же в специальных файликах хранятся текущие лучшие результаты по каждому из тестов. После конца контеста требуется перетестировать все посылки, чтобы каждая была оценена исходя из глобально лучшего ответа, а не лучшего на момент посылки. Конечно, вместо этого можно скриптами подправить логи тестирования, но этот костыль тоже не блещет красотой.

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

Итак, предложения (спасибо Gassa за помощь при формулировке и разработке):

  1. Можно считать, что для выставления оценки за тест достаточно некоторой информации об ответе, меньшей, чем сам ответ (назовём её целевой функцией). Я не видел ни одной задачи, где это не было бы числом (например, длина пути коммивояжёра). Тем не менее, "с заделом на будущее" можно считать эту информацию последовательностью чисел и строк (сравниваются лексикографически). Последовательности также сравниваются лексикографически. Что при этом считать лучшим ответом — параметр задачи (например, надо минимизировать первый элемент, а при равенстве — максимизировать второй и т.д.). Погрешности сравнения вещественных чисел выставляются как параметры задачи, возможно, с некоторыми умолчаниями.

  2. Хочется избавиться от необходимости перетестирования/ручной правки логов в конце/процессе контеста. Для этого предлагается отделить функциональность выставления баллов за тест от чекера. На чекер ложится обязанность выставить WA/PE/OK (вердикт PC/Partially Correct убирается) и выдать в комментарии значение целевой функции. Разумеется, не хочется терять комментарий в его стандартном смысле, поэтому предлагаю выводить в формате <комментарий><перевод строки><значение целевой функции>. Например: Looks good\n123 abacaba 44.5 При этом чекеру совершенно незачем знать текущий лучший ответ, и пропадает необходимость передавать его на тестирующую машину.

  3. Таким образом, тестирующая система для получения фактического балла за тест (мне кажется, лучше выдавать процент от максимально возможного балла за тест, нежели сами баллы) должна запустить программу выставления баллов (назову её valuer по аналогии с ejudge) и передать ей на вход значение целевой функции участника и лучшее значение целевой функции.

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

  5. Исчезает необходимость перетестирования в конце контеста: достаточно еще раз запустить valuer для каждой посылки.

Впрочем, у меня остались некоторые неразрешённые вопросы:

  1. Для выставления баллов за решение в текущей модели требуется довольно дорогостоящий запуск отдельного процесса. Мне не хочется запускать "чужой код" вне песочницы, поэтому тратится еще и время тестирующей машины. Возможное решение: использовать для написания valuer'а некоторого популярного/простого скриптового языка (например, EcmaScript/JavaScript или Lua), который легко проинтерпретировать и ограничить в правах. Тогда можно будет запускать его хоть после каждого сабмита и показывать результаты онлайн.

  2. Если брать скриптовой язык — то какой? Хотелось бы выбрать один на всех. EcmaScript, как мне кажется, более известен и больше похож на C/C++/Java. С другой стороны, существующие интерпретаторы EcmaScript довольно громоздки. Lua же предоставляет легковесный интерпретатор с привязками ко многим языкам (C++, Delphi, Java, Python), однако он не слишком популярен и использует другой синтаксис (например, end вместо фигурных скобок, комментарии двойными дефисами и прочее). В остальном языки довольно схожи.

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

UPD: выложил пример чекера и valuer'а на C++ для задачи о коммивояжёре. Также есть пример valuer'а на javascript.

В конфиг testsys'а для такой задачи могут добавиться такие строчки:

# Целевая функция состоит ровно из одного токена, который надо минимизировать
# В случае большего количества токенов строка может выглядеть как "<<><"
DynamicScoringComparator = "<"; 
# DynamicScoringAbsoluteEps = 0.000000001; # По умолчанию
# DynamicScoringRelativeEps = 0.000000001; # По умолчанию
DynamicScoringValuer = $probdir\valuer.exe

Read more »

 
 
 
 
  • Vote: I like it
  • +63
  • Vote: I do not like it

Интерактивные задачи: решение проблем, поиск дополнительных проблем
By yeputons, 7 years ago, In Russian,

На Codeforces уже поднимались темы об интерактивных задачах (первая и вторая).

В этой теме мне хочется поднять вопрос о вердиктах в интерактивных задачах (с которыми довольно часто возникают проблемы) и предложить дополнение к алгоритму тестирования, которое позволит выставлять их практически не завися от прихотей ОС (проблема, поднятая NALP в этой теме). Также будет показан код под Windows, реализующий это дополнение.

В самом начале хочется спросить: а как, вообще говоря, выставляются вердикты в обычных задачах? Базовой аксиомой является "сначала решение корректно завершается, а потом проверяется ответ". Таким образом, даже если решение вывело (не)корректный ответ в выходной файл, а потом завершилось с ненулевым кодом возврата (либо зависло), система не станет это проверять, а просто скажет RTE/TL.

В интерактивных задачах эта аксиома не работает. Например, если в процессе какой-то игры участник выводит несуществующий ход, продолжать взаимодействие не имеет смысла и надо выдать WA. Я предлагаю взять за аксиому следующее: "в первый момент времени, когда стало возможным выдать вердикт, отличный от OK, выполнение должно прерываться с очевидным вердиктом". Рассмотрим несколько примеров:

  1. Участник вывел неверный ход и ждёт ответа чекера. Это очевидный WA.

  2. Участник вывел неверный ход, понял, что сам дурак, и завершился с RTE.

  3. Участник в процессе вывода вышел за границу массива, вывел бред и завершился с RTE.

Я утверждаю, что ситуации 2 и 3 в принципе неотличимы. Проверяющая система не может однозначно определить, вывел ли участник бред из-за RTE или же он случился строго после. Поэтому выставляется вердикт WA, который случился в момент вывода в stdout, что произошло раньше, чем RTE, который случился в момент завершения программы. В частности, при изменении задачи на интерактивную, могут поменяться получаемые вердикты: любой из них (TL/RTE/ML) может поменяться на WA. Это довольно неинтуитивно после стандартных задач. В качестве альтернативы после завершения интерактора можно некоторое время (до IL/TL) ожидать падения решения и, если оно произойдёт, поставить RTE. Это будет чуть ближе к стандартным задачам в том смысле, что в случае падения решение не будет проверяться его последний ответ. Это место еще стоит обсудить.

Также хочется отметить сложность в отличии вердиктов Idleness Limit Exceeded и WA/PE. Первый легко получить, если забыть fflush. Однако представим себе ситуацию, в которой участник по каким-то причинам вывел четыре числа вместо пяти и начал ждать ответа интерактора. В этом случае налицо нарушение протокола взаимодействия и хочется выставить WA/PE. Однако с точки зрения тестирующей системы ситуации отличаются только наличием вывода "в последнее время", что непонятно, как формализовать. Есть предложения? Мне лично хочется оставить как есть и ничего не придумывать.

Теперь перейдём к решению старых проблем. В первой теме MikeMirzayanov предложил алгоритм тестирования задач. Вкратце:

  1. Параллельно с решением запускается интерактор, который имеет доступ к тесту (и ответу, если такой есть) и взаимодействует с решением. В случае нарушения протокола/заведомо неверного ответа он завершает работу. Если всё в порядке, то отдельно запускается чекер, который проверяет ответ, выведенный интерактором в файл вывода (в некоторых задачах чекер пустой и несодержателен — всё проверяет интерактор).

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

  3. Если первым завершается интерактор, то либо сразу ставится вердикт WA/PE, либо ожидается корректное завершение решения и запускается чекер.

В отдельном посте NALP указал на довольно существенный недостаток системы в реальных условиях: стандартные средства ОС не дают возможности точно определить, какой процесс завершился первым (да и не очень понятно, что это такое в многозадачной среде). Поэтому с точки зрения проверяющей системы ситуации "решение вывело WA, интерактор закрылся, решение упало с RTE, так как не смогло считать" и "решение упало, интерактор сказал WA, так как поток закрылся" неотличимы: решение завершилось некорректно, интерактор завершился с кодом возврата WA.

Теперь я хочу предложить точное и стабильное решение последней проблемы. Для этого сделаю два предположения:

  1. При попытке чтения оба процесса (не поток, а весь процесс) полностью блокируются. Обычно использование многопоточности на олимпиадах либо запрещено, либо бессмысленно из-за подсчёта процессорного времени. Ситуации, в которой потребуется неблокирующий ввод в задаче, я представить также не могу, так что я этот пункт считаю покрывающим вообще все задачи.

  2. Даже после выставление вердикта ОК, интерактор не завершается, пока не получит EOF, чтобы проверить, что участник не вывел что-то лишнее.

Решение проблемы выставления вердикта состоит в следующем: при создании пайпов для взаимодействия решений, тестирующая система не закрывает свой хэндл на вывод в пайп. Таким образом, у каждого пайпа образуется не два, а три конца — по одному у решения, у интерактора и у системы. При завершении любого из двух процессов, пайп не закрывается и решение/интерактор не получают EOF, пока этого не захочет тестирующая система.

Итого, алгоритм получается такой:

  1. Запустить параллельно интерактор и решение с замкнутыми друг на друга вводом-выводом. При этом необходимо сохранить открытые хэндлы в тестирующей системе.

  2. Пусть первым завершился интерактор. Так как он должен был ждать EOF в случае OK, то он должен был завешиться с вердиктом WA, который мы и выставляем (либо, как альтернативное решение, надо подождать и проверить отсутсвие RTE).

  3. Значит, первым завершилось решение. Если решение завершилось корректно, мы закрываем хэндлы, интерактор получает EOF и завершается с некоторым вердиктом, который мы возвращаем как результат проверки. Если же оно завершилось некорректно, то возможно два варианта: либо это произошло вскоре после получения WA (и интерактор должен скоро завершиться), либо нет. Чтобы отличить WA/RTE в этой ситуации, надо проверить, что интерактор не ждёт ввода (т.е., тратит процессорное время). Если ждёт — ставим RTE, если делает что-то осмысленное — ждём его завершения и ставим вердикт.

Эта идея осуществлена в написанной мной для демонстрации утилите, которую можно скачать здесь. Она следует концепции "выставляем то, что случилось раньше" и не ждёт RTE после завершения интерактора с WA, зато ожидает завершения интерактора в случае падения решения.

Прошу высказать свои мысли по поводу дополненной схемы, возможности её реализации в других ОС, а также любую критику по поводу высказанных мыслей.

Read more »

 
 
 
 
  • Vote: I like it
  • +58
  • Vote: I do not like it

APIO 2012’s results
By yeputons, 7 years ago, In English,

Does anyone know when the results of APIO 2012 will appear? Results of open contest were published several days ago, test data is available for two days already, but results are still 'TBA'.

Read more »

 
 
 
 
  • Vote: I like it
  • +16
  • Vote: I do not like it

USACO 2012 March
By yeputons, 8 years ago, In Russian,

Довольно странно, что никто не создал пост для обсуждения. Сейчас заканчивается мартовский раунд USACO 2012. Желающие еще могут начать участие в течениие целых 18.5 часов. Предлагаю после окончания обсуждать тут задачи.

Read more »

 
 
 
 
  • Vote: I like it
  • +16
  • Vote: I do not like it

Userscript for new comments walking in Codeforces' blog
By yeputons, 8 years ago, translation, In English,
Hi everybody.
I'm tired for scrolling page to find a new comment and don't like "Recent actions". So, I wrote a userscript, which adds a "new comments navigate buttons" in the right of the window.
It works in Firefox (you need GreaseMonkey plugin) and Chrome. It also should work in Opera and some other browsers - I don't use any specific API.

You can install it here. If the only thing you see is javascript code it means that your browser doesn't support userscripts

You can report bugs, ideas and suggestions here.

UPD: now you can view parent comment if you hover over the "^" link. This link still works.

UPD2: repository on GitHub is available.

Read more »

 
 
 
 
  • Vote: I like it
  • +165
  • Vote: I do not like it

Дорешивание прошлогоднего региона и заочного этапа Открытой олимпиады.
By yeputons, 8 years ago, In Russian,

На Росолимпе появились тесты к прошлогоднему региону. Заодно выложил заочный этап заочки того же года.


Всё там же, где обычно: http://yeputons.net/tsweb/. Если кому-нибудь еще надо, то регистрируемся и сдаём. Можно переключаться между контестами ("List of all contests"). Система следующая: вы получаете результат выполнения программы на тестах из примера (и на online-группе, если такая есть), и, если хотите, можете открыть полные детальные результаты (как на IOI в этом году, кнопка "Use token"). Если программа не прошла примеры - она не тестируется вообще.


Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

Tutorial for school regional team contest of Saratov
By yeputons, 8 years ago, translation, In English,
You can leave your questions, suggestions and more beautiful in comments.

Problem A. Elevator


You can either check all four cases or notice, that if we consider front/back equal to 0/1 (b) and decrease a by 1, then a XOR b became the answer (0/1). Time and memory consumption - O(1).



Problem B. Quiz League


Just write one loop: while kth question has already been asked, increase k by one and if k > n let k = 1. Time and memory consumpiton - O(n).



Problem C. Winnie-the-Pooh and honey


One of the possible solutions is direct emulation. Winnie won't do more than 3n iterations (because he can use each jar more than three times). You can emulate each iteration in O(n) (just find maximum in array). Summary time - O(n2) ≈ 104 operations, memory consumption - O(n)

There is another shorter solution: let's notice that order of jars doesn't matter. Let's see how much honey from each jar will be eaten by Winnie and how much will be left to Piglet. If ai ≥ 3k then Winnie will leave ai - 3k kg of honey to Piglet. If ai < 3k then he'll leave only kg. Now solution is one loop. Time and memory consumption is O(n).

Read more »

 
 
 
 
  • Vote: I like it
  • +50
  • Vote: I do not like it

TopCoder Single Round Match 521
By yeputons, 8 years ago, In Russian,

Сегодня, в четверг, 13 октября 2011 года в 15:02 по Москве состоится 521-й TopCoder Single Round Match (время в других городах).

Read more »

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

Финал Яндекс.Алгоритм: разбор A-B
By yeputons, 8 years ago, In Russian,

Так как остальные задачи я не то что не пытался решить, а даже не читал, публикую те решения, которые узнал

Задача A. Домино

Для начала поймём, что на квадраты 2x2 всё поле разбивается однозначно и это можно сделать жадным алгоритмом. Теперь у нас есть 14 квадратов. Далее можно сделать необязательное преобразование, от которого лично мне стало жить проще: построим граф на 14 вершинах, ребро между вершинами будет тогда и только тогда, когда у соответствующих квадратов есть общая доминошка. В принципе, это даже какой-то оптимайз по времени, но не суть важно.
Теперь задача такова: есть граф на 14 вершинах, надо раскрасить их в цвета от 0 до 6 так, чтобы все рёбра были разными (два ребра одинаковы, если цвета концов совпадают). Утверждается, что решение - перебор. Перебираем цвет первой, второй, третьей, ..., 14й вершины, на каждом шаге проверяем, что у нас не появилось ребро той же расцветки, что уже было (естесственно, делаем это массивом bool'ов). После чего останется вывести ответ и какую-нибудь раскраску.
Однако это решение может не зайти по времени. Остался один мощный оптимайз. Заметим, что, по сути, разницы между цветами нет. Значит, цвета в раскраске можно переставлять как угодно. Теперь научимся считать количество ответов с точностью до перестановок цветов, а в конце домножим его на 7!=5040. Это просто: достаточно ввести условие, что цвет очередной вершины либо встречался раньше, либо идет сразу после максимального использованного цвета. Например, после цветов 0 1 2 1 0 2 могут идти только цвета 0..3.
Чтобы уверовать в то, что это решение зайдёт, можно грубо оценить количество ответов. Каждая вершина раскрашена в один из семи цветов, каждый цвет встречается ровно два раза, плюс мы не учитываем различные перестановки. Итого получается , что, очевидно даже при отсечении на последнем шаге рекурсии, влезает в TL.

Задача B. Надмножество

Задача была немножко (или множко?) идейной. Одним из возможных решений является разделить множество точек пополам веритикальной прямой (если не получается ровно, та так, чтобы разница была минимальна), решить задачу рекурсивно для двух половин, и добавить на разделяющую прямую точки со всеми встречающимися в ответах для половин y'ами.
Докажем корректность. Если точки лежат в одной половине, всё мы верим, что верно решили подзадачу. Если же они лежат в разных половинах, то их bounding box пересекает нашу прямую, и в точках пересечения выделенные точки есть (посльку их y'и встречались слева и справа).

Прошу сообщество рассказать остальные задачи в комментариях

Read more »

 
 
 
 
  • Vote: I like it
  • +15
  • Vote: I do not like it

Статистика по "полезности" тестов
By yeputons, 8 years ago, In Russian,
Добрый всем день.
Недавно меня заинтересовал вопрос, и хочу с ним обратиться к тем, кто имеет доступ к логам проверки решений - на скольки процентов тестов обычно хоть кто-то валится? На каждом тесте, на половине, на каких-то трёх?

Read more »

 
 
 
 
  • Vote: I like it
  • +15
  • Vote: I do not like it

Краткие правила Google Code Jam - еще не поздно принять участие!
By yeputons, 8 years ago, In Russian,

Google Code Jam - очередное всемирное соревнование по спортивному программированию (язык - только английский). Для участния нужно иметь Google-аккаунт, зарегистрироваться и принять участие в квалификационном раунде, который продлится до трёх часов ночи (по Москве) сегодняшнего дня.

Итак, правила:

  1. Есть несколько задач, тесты открытые (с мультитестом) - Вам нужно прислать в систему ответ и программу, если жюри усомнится в том, что Вы играли честно. Допустимые языки - любые. В каждой задаче есть две подзадачи: Small input и Large input. Каждая из них оценивается по своей системе и может быть либо решена полностью (тогда Вы получаете некоторое количество баллов), либо не решена вообще (получаете ноль). Участники ранжируются по количеству баллов (больше - лучше) и штрафному времени, именно в таком порядке.
  2. Small input. Ограничения небольшие. Для того, чтобы попробовать сдать подзадачу, надо нажать соответствующую кнопку. Вам выскочит окно с запросом на скачивание файла - это тесты. После нажатия на кнопку есть 4 минуты для того, чтобы запустить программу и загрузить в систему ответ и код. Главное, на самом деле - ответ. После загрузки есть три вердикта:
    1. Rejected. Вы послали какую-то хрень. Ближайший аналог - PE. Например, не совпадает количество тестов. Эта посылка везде игнорируется. До окончания 4х минут Вы можете попробовать еще раз.
    2. Incorrect. На каком-то из тестов ответ неправильный. Таймер сбрасывается и, чтобы попробовать еще раз, надо брать еще одну попытку.
    3. Correct. На всех тестах ответ верный - Вы точно получили свои баллы за подзадачу. Всё, больше её посылать нельзя вообще - кнопка исчезает.
    4. Если вы не успели за 4 минуты получить свой Correct, считается, что Вы получили Incorrect. А если Вы получили за попытку Incorrect, то можно попробовать еще раз - 4 минуты пойдут заново, но Вам выдадут другой тест.
  3. Large input. Подзадачу можно посылать только после получения Correсt на Small input. Тут всё почти аналогично, но у вас есть только одна, и только одна 8-минутная попытка сдачи. При приёме в систему вы можете получить только Rejected (аналогичный предыдущему), либо Submitted - что означает, что претензий нет. Правильный ответ, или нет - Вы узнаете только по окончании тура. За эти 8 минут можно перепослать сколько угодно раз - засчитывается последняя посылка с вердиктом Submitted. 
  4. Штрафное время. Считается как время последней посылки (по всем задачам), которая принесла Вам баллы (Correct на Small input или Submitted на Large input) плюс 4 минуты за каждый Incorrect в Small input (опять же, по всем задачам).
  5. Вопросы. Во время раунда можно задавать вопросы при помощи кнопки Ask a question под списком задач. Также можно, если Вы послали не тот код на Large input, попросить жюри перепослать (перепослать ответ невозможно, даже если попросить). Впрочем, подчеркивается, что не стоит злоупотреблять этой возможностью.
  6. FAQ.
  7. Квалификационный тур. В нём обязательно надо принять участие - задачки довольно простые. Собственно, без этого Вас не пустят дальше. Для прохода в Online Round 1 требуется набрать хотя бы 25 баллов (см. список заданных вопросов в контесте), что меньше, чем суммарный балл по всем Small Input. То есть Вы практически сразу знаете, прошли Вы, или нет.
P.S. Большое спасибо Zlobober'у за ответы вот в этой теме.

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

Быстрое умножение многочленов при помощи преобразования Фурье — это просто
By yeputons, 8 years ago, In Russian,

Добрый вечер.
Пару дней назад опубликовал статью на Хабре про БПФ. Постарался объяснить и доказать всё без матриц (как на e-maxx), потому что не умею с ними еще работать на интуитивном уровне. Там точно также есть код и оптимизации (кстати, одной очень важной - прекалк корней, на e-maxx нет).
Если кому-нибудь помогло разобраться - буду рад.

Read more »

 
 
 
 
  • Vote: I like it
  • +28
  • Vote: I do not like it

Google CodeJam - правила (есть вопрос)
By yeputons, 8 years ago, In Russian,
Добрый вечер.
В связи с тем, что через некоторое время начинается квалификационный раунд Google CodeJam, хотелось бы прояснить несколько непоняток относительно правил.

Как я понял, каждая задача состоит из двух подзадача: Small Input и Large Input. Вторую можно решать только после первой. Каждая даёт сколько-то очков.

Для решения Small Input качаем тест (с этого момента пошёл 4-х минутный таймер), запускаем на нём наш код, отсылаем в систему сначала ответ (получаем сразу либо Rejected - ботву послали, либо Correct - всё ок, либо Incorrect - вывел неправильный ответ), потом код, который этот ответ сгенерировал. Если не получили Correct за 4 минуты, считается как Incorrect. После этого можно попробовать еще раз, но уже с другим тестом. Попыток много. Вопрос: сбрасывается ли после получения Incorrect таймер (т.е., можно ли исправить баг и послать другой ответ на тот же тест за эти 4 минуты)?.

Далее. Large Input. Тут у нас одна 8-и минутная попытка (опять качаем тест), решения получают Correct/Incorrect в конце контеста, Rejected - сразу. Считается последняя попытка, которая не-Rejected.

Участники ранжируются по сумме набранных баллов, при равенстве - по штрафному времени, которое равно "время последней Correct-посылки/не-Rejected посылки по Large input" плюс количество Incorrect попыток * 4.

И, да, в течение раунда можно попробовать обратиться к жюри, если послал не тот код на Large input. Ответ перепосылать нельзя. Также можно спрашивать по условиям при помощи "Ask question".

Вопрос два: всё ли я правильно понял?

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

Задача о синхронизвации времени и задача о системе неравенств
By yeputons, 8 years ago, In Russian,

Вопрос: что есть сабж?
Откуда взял: книжка, которую наказали купить и составить по ней план теорподготовки к IOI.

Read more »

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

Codeforces Beta Round #71 - разбор (перевод A-D)
By yeputons, 8 years ago, In Russian,

Задача A. Игра в автобусе (автор - rng_58)

В этой задаче прекрасно работает симуляция "в лоб" - нам прямым текстом сказано, как ходят игроки. Лиса Кейл играет по следующей стратегии: если есть хотя бы две монеты по 100 йен и две монеты по 10 йен, она берёт их. Иначе, если есть хотя бы одна монета по 100 йен и 12 монет по 10 - она забирает их. В противном случае она берет 22 монеты по 10 йен. Если ей это не удаётся - выигрывает Ханако. Кролик поступает точно также, но в обратном порядке. Сложность решения - O(x+y).

Задача B. Разноцветное поле (автор - ir5)

Решение, использующее массив NxM получает TL/ML, и, разумеется, мы не можем решать задачу "в лоб". Так как и запросов, и безжизненных клеток не более 1000, нам достаточно научиться отвечать на каждый запрос за время O(K).
Пусть (a, b) - клетка из очередного запроса. Является ли она безжизненной, или нет - решит один цикл for по входным данным.
Итак, мы знаем, что на этой клетке что-то растёт. Пусть I - суммарное число клеток перед (a, b), а J - количество безжизненных клеток перед (a, b). Тогда ответ определяется значением (I-J) mod 3 (где 0 => "Carrots", 1 => "Kiwis", 2 => "Grapes"). Путем несложной математики можно понять, что I=(a-1)M+(b-1) (первое слагаемое - это количество клеток в предыдущих строках, а второе - количество предыдущих клеток в текущей строке), а величину J можно опять же подсчитать циклом for за O(K).
Получаем решение за O(TK), где T - количество запросов.

Задача C. Скучные строки (автор - ir5)

Мы можем представить каждую подстроку в s, совпадающую с какой-либо скучной строкой, как "запрещённый отрезок". Таких кандидатов в плохие отрезки для каждой из bi порядка O(n), поэтому мы можем подсчитать их все за O(|s|· n· |bi|) (да, тут не требуется никаких специальных алгоритмов, например, КМП).
Теперь мы можем переписать задачу по-другому: дано не более 106 запрещенных отрезков, найти отрезок, который не содержит полностью ни один из запрещённых.

Давайте подсчитаем величину right[i] - минимальная правая граница среди запрещенных интервалов с левой границей в i. Если таких интервалов нет, положим right[i]=|s|.

Теперь давайте переберём начало ответа, начиная с |s| и до 0. Вначале ответ - пустая строка. Пусть ответ для предыдщего начала - подстрока с i+1 до j. Тогда, если right[i]>j, то мы можем спокойно приписать один символ слева и ответ увеличивается на 1 - подстрока с i до j. Если же right[i]<=j, то ответ не может быть дальше, чем до right[i]-1, в противном случае мы полностью покроем "плохой отрезок". Таким образом, мы пробежимся по всем возможным началам ответов за O(|s|).

Итого время работы - O(|s|· n· |bi|).

Задача D. Кодовый замок (автор - rng_58)

Давайте слегка переформулируем состояние замка: определим массив bi следующим образом: bi = 0, если панели i и i + 1 находятся в одинаковом состоянии и bi = 1 в противном случае. Положим, что панели 0 и n + 1 выключены (OFF). Если Кейл изменяет состояние панелей на отрезке с x до x+a-1 (включительно), то в массиве b изменяются значения bx и bx + a:

Задача D'.
У Вас есть массив bi. Не более 20 (=2k) элементов - единички. За каждый ход Вы можете изменить значения в bx и bx + a, где a - элемент ai и 0 ≤ x ≤ n - a. Определите минимальное количество ходов, требуемое для обнуления массива (мы просто "перевернули" порядок действий).

Понятно, что порядок ходов не важен. Также понятно, что если массив еще не обнулён, то есть такой индекс x, что bx = 1, и нам придётся походить, задев этот индекс, хотя бы один раз. Давайте следаем этот ход первым. Далее применим аналогичное рассуждение и получим, что на каждом ходу хотя бы одно из двух чисел bx и bx + a - единица.

Задача D''.
Теперь давайте построим граф с вершинами от 0 до n+1. Ребро между двумя вершинами v1 и v2 будет в том, и только том случае, если |v1 - v2| - элемент массива ai (то есть, мы можем сделать ход bv1 и bv2. Также изначально есть не более 20 фишек (стоят в позициях изначальных единиц в массиве bi). За один ход мы можем подвинуть фишку по какому-либо ребру. Если две фишки оказываются в одной вершине, они исчезают. Определить минимальное количество ходов, необходимое для избавления от всех фишек.

Для начала предподсчитаем попарные расстояния между всеми фишками. Это можно сделать, 20 раз запустив BFS. А далее имеем динамику по подмножествам: d[S] (где S - подмножество фишек) - минимальное количество шагов, чтобы убрать все фишки из S. Если S пусто, d[S=0]=0. Если S = {s0, s1, ..., sm - 1} непусто, то мы выбирае фишки, которая исчезнет вместе с нулевой, и делаем переход: d[S] = min(d[S\{s0, si}] + dist(s0, si)), где 1 ≤ i ≤ m - 1.

Итоговая сложность решения - O(knl + k· 22k).

Read more »

 
 
 
 
  • Vote: I like it
  • +35
  • Vote: I do not like it

ЛКШ.P, Летняя школа Яндекса и тому подобное
By yeputons, 8 years ago, In Russian,

Добрый всем вечер, утро.
В ЛКШ в этом году появилось необычайно интересная мне параллель P - промышленное программирование. Как я понял по описанию на сайте в ней будет производиться "симуляция" работы команды в крупной компании со всеми вытекающими: svn, читабельный код, ООП, юнит-тесты и пр. плюшки. Собственно, мне бы очень хотелось туда поехать, потому как мне нравится писать код, который кому-то нужен дольше пяти часов.
Но вот проблема: эта параллель существует только в июльской смене (10-30 июля), а с 22-го по 29-е в Таиланде (соответственно, надо прибавить время на перелёт и акклиматизацию) происходит IOI.
Собственно, вопрос: знает ли кто-нибудь аналогичные по полезности мероприятия, куда теоретически могут взять школьника? Я слышал что-то про летнюю школу Яндекса, но ни гугление, ни яндексация, ни привели меня на какой-нибудь большой сайт.
Про Google Summer of Code слышал, но там ограничение по возрасту - 18+. В этом году уже участвовал в Google Code-in - похожее мероприятие, но для школьников (13+).

Read more »

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

Теперь у нас есть поддержка хоткеев в редакторе
By yeputons, 8 years ago, In Russian,
На Codeforces теперь используется новый WYSIWYG-редактор с поддержкой хоткеев. Поздравляю всех с этим знаменательным событием!
Спасибо, Штаб!

Read more »

 
 
 
 
  • Vote: I like it
  • +15
  • Vote: I do not like it