Добрый всем вечер, утро.
В ЛКШ в этом году появилось необычайно интересная мне параллель P - промышленное программирование. Как я понял по описанию на сайте в ней будет производиться "симуляция" работы команды в крупной компании со всеми вытекающими: svn, читабельный код, ООП, юнит-тесты и пр. плюшки. Собственно, мне бы очень хотелось туда поехать, потому как мне нравится писать код, который кому-то нужен дольше пяти часов.
Но вот проблема: эта параллель существует только в июльской смене (10-30 июля), а с 22-го по 29-е в Таиланде (соответственно, надо прибавить время на перелёт и акклиматизацию) происходит IOI.
Собственно, вопрос: знает ли кто-нибудь аналогичные по полезности мероприятия, куда теоретически могут взять школьника? Я слышал что-то про летнюю школу Яндекса, но ни гугление, ни яндексация, ни привели меня на какой-нибудь большой сайт.
Про Google Summer of Code слышал, но там ограничение по возрасту - 18+. В этом году уже участвовал в Google Code-in - похожее мероприятие, но для школьников (13+).
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
На Codeforces теперь используется новый WYSIWYG-редактор с поддержкой хоткеев. Поздравляю всех с этим знаменательным событием!
Спасибо, Штаб!
Спасибо, Штаб!
Задача A. Чат
Задача решается жадным алгоритмом. Сначала найдём в строке первую букву ('h"). Далее - найдём следующую после неё букву 'e'. Если мы таким образом нашли все буквы, то ответ, очевидно, YES. Теперь давайте докажем, что если ответ был, то он обязательно найдётся. В самом деле, пусть был какой-то ответ. Посмотрим на позицию буквы 'h'. Если мы её сдвинем до самой первой влево (той, которую найдёт жадник), то ничего не изменится. Аналогично поступим со второй и следующими буквами.
Получили жадный алгоритм, работающий за O(n), где n - длина входа.
Получили жадный алгоритм, работающий за O(n), где n - длина входа.
Задача B. Монеты
В этой задаче правильным решением опять же является жадный алгоритм. Выглядит он так: перебираем все числа от 2 и далее, пока стоимость последней добавленной монеты делится на него, делим, добавляем в ответ.
Доказать корректность можно, если посмотреть на стоимости монет в разложении на простые множители. В каждой следующей стоимости все простые входят в меньшей либо равной степени, нежели в текущей (это равносильно тому, что одно делится на другое). Также очевидно, что если суммарная степень уменьшилась хотя бы на два (например, было число a = x· y· z (где y, z > 1, а стало b = x, то можно добавить еще одну промежуточную стоимость a > c = x· y > b. Таким образом, в правильном ответе сумма степеней вхождений при переходе от стоимости к следующей и меньшей уменьшается каждый раз на один. Наш жадный алгоритм именно так и поступает.
Доказать корректность можно, если посмотреть на стоимости монет в разложении на простые множители. В каждой следующей стоимости все простые входят в меньшей либо равной степени, нежели в текущей (это равносильно тому, что одно делится на другое). Также очевидно, что если суммарная степень уменьшилась хотя бы на два (например, было число a = x· y· z (где y, z > 1, а стало b = x, то можно добавить еще одну промежуточную стоимость a > c = x· y > b. Таким образом, в правильном ответе сумма степеней вхождений при переходе от стоимости к следующей и меньшей уменьшается каждый раз на один. Наш жадный алгоритм именно так и поступает.
Задача C. Деревья
Первая мысль - красивая последовательность полностью задаётся любым своим членом. Следующая мысль: хотя бы одно дерево мы трогать не будем. Доказательство: скажем, что мы не трогаем первое дерево, а высоты остальных подгоним. Они, очевидно, все будут положительны.
Решение за квадрат: перебираем, какое дерево мы не трогаем, узнаём первый член последовательности, смотрим, сколько деревьев не совпало.
Это оптимизируется до решения за линию: если мы не трогаем какое-то дерево, то у нас фиксирован первый член последовательности. Давайте подсчитаем для каждого возможного первого члена, скольки деревьям он подходит. Это делается линейным проходом по всем деревьям и операцией "инкремент" на массиве. После чего осталось найти значение первого члена, которому удовлетворяет наибольшее количетсво деревьев, и вывести n - x, где x - это значение.
Решение за квадрат: перебираем, какое дерево мы не трогаем, узнаём первый член последовательности, смотрим, сколько деревьев не совпало.
Это оптимизируется до решения за линию: если мы не трогаем какое-то дерево, то у нас фиксирован первый член последовательности. Давайте подсчитаем для каждого возможного первого члена, скольки деревьям он подходит. Это делается линейным проходом по всем деревьям и операцией "инкремент" на массиве. После чего осталось найти значение первого члена, которому удовлетворяет наибольшее количетсво деревьев, и вывести n - x, где x - это значение.
Задача D. Календарь
Для начала заметим, что так как все строки календаря должны иметь одинаковую длину, то мы легко может эту длину найти. Это просто 
, где suml - суммарная длина всех строк. Теперь посмотрим на строку, которую поставим самой первой. Очевидно, выгодно брать строку, чтобы s + d было минимально (где s - наша строка, а d - дописываемый символ). Понятно, что такая найдётся однозначно, иначе получается, что две строки совпадают (так как символ d нигде не встречается). Разумеется, нельзя забывать, что зафиксировав первую строку, мы зафиксируем длину второй - надо, чтобы хотя бы одна была. Отлично, с первой строкой мы определились. Теперь мы знаем длину второй строки. Здесь нам надо взять просто минимальную строку соответствующей длины (одна префиксом другой быть не может - длины равны). Таким образом, заполняем календарь по линиям.
, где suml - суммарная длина всех строк. Теперь посмотрим на строку, которую поставим самой первой. Очевидно, выгодно брать строку, чтобы s + d было минимально (где s - наша строка, а d - дописываемый символ). Понятно, что такая найдётся однозначно, иначе получается, что две строки совпадают (так как символ d нигде не встречается). Разумеется, нельзя забывать, что зафиксировав первую строку, мы зафиксируем длину второй - надо, чтобы хотя бы одна была. Отлично, с первой строкой мы определились. Теперь мы знаем длину второй строки. Здесь нам надо взять просто минимальную строку соответствующей длины (одна префиксом другой быть не может - длины равны). Таким образом, заполняем календарь по линиям.Задача E. Выражение
Under construction. Основная идея - кубическая динамика с переходом за 102.
Разбор задач Codeforces Beta Round 54 (Div. 2)
Прошёл пробный (да и первый тоже) туры XXXIII Всероссийской олимпиады школьников по информатике.
Результаты доступны на Google Spreadsheets. Добавьте свои! Внимательно читаем предупреждения сверху. Просьба не портить результаты и устраивать чат на других листах (либо в специализированном окошке от гугла - кто найдет, тот молодец).
Результаты доступны на Google Spreadsheets. Добавьте свои! Внимательно читаем предупреждения сверху. Просьба не портить результаты и устраивать чат на других листах (либо в специализированном окошке от гугла - кто найдет, тот молодец).
Добрый день.
Предположим, у нас есть такая задача: есть поле WxH, в некоторых клетах стоят стенки. Есть минимальный путь из верхнего левого угла в правый нижний и нужно что-то посчитать от этого пути.
Можно построить тест, на котором этот путь имеет длину порядка половины площади и идёт "змейкой".
Однако я слышал, что также можно построить тест, где этот путь будет иметь длину порядку 2/3 площади и этим люди челленжили какую-то задачу на TopCoder.
Кто-нибудь знает этот тест?
Предположим, у нас есть такая задача: есть поле WxH, в некоторых клетах стоят стенки. Есть минимальный путь из верхнего левого угла в правый нижний и нужно что-то посчитать от этого пути.
Можно построить тест, на котором этот путь имеет длину порядка половины площади и идёт "змейкой".
Однако я слышал, что также можно построить тест, где этот путь будет иметь длину порядку 2/3 площади и этим люди челленжили какую-то задачу на TopCoder.
Кто-нибудь знает этот тест?
Доброе утро.
Кто-нибудь знает алгоритм деления длинных чисел быстрее, чем за квадрат? Слышал, что это можно сделать при помощи преобразования Фурье (умножать им уже умею)
Кто-нибудь знает алгоритм деления длинных чисел быстрее, чем за квадрат? Слышал, что это можно сделать при помощи преобразования Фурье (умножать им уже умею)
Навеяно вот этим комментарием. У меня давно была такая идея: если разделяют рейтинг на Algorithm/Development/etc, почему бы не разделить вклад на Разборы+Идеи+Помощь/Шутки юмора?Просто мне самому кажется неправильным получать такие же кучи плюсов за шутки, как и за хорошие идеи.
Ваше мнение?
Ваше мнение?
Добрый вечер.
Смотрю разные проверяющие системы и наткнулся на dudge. Собственно, есть вопросы к тем, кто с ней работал:
Смотрю разные проверяющие системы и наткнулся на dudge. Собственно, есть вопросы к тем, кто с ней работал:
Так как ждать официальных резов всем, я думаю, лень, то можно заполнять свои результаты тут:
http://yeputons.net/wiki/COCI_2011_R4
Заодно можно и почитать коллективный разбор задач.
http://yeputons.net/wiki/COCI_2011_R4
Заодно можно и почитать коллективный разбор задач.
А когда нет - могу посмотреть, если введу codeforces.ru без www.
UPD. Fixed
После публикации моего предыдущего поста на эту тему я решил обобщить информацию, которую узнал.
Итак, на главной странице системы багрепортов GCC висит отличное сообщение: "Проблемы с числами с плавающей точкой - самый популярный небаг". Т.е. к этому надо быть готовым и исправлять это они не собираются.
Небаг заключается в некорректном преобразовании оптимизатором плавающих чисел. Точнее, не так, как это делает соппроцессор (иногда, впрочем, угадывает). Как от double к int, так и в обратную сторону.
В частности, код из предыдущего поста (компилировать с -O2) на некоторых версиях и машинах может вывести, что 20971519 == 20971520. Однако, если сделать EPS = 10-8, то лично у меня всё работает.
Ощущение, что оптимизатор что-то где-то всё-таки криво считает (например, во float).
Но всё же это надо учитывать. Я лично изменил свой любимый EPS. Жаль.
Итак, на главной странице системы багрепортов GCC висит отличное сообщение: "Проблемы с числами с плавающей точкой - самый популярный небаг". Т.е. к этому надо быть готовым и исправлять это они не собираются.
Небаг заключается в некорректном преобразовании оптимизатором плавающих чисел. Точнее, не так, как это делает соппроцессор (иногда, впрочем, угадывает). Как от double к int, так и в обратную сторону.
В частности, код из предыдущего поста (компилировать с -O2) на некоторых версиях и машинах может вывести, что 20971519 == 20971520. Однако, если сделать EPS = 10-8, то лично у меня всё работает.
Ощущение, что оптимизатор что-то где-то всё-таки криво считает (например, во float).
Но всё же это надо учитывать. Я лично изменил свой любимый EPS. Жаль.
Так как в последнее время я много пишу на Codeforces и контестов, и постов с комментариями, у меня появились некоторые предложения по улучшению WYSIWYG редактора.
Расставил в порядке уменьшения приоритета:
Расставил в порядке уменьшения приоритета:
- Хоткеи. Когда я пишу в Word/TinyMCE, я привык не пользоваться мышкой. Вообще. Я просто выделяю текст стрелочками и нажимаю Ctrl+B/Ctrl+I/Ctrl+U/Ctrl+S/... Получается гораздо быстрее. Тут пока таких хоткеев не замечено. (Firefox 3.6.13)
- Заголовки. В какой-то момент я случайно обнаружил, что иногда редактор заменяет текст "по центру" на красивый синий заголовок. Причём обнаруживается это только при предпросмотре или сохранении - в окне редактирования не видно. Также он делает когда хочет, а не когда нужно. Приходится лезть в HTML-код и самостоятельно добавлять class="header". А потом нажимать предпросмотр и убеждаться что всё хорошо.
- Редактирование HTML-кода. Когда я поступаю так, как написал выше, иногда забываю "свернуть" HTML обратно. В результате чего теряю изменения. Хорошо было бы не добавлять окошко с кодом рядом, а заменять им WYSIWYG. Или просто при нажатии на одну из кнопок "Отправить" показывать предупреждение, что остались несохранённые изменения HTML-кода.
- Списки выглядят по-разному. Ну, тут всё понятно. Ненумерованный список показывается с большими отступами в редакторе и без них - в предпросмотре.
- Подсветка синтаксиса. Когда требуется вставить большой кусок кода, я пользуюсь Pastebin. Но когда надо показать буквально 5-10 строк, это кажется излишним. Поэтому есть предложение сделать подсветку синтаксиса. Можно даже не в редакторе - это ИМХО трудно. Например, сделать еше один тег [code] впридачу к
Поехали.
A. Автодополнение
В это задаче требовалось прочитать условие и решить как угодно. Одно из самых простых решение - считать строчку, считать последние страницы, отсортировать (хоть пузырьком - 1003 прекрасно укладывается, куб потому что надо еще сравнивать), а затем бежать с начала до конца и выводить первую строку, у которой префикс совпадает с нашей. Это проверяется if'ом на длину (чтобы не было RTE) и одним for'ом. Нашли строку - вывели и завершились. Они отсортированы, поэтому выведем то, что надо. Если не нашли - вывели исходную строку.
Разбор задач Codeforces Beta Round 49 (Div. 2)
Собственно, сабж c контеста:
http://pastebin.com/jvkUcZx3
Казалось бы, процедура, вызываемая от параметров, равных побайтно, должна возвращать один и тот же результат. Ан нет - они различаются.
В MSVC++ всё ок.
Предложили еще один вариант. Он гораздо проще и даже, казалось бы, понятно, почему случается. По стандарту - результат неопределён.
COLLECT_GCC=C:\Soft\MinGW\bin\gcc.EXE
COLLECT_LTO_WRAPPER=c:/soft/mingw/bin/../libexec/gcc/mingw32/4.5.0/lto-wrapper.exe
Target: mingw32
Configured with: ../gcc-4.5.0/configure --enable-languages=c,c++,ada,fortran,objc,obj-c++ --disable-sjlj-exceptions --with-dwarf2 --enable-shared --enable-libgomp --disable-win32-registry --enable-libstdcxx-debug --enable-version-specific-runtime-libs --disable-werror --build=mingw32 --prefix=/mingw
Thread model: win32
gcc version 4.5.0 (GCC)
Intel Core i3 M350 (x86)
UPD. На сервере CF тоже выдает некорректный результат. Попробуйте во вкладке "запуск".
UPD2. В одном из комментариев выдвинули дополнительное требование: включите оптимизатор (-O1/-O2)
UPD3. Две абсолютно одинаковые посылки под разными компиляторами получают разные вердикты: GCC - WA14 (240112), MSVC++ - OK (240115). Задача B из CF49
http://pastebin.com/jvkUcZx3
Казалось бы, процедура, вызываемая от параметров, равных побайтно, должна возвращать один и тот же результат. Ан нет - они различаются.
В MSVC++ всё ок.
COLLECT_GCC=C:\Soft\MinGW\bin\gcc.EXE
COLLECT_LTO_WRAPPER=c:/soft/mingw/bin/../libexec/gcc/mingw32/4.5.0/lto-wrapper.exe
Target: mingw32
Configured with: ../gcc-4.5.0/configure --enable-languages=c,c++,ada,fortran,objc,obj-c++ --disable-sjlj-exceptions --with-dwarf2 --enable-shared --enable-libgomp --disable-win32-registry --enable-libstdcxx-debug --enable-version-specific-runtime-libs --disable-werror --build=mingw32 --prefix=/mingw
Thread model: win32
gcc version 4.5.0 (GCC)
Intel Core i3 M350 (x86)
UPD. На сервере CF тоже выдает некорректный результат. Попробуйте во вкладке "запуск".
UPD2. В одном из комментариев выдвинули дополнительное требование: включите оптимизатор (-O1/-O2)
UPD3. Две абсолютно одинаковые посылки под разными компиляторами получают разные вердикты: GCC - WA14 (240112), MSVC++ - OK (240115). Задача B из CF49
Да что же это такое?!
Уже лежали, казалось бы, все: CF, TC (две минуты), lksh.ru, olympiads.ru.
Тимус, к сожалению, не мониторил.
Теперь уже четвёртый час висит в заочке "решение компилируется". Судя по всему, все посылки, посланные после, тоже стоят. У меня номер 35501. Кому написать? Судьям вопрос уже отправил.
UPD. Что, любопытно, последняя проверенная посылка была 5 января в 14:12:18.
Уже лежали, казалось бы, все: CF, TC (две минуты), lksh.ru, olympiads.ru.
Тимус, к сожалению, не мониторил.
Теперь уже четвёртый час висит в заочке "решение компилируется". Судя по всему, все посылки, посланные после, тоже стоят. У меня номер 35501. Кому написать? Судьям вопрос уже отправил.
UPD. Что, любопытно, последняя проверенная посылка была 5 января в 14:12:18.
Еще вопрос: кто-нибудь знает, как поставить ссылку на профиль пользователя в посте?
A. Задача Читериуса
В этой задаче теоретически могли быть следующие проблемы: считывание, сравнивание, "я не прочитал, что n<=1000" и "электричка опоздала на 10 минут к началу раунда". У меня была последняя :)
Считывать можно было либо построчно, либо по токенам. Всё языки это умеют.
Сравнивать два квадрата можно опять же как угодно. Я делал так: считал две строчки, соеденил в одну и поменял 3й и 4й местами. Получилась "ленточка". Две "ленточки" можно сравнить двумя циклами: первый перебирает сдвиг, второй проверяет, что всё совпало.
Далее оставалось лишь посчитать количество стопок. Это можно было делать так: перебираем все непомеченные квадратики, добавляем один к ответу и помечаем все квадратики, которые равны текущему.
Считывать можно было либо построчно, либо по токенам. Всё языки это умеют.
Сравнивать два квадрата можно опять же как угодно. Я делал так: считал две строчки, соеденил в одну и поменял 3й и 4й местами. Получилась "ленточка". Две "ленточки" можно сравнить двумя циклами: первый перебирает сдвиг, второй проверяет, что всё совпало.
Далее оставалось лишь посчитать количество стопок. Это можно было делать так: перебираем все непомеченные квадратики, добавляем один к ответу и помечаем все квадратики, которые равны текущему.
Разбор задач Codeforces Beta Round 48
TopCoder тоже лежит.
- Sign out
- Заходим последовательно на две разные страницы (например, CF Beta Round #46 и #47)
- На той, на которую зашли первой (#46) входим в систему.
- Перенаправляемся на последнюю открытую страницу
- У нас есть две вкладки/окна с CF Beta Round #47
UPD: тема уже поднималась
Кто-нибудь знает, почему сейчас лежали codoforces.ru, olympiads.ru, lksh.ru ? CF вроде поднялся, остальные - пока нет.
Почему на acm.timus.ru нельзя кидать Exception на C++ даже внутри try {...} catch {...} ?
Виноваты ключи компиляции или VC++? Почему они не поставят еще хотя бы GCC?
Кто-нибудь знает мотивацию?
Или какой-нибудь механизм, похожий на exception (выйти из глубокой рекурсии наверх просто и с параметром)
Виноваты ключи компиляции или VC++? Почему они не поставят еще хотя бы GCC?
Кто-нибудь знает мотивацию?
Или какой-нибудь механизм, похожий на exception (выйти из глубокой рекурсии наверх просто и с параметром)
http://codeforces.net/contest/44/problem/H?locale=ru
на страницу
http://codeforces.net/contest/44/problem/H?locale=en
и обратно при помощи кнопочки смены языка выскакивает сообщение "Ваше решение будет отправлено в дорешивание. Результаты можно смотреть в статусе и в нижней части турнирной таблицы" (на языке, с которого переходим).
Баг №2
Ссылка http://codeforces.net/comments/830 не работает, однако прекрасно получается зайти по адресу http://www.codeforces.ru/comments/830
Вроде бы простая задача: посчитать количество единичек в числе.
Я знаю четыре способа её решения: "наивный" метод (пробежаться по всем битам), встроенная в Gcc функция __builtin_popcount, предподсчёт для всех чисел < 0xFFFF и метод за log log X.
Я знаю четыре способа её решения: "наивный" метод (пробежаться по всем битам), встроенная в Gcc функция __builtin_popcount, предподсчёт для всех чисел < 0xFFFF и метод за log log X.
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 17.11.2024 20:38:52 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
