Тренировки ИТМО (neerc.ifmo.ru/trains/

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

DP Bitmask - Topic Stream

Shayan

До начала 04:18:03

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
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	167
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя agul

Тренировки ИТМО (neerc.ifmo.ru/trains/

Автор agul, 13 лет назад, По-русски

Здесь обсуждаются задачи тренировок ИТМО (http://neerc.ifmo.ru/trains/).

Тренировки проводятся по средам и субботам, начало в 16:30 (МСК), длительность - 5 часов, формат - ACM.

P.S. Пожалуйста, не обсуждайте до окончания тренировки задачи. Мы за честность :)

itmo, trains

agul
13 лет назад
127

Комментарии (125)

Показать архивные | Написать комментарий?

PavelKunyavskiy

13 лет назад, # |

Да на главной странице вроде. Еще бы я их не видел до этого (:

→ Ответить

Romka

13 лет назад, # ^ |

Дак вроде уже традиция давать на первые личные тренировки ЛКШатские задачи ;)

→ Ответить

agul	13 лет назад, # ^ \| 0 Там у меня как-то условия странно слева обрезаны. Так у всех? → Ответить

tunyash

13 лет назад, # |

А о каких тренировках идет речь, если не секрет?

→ Ответить

yarrr

13 лет назад, # |

Блин, в чём в Е то подвох, я всю голову сломал :(

→ Ответить

shevchen

13 лет назад, # ^ |

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

→ Ответить

yarrr

13 лет назад, # ^ |

Сортировал, тримил, не учитывал :(

Не покажешь код, пожалуйста?

→ Ответить

shevchen

13 лет назад, # ^ |

http://pastie.org/2533122

Код кривой - писался быстро - но вроде понятный.

→ Ответить

pkhaustov

13 лет назад, # |

Мда... Андрей Станкевич решил поиздеваться над участниками сегодня.

Я прекрасно понимаю, что его тренировки важны для подготовки к полуфиналу, но после сегодняшнего мне будет сложно себя заставить решать его контесты и впредь.

Первую задачу я решил на 37ой минуте, потому что в условиях в одном месте указано, что надо читать из файла, а в другом - использовать stdin. Я прочитал то, что написано непосредственно в примере ввода и получил 8 бревен по одной задаче и 2 бревна по другой. В конце концов я заметил, что информация в начале описания задачи отличается от той, что указана в конце описания задачи и тут же менее чем за пол часа отгрузил 5 задач. После чего мне предстояло потратить время на то, чтобы переписать с векторов на статику хранение графа для сдачи 6ой задачи H. Решить единственную интересную для меня задачу контеста J. А затем я на удивление самому себе сдал задачу E с первой попытки (задача абсолютно безыдейная и вообще не понятно, что она делает в этом наборе). Далее я занялся тем, что пытался протолкнуть читерское решение по задаче F и мне это удалось! +23 за 6 минут до конца и я сижу с 9 задачами! Время у меня и без этих +23 было конским из-за непоняток с файлами, но 9 задач выводили меня на приятное 4ое место.

Но и тут не обошлось без очередного сюрприза. После контеста началась какая-то непонятная перепроверка в результате которой мое решение по задаче на технику E получило бревно. Такие же бревна появились у всех, кто сдал эту задачу до Rejudge'а. И вот он я сижу с 8 задачами и космическим штрафом и гадаю, что же там такое произошло с моим решением, что Accepted полученный на середине контеста у меня отобрали уже после контеста. Мне интересно, что же там такое исправили в тестах. Человек 5 сдали эту задачу до реджаджа. После него у них остались плюсики в таблице, но после контеста почему-то их отобрали. Крайне непонятная и неприятная ситуация. Я понимаю, тренировка тренировкой, но это - как минимум неприятно для меня. Если бы мне выскочил WA, я бы исправил ошибку за оставшиеся два с лишним часа.

Кстати, так же было и на полуфинале. На втором часу я сдал задачу с плюса, но в финальной таблице у нас красовалось "-1". Тогда Accepted все-таки вернули. Надеюсь, что вернут и сейчас.

Андрей, если Вы это читаете, то напишите пожалуйста хотя бы что же было не так в тестах или чекере, что часть решений получала Accepted, а часть наоборот стала получать после исправления этого "не так".

→ Ответить

Narg	13 лет назад, # ^ \| 0 Лол. В H прекрасно проходило два массива ArrayList<Integer>[] g, w. А какой чит ты запихнул? Я вот полчаса думал не написать ли декартво дерево которое умеет все действия или корневую оптимизацию на запросах и решил, что лучше отчет по работе напишу) → Ответить

Jacob

13 лет назад, # ^ |

-8

Ну да, два ArrayList<Integer>, наверное, действительно проходит.

А в С++ походу просто забыли включить оптимизацию.

→ Ответить

ivan.popelyshev

13 лет назад, # ^ |

А я вот после -13 по Е забил на контест. А надо было спокойно кодить B, оказывается моя E должна была пройти еще в первом часу :) реджадж был. С файлами, кстати, тоже накололся.

И да, тоже хочется знать что там случилось в Е.

→ Ответить

Narg	13 лет назад, # ^ \| 0 Для B есть решение, которое было было бы приятно кодить? → Ответить

mmaxio

13 лет назад, # ^ |

А как B решается?

→ Ответить

yarrr

13 лет назад, # ^ |

← Rev. 2 →

Обломайте идею, пожалуйста, а то проверить нельзя же.

0) Разобьём углы, где phi2 < phi1 на два, очевидно.

1) Занумеруем все углы по возрастанию. Каждый сегмент = 4 инта, номера углов и радиусы.

2) Сделаем 2 массива сегментов, первый отсортируем по возрастанию радиусов начала, второй по радиусам концов.

3) Заведем дерево отрезков, где мы будем поддерживать углы на текущей итерации.

4) Итерируемся по радиусам. У нас есть текущий промежуток: [r[i], r[i + 1]]. Очистим дерево отрезков от всех устарелых сегментов, где r2 <= r[i].

Добавим в дерево отрезков все новые сегменты, где r1 == r[i].

5) Считаем сумму углов в нём.

6) Зная угол и радиусы, получаем площадь текущего сегмента.

7) ...

8) PROFIT!

Код: http://pastebin.com/HejT3KCn

То есть ключевая идея, что мы двумя указателями в дерево отрезков добавляем нужную инфу и подчищаем устаревшую. В Сазанке похожая задача была про прямоугольники.

→ Ответить

PavelKunyavskiy

13 лет назад, # ^ |

Идея решения правильная. В этой задаче я знаю две баги, которые можно сделать - слишком маленькие массивы и не учесть случай когда покрыто все. И по-моему у Вас именно второе. Либо я вообще не понимаю как код работает, кода есть пересечения.

→ Ответить

yarrr

13 лет назад, # ^ |

Да я так потестил на больших тестах, вроде работает.

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

Соответственно, при добавлении угла добавляем +1 на отрезке, при удалении делаем -1 на отрезке и пересчитываем дабловые велечины.

Я только 1 не могу понять, на такой тест:

0.000000 6.283185 1 10000"

Правильный ответ: 314159246,858407500?

>>> 6.283185 * (10000.0**2 - 1.0**2) / 2.0

314159246.8584075

→ Ответить

PavelKunyavskiy

13 лет назад, # ^ |

Да казалось бы. Там случай чуть хитрее. Попробуйте так:

0 π 1 2

π 2·π 1 2

$\text{[math]}$ $\text{[math]}$ 1 2

Неаккуратная реализация может почитать ответ в два раза меньше.

→ Ответить

yarrr

13 лет назад, # ^ |

Оно? :)

C:\Users\safronov\Dropbox\Eclipse\Sandbox\bin>java Main

0 3.1415 1 2

3.1415 6.2831 1 2

1.5707 4.7123 1 2

9,424650000

→ Ответить

PavelKunyavskiy

13 лет назад, # ^ |

Вроде правильно. Не знаю даже что еще бывает.

Вот мое решение. К сожалению не уверен, что последнее.

→ Ответить

mmaxio

13 лет назад, # ^ |

← Rev. 2 →

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

Для этого заводим дерево отрезков, в вершине хранятся 3 значения - собственно сумма по покрытым клеточкам(value), сумма чисел на всех клеточках, которые соответствуют этой вершине(full)(это предподсчитывается один раз в начале) и количество отрезков, которыми эта вершина полностью покрыта(add).

Добавляем/удаляем отрезки как обычно, реальное значение в вершине - это add[v] > 0 ? full[v] : value[v].

Есть тонкий момент - нельзя раздавать add детям, иначе может случиться, что надо из вершины вычесть 1, а там уже 0 и придется пойти в детей.

Что интересно, можно и раздавать, но тогда после того, как запустимся от детей, надо найти минимум из их add'ов, из них обоих этот минимум вычесть, а к себе прибавить.

→ Ответить

niyaznigmatul

13 лет назад, # ^ |

Я не Андрей, но скажу, что как уже написали выше, задачи были взяты из олимпиады ЛКШ.

А проблемы с задачей E, были у многих, в том числе и у меня. Проблема была в том, что в условии не написано, что все сабмиты отсортированы по времени отправки. Не знаю, что там было в тестах, но если сортировать сабмиты, решение получало WA 6, а если не сортировать - AC. Потом, во время контеста, тесты поправили и перетестировали.

→ Ответить

pkhaustov

13 лет назад, # ^ |

Так же в условии не сказано, что никакие две посылки не имеют одинакового времени. Представим тест, где в одно время сделано сразу 1000 посылок, одна из которых OK, а оставшиеся 999 - WA. И как их сортировать?! В зависимости от того, какой по порядку окажется посылка с OK, будет определяться ответ. Отсюда логично предположить, что жюри любезно отсортируют входные данные за нас, избавив нас от неоднозначности. Проверяем, да - Accepted. Так какого х%# после раунда оказывается, что не так? В любом случае, Accepted поставленный на середине контеста после контеста убирать - не правильно. Между прочим, во время контеста мне пришло сообщение с чем-то вроде "Rejudge of your solution for problem E: new outcome: Accepted".

→ Ответить

ivan.popelyshev

13 лет назад, # ^ |

А вот на это я ставил new RuntimeException(); , так что это не так.

→ Ответить

pkhaustov

13 лет назад, # ^ |

Я тоже послал код, который в случае, если что-то не так с порядком сабмитов выдает WA. И как ни странно, он его не выдал.

→ Ответить

Narg

13 лет назад, # ^ |

Это же _тренировка_ для студентов ИТМО, а не рейтинговое соревнование topcoder open. В чём проблема, что accepted выставляется в зависимости от того, насколько решение соответсвует условию а не от того как шёл контест? Боишься, что внуки отроют архив тренировок и их опечалят твои результаты?

Меня больше смущает, что до первого реджаджа мои решения по Е получали RE (казалось бы причём тут порядок сабмитов?), после него OK, а что после второго неизвестно, потому что система не даёт залогиниться.

→ Ответить

pkhaustov

13 лет назад, # ^ |

Мне самому отстойно осознавать, что есть таблица, где я занимаю позорное 13ое место, не сдав задачу, в которой надо было безыдейно промоделировать процесс, который я сотню раз моделировал.

Правильным решением для жюри было бы просто отсортировать сабмиты в нужном порядке во входных файлах и перепроверить на таком наборе тестов.

→ Ответить

goryinyich

13 лет назад, # ^ |

← Rev. 2 →

Мое решение Е проходило как до реджаджа, так и после. Собственно, я так и не понял, в чем была подстава

→ Ответить

Narg	13 лет назад, # ^ \| 0 У тебя -2, вообще-то. → Ответить

pva701

13 лет назад, # ^ |

← Rev. 2 →

у меня анологично с Е и Н, решение на векторах, получило тле27... мммм, при том что я таким же решением сдавал уже эту задачу, хорошо хоть реджадж провели...

→ Ответить

Creed

13 лет назад, # ^ |

→ Ответить

PavelKunyavskiy

13 лет назад, # ^ |

← Rev. 2 →

F - это про next_permutation? Если да, то можно поподробнее что за решение. Мы вроде нормальные тесты сделали с Мишей к олимпиаде. (Хотя там ничего кроме квадрата не присылали)

→ Ответить

pkhaustov

13 лет назад, # ^ |

Ну квадрат и зашел :) Я сделал несколько модификаций разного рода. Во-первых я не использовал встроенный next_permutation, а написал свой, который работал специфично. До тех пор, пока надо было просто найти самый левый элемент, который изменит свою позицию, все делалось тупо за линию. После чего я выполнял reverse отрезка только в случае, если первый элемент этого интервала не равен последнему. Так же я считал наибольшие префикс и суффикс из одинаковых элементов и если интервал попадал полностью в такие участки, то операцию next я не выполнял. У меня в голове были еще идеи, но они не пригодились, решение и так получило Accepted.

→ Ответить

PavelKunyavskiy

13 лет назад, # ^ |

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

→ Ответить

pkhaustov

13 лет назад, # ^ |

Если я знал, что при "next L R" весь отрезок состоит из одинаковых чисел, то я просто пропускал этот запрос. А предпосчитывал одинаковость я, как уже сказал, для суффикса последовательности и для ее префикса (просто с двух сторон от концов нашел наибольшие одинаковые подпоследовательности). Они, кончено же, пересчитывались, что выполнялось за O(N) в сумме по всем запросам.

→ Ответить

PavelKunyavskiy

13 лет назад, # ^ |

Ну там еще был тест с кучей 1 и небольшим количеством вкраплений, но это уже квадрат деленный на константу. а тут еще и половина действий не делается. Видимо это валиться только если такое решение прийдет в голову и то не факт...

→ Ответить

andrewzta

13 лет назад, # ^ |

+23

Ой, у нас было столько проблем, что все и не перечислишь.

Надеюсь, дальше все пойдет поспокойнее.

→ Ответить

zurg	13 лет назад, # \| 0 А я время не сортировал в Е, как и сказал niyaznigmatul, а все равно ВА6. А будет ли дорешивание? → Ответить

Trytrytry

13 лет назад, # |

А на этом сайте можно любому человеку зарегистрироваться? (ату у меня что-то не получается, так какие-то пароли нужно).

→ Ответить

niyaznigmatul

13 лет назад, # ^ |

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

→ Ответить

gojira

13 лет назад, # |

А кто-нибудь смог сконвертировать условия так, чтобы левые 3 сантиметра страницы не отрезались? Если да, можете поделиться pdf-ом?

→ Ответить

shevchen

13 лет назад, # ^ |

На будущее - GSview и .ps открывает, и конвертит нормально.

→ Ответить

imslavko

13 лет назад, # ^ |

ps2pdf?

→ Ответить

shevchen

13 лет назад, # ^ |

← Rev. 2 →

*nevermind*

→ Ответить

imslavko

13 лет назад, # ^ |

у меня есть ps2pdf, но нет GSview, это нормально? Я так понял, это не одно и то же, и изначально предложил ps2pdf, как альтернативу GSview

→ Ответить

shevchen

13 лет назад, # ^ |

Я понял вопрос как "Из ps в pdf?". Насчет ps2pdf ничего сказать не могу.

→ Ответить

gojira

13 лет назад, # ^ |

Получилось, спасибо. Всё же странно что стандартными Adobe-овскими продуктами не получается.

→ Ответить

shevchen

13 лет назад, # |

Вот интересно, в задаче К при заполненной последней табличке правильный ответ - 0. Где логика?

→ Ответить

mmaxio

13 лет назад, # ^ |

Логики нет, но в условии об этом сказано =)

→ Ответить

shevchen

13 лет назад, # ^ |

Ну вот, вместо того, чтобы дочитать условие, потратил 3 попытки и 20 минут =)

→ Ответить

mastersobg

13 лет назад, # ^ |

А можно объяснить условие по K? Я его за 5 часов не втёр. =) Какие перестановки получаются?

→ Ответить

shevchen

13 лет назад, # ^ |

В примере (кольцо развернуто в прямоугольник):

==|

|==

=|=

| | |

→ Ответить

mastersobg

13 лет назад, # ^ |

А "| | =" почему нельзя?

→ Ответить

shevchen

13 лет назад, # ^ |

== в моем рисунке - пара динозавров (каждый вытянут в длину). Пополам животное резать нельзя.

→ Ответить

mastersobg

13 лет назад, # ^ |

Всё, понял условие, спасибо. Тяжко оно мне далось =)

→ Ответить

pkhaustov

13 лет назад, # |

+11

Закончился контест IFMO Training 02 - September 17, 2011.

Про задачу C:

Не могу понять, почему же мой код на C ловил Runtime Error on test #4. Я уже все испробовал. Я даже чтение переписал кучей разных способов. Кто-нибудь может показать мне этот тест пожалуйста? Если кто-то сталкивался с такой же проблемой, то поделитесь, как вы с ней разобрались. Я отловил с помощью методов WA, что у меня вызывается от отрицательного числа функция, которой аргументом передается номер вершины. А поведение программы зависит от метода чтения, что странно. Обидно, задача простая, я на контесте так и не зашла.

А теперь про задачу А:

До меня дошло нормальное решение задачи A только после того, как я сдал решение, которое вообще не использовало координаты центров окружностей из входного файла. На самом деле там нужно было просто разделить прямоугольник на 4 равные части и в каждой из них нарисовать миниатюрную копию такого же способа, как тот, который был дан во входном файле. Однако, решение, которое пробует два вида укладки - прямой и косой, так же получает Accepted.

→ Ответить

shevchen

13 лет назад, # ^ |

В С была RE4 из-за того, что искал в дереве отрезков от большего к меньшему.

В А, кстати, нужно рассмотреть 2 способа косой укладки, помимо квадратичной. А как доказать достаточность?

→ Ответить

pkhaustov

13 лет назад, # ^ |

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

→ Ответить

pkhaustov

13 лет назад, # ^ |

По поводу задач C. Я не использовал дерево отрезков. Мое решение использовало идею binary uplifting'а. Я все-таки склоняюсь к мнению, что что-то не так было с чтением.

Есть те, кто сдал эту задачу на C++? А те, кто сдал ее без использования дерева отрезков?

→ Ответить

gojira

13 лет назад, # ^ |

Да, я решил на C++. Решал через запоминание предков степеней 2 (видимо это и есть binary uplifting?).

→ Ответить

pkhaustov

13 лет назад, # ^ |

Да, это и есть binary uplifting.

→ Ответить

qwerty787788

13 лет назад, # ^ |

Черт, такое простое решение по А, и его почти никто не придумал [и я тоже]:(

→ Ответить

yarrr

13 лет назад, # |

Расскажите, пожалуйста, как решать H (кол-во возможных деревьев?) и K (про танцы).

Спасибо.

→ Ответить

shevchen

13 лет назад, # ^ |

H: возьмем центральное ребро человека. Переберем все ребра дерева и будем пытаться наложить одно на другое. Понятно, количество наложений - C(degree(v) - 1, 3) * C(degree(u) - 1, 2); суммируем для всех ребер дерева.

K: если N кратно 2, возможно 2 размещения, при которых динозавры сдвинуты на полкорпуса относительно друг друга. Остальные случаи считаются динамикой, если не понятно, расскажу подробней.

→ Ответить

yarrr

13 лет назад, # ^ |

А не подскажешь, что за динамика?

Я просто поперебирал для маленьких значений, там последовательность у меня была похожа очень на Фибоначчи.

→ Ответить

shevchen

13 лет назад, # ^ |

Почти Фибоначчи и есть.

Итак, рассматриваем случай, когда динозавры идут или попарно вдоль кольца (=), или перпендикулярно (|). Тогда f(i+2) = f(i) + f(i+1), где f(i) - количество способов замостить прямоугольник i на 2. f(0) = 1, f(1) = 1. Но в этом решении фиксирована какая-то позиция - начало отсчета, через которую вдоль кольца нет пары динозавров. Случаев, когда пара есть, f(n - 2).

→ Ответить

mmaxio

13 лет назад, # |

Давайте обсудим задачу E, которую никто не решил. Есть ли решение лучше, чем $\text{[math]}$ ?

→ Ответить

gojira

13 лет назад, # ^ |

Видимо, имеется в виду деление последовательности на отрезки длины sqrt(N), хранение для каждого такого отрезка значения, которое добавлено ко всем элементам одновременно, и хранение для каждого отрезка в бинарном дереве поиска всех его элементов без учета этого добавления. Можно заменить BST на хеш-таблицу, убрав этим из оценки сложности логарифм. Я закодил такую штуку, но всё равно TLE10/11.

→ Ответить

mmaxio

13 лет назад, # ^ |

Ага, типа того. Ну еще есть такая мысль хранить каждый отрезок как отсортированный, добавление тогда будет тоже за $\text{[math]}$ , но константа намного меньше. А еще можно заметить, что если так делать, то на самом деле при добавлении нам надо будет слить два отсортированных массива в один(порядок чисел среди тех, к которым что-то добавили, и среди остальных не меняется) и добавление опять за $\text{[math]}$ . Но асимптотика от этого не улучшается =)

→ Ответить

PavelKunyavskiy

13 лет назад, # ^ |

1. BST точно не надо - сортировка + бинпоиски.

2. По каким-то не известным лично мне причинам оптимальное значение блока меньше, чем $\text{[math]}$ . Оно где-то в районе 100. Подбирается на случайном макс тесте. А TL реально жестко очень выставили.

3. При очень большом желании казалось бы можно загнать лог под корень. Скорее всего отсюда и берется это около 100. Оно очень похоже на $\text{[math]}$ .

→ Ответить

niyaznigmatul

13 лет назад, # ^ |

Я решил за $\text{[math]}$ , хранил в каждом блоке хэш-таблицу. Только на Java не прошло, пришлось переписать на C++.

→ Ответить

caustique

13 лет назад, # |

Зарегистрировался еще вчера, но до сих пор не получил логин.

По почте тоже не отвечают.

Что делать?

→ Ответить

Jokser

13 лет назад, # |

Вопрос по сегодняшней тренировке - как решать A,B,F,K ?

→ Ответить

CherryTree

13 лет назад, # ^ |

В F любую последовательность из 2-х операций можно представить в виде эквивалентной ей последовательности из максимум 1-й операции.

→ Ответить

mmaxio

13 лет назад, # ^ |

Я просто каждому преобразованию сопоставил матрицу 4 на 4 и потом их умножал.

→ Ответить

Eledven

13 лет назад, # ^ |

← Rev. 2 →

F - Представим каждую операцию как композицию операций транспонирования и переворота относительно горизонтали. Почему такие? Потому что 2 операции транспонирования, или 2 операции переворота подряд не меняют матрицу. Запишем все наши операции в стек так, что бы 2 одинаковые не шли рядом. В итоге стек будет выглядеть как-то так:

а) 0, 1, 0, 1, ...

б) 1, 0, 1, 0,...

Заметим, что с периодом 8 мы возвращаемся в начальное состояние. Осталось только выполнить первые mod 8 операций, лежащих в стеке.

K - зафиксируем ответ бинпоиском. Как проверить, что такой ответ можно получить? Рассмотрим массив a_i = v_i - m * w_i, где m - проверяемый массив. Ответ существует, если сумма k наибольших значений a_i >= 0. Воспользуемся поиском k-ой порядковой статистики массива чтобы найти первые k чисел за O(n).

Надеюсь, что все понятно. =)

→ Ответить

stostap

13 лет назад, # |

-7

B - Флойд - Уоршалл...

→ Ответить

NiceDay

13 лет назад, # |

А на этой тренировке дорешивание возможно?

→ Ответить

mmaxio

13 лет назад, # |

Скиньте кто-нибудь код J на Java, познать магию стандартных библиотек при работе с датами.

→ Ответить

MBabin

13 лет назад, # |

Почему относительно мало сдавало A? В Яве же есть готовый gcd для длинных чисел

→ Ответить

stostap

13 лет назад, # |

А что за шутка была в B? Тест 1?

→ Ответить

ant.ermilov

13 лет назад, # ^ |

Вроде в F тоже был первый тест не из условия...

→ Ответить

mmaxio

13 лет назад, # ^ |

Кстати говоря, все тесты и решения жюри доступны: http://neerc.ifmo.ru/past/2005.html

→ Ответить

stostap

13 лет назад, # |

Кто хочеть дорешевать - acm.tju.edu.cn/toj задачи 2723 - 2733

→ Ответить

Kenny_HORROR

13 лет назад, # ^ |

Спасибо. (а то у меня контест шел во время пар и возможности нормально решать не было).

→ Ответить

egorow29

13 лет назад, # |

Ребят, расскажите про решение E, сижу туплю вообще ничего придумать не могу (

→ Ответить

shevchen

13 лет назад, # ^ |

← Rev. 2 →

Просуммируем все возможные исходы независимо по битам. Для i^гобита определим, в составе скольких ксоров он присутствует, и домножим на 2ⁱ. Формула для количества исходных чисел с присутствующим i^мбитом - что-то вроде (N / 2ⁱ⁺¹) * 2ⁱ + max(0, N % 2ⁱ⁺¹ - 2ⁱ) = K. Тогда существует K чисел с единицей и N-K с нулем на i^й позиции. Значит, будет 2*K*(N-K) ксоров с единицей в i^м бите. В конце поделим сумму на N².

→ Ответить

pva701

13 лет назад, # |

а теперь всегда задачи будут на английском?

→ Ответить

zurg	13 лет назад, # \| 0 Подскажите, как правильно решать задачу С? → Ответить

ant.ermilov

13 лет назад, # ^ |

1. найдём бинпоиском высоту H - уровень воды, если положить шар на дно

2. посчитаем k=min(1,p/p0), где p - средняя плотность шара

3. наш объект погрузится в воду на k-ую часть своего объёма, если позволяет H

→ Ответить

zurg	13 лет назад, # ^ \| 0 А как влияет неоднородность шара, кроме как на подсчет средней плотности? → Ответить

ant.ermilov

13 лет назад, # ^ |

У меня вышло, что никак

Вроде силе Архимеда всё равно, из чего состоит тело

→ Ответить

hydrastuff

13 лет назад, # |

Интересны А, H )

→ Ответить

MBabin

13 лет назад, # ^ |

A) - почему-то не сдалась, но вроде как-то так должно работать:

1) Если граф связный, все степени четные и у каждой вершины ни один цвет не встречается больше половины ее степени раз (условие *), то ответ Yes. Это легко доказать - возмем первую вершину и будем ходить по ребрам пока можно (каждый раз проходить через вершину нужно так, чтобы было выполнено *). В итоге у нас получиться цикл, который можно удалить из графа. Потом аналогично найдем новый цикл итд. Осталось объединить циклы в один. Это тоже всегда можно сделать так как любые два цикла можно соединить в 1 (и условие с разными цветами тоже будет выполнено). Отсюда сразу следует алгоритм, но его имхо долго писать.

Я писал немного по другому - постепенно строил цикл и при добавлении ребра проверял, что граф после удаления этого ребра связен и что услове (*) выполнено для предыдущего конца пути.

→ Ответить

niyaznigmatul

13 лет назад, # ^ |

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

→ Ответить

MBabin

13 лет назад, # ^ |

Ясно. А у вас в ИТМО случайно не было разбора как решать F? (вроде это degree sequence of k-edge connected graph) но чето нагуглить не получается. (только для k - connected что-то находил)

→ Ответить

niyaznigmatul

13 лет назад, # ^ |

нет, к сожалению, не было

→ Ответить

MBabin

13 лет назад, # ^ |

H) Не успел ее начать писать. Поэтому скажу тока идею, которая может быть полезна - переведем массив a в массив разностей d (d[i] = a[i] - a[i -1] (это как бы соответствует производной).

Нужно чтобы все d[i] были >= 0. Теперь можно заметить что нам важны тока знаки d[i] (>= 0 соответствует +1 иначе -1) и знак a[1]. Обозначим массив знаков d[] как z[] и знак a[1] как z0, тогда

i-я операция делает такую штуку: (z0 | z[1],z[2]...z[i],z[i+1],...) -> (z[i] | -z[i -1],...-z[1],z0,z[i+1]...).

Понятно как решать за 3n и наверно если немного подумать то получится и за < 2n :)

→ Ответить

MBabin

13 лет назад, # |

Интересно как решать F.

→ Ответить

yarrr

13 лет назад, # |

Расскажите про D (про путь байкеров туда-обратно), пожалуйста.

→ Ответить

hydrastuff

13 лет назад, # ^ |

для четверки из входного файла a, b, c, d

добавляются ребра a->b capa = 1, cost = c,

a->b capa = 1, cost = c+d (если d != -1)

b->a capa = 1, cost = c

b->a capa = 1, cost = c + d (d != -1)

Ищется минкост величины 2.

→ Ответить

Ripatti

13 лет назад, # ^ |

Ну и еще что можно добавить по этой задаче: кратчайшие пути в минкосте очень удобно искать алгоритмом Форда-Беллмана (ограничения позволяют). Моя Дейкстра в потенциалами так и не зашла (да, это те 17 неудачных попыток XD), а Форд-Беллман зашел сразу. Возможно, там еще хорошо проходит Левит.

→ Ответить

hydrastuff

13 лет назад, # ^ |

по времени не зашла? если да то странно

→ Ответить

Ripatti

13 лет назад, # ^ |

Не, WA20. Ошибку так и не нашел.

→ Ответить

CherryTree

13 лет назад, # |

Trainings will be on Wednesday and Saturdays. Start at 16-30.

Может кто-нибудь знает, будет ли сегодня тренировка? Вроде как Wednesday и уже почти 17-00 а все еще BEFORE.

→ Ответить

agul	13 лет назад, # ^ \| 0 В общем-то, неудивительно. ИТМО часто задерживает и тренировки, и интернет-олимпиады. В принципе, ничего страшного - все равно ведь начнут. → Ответить

Gerald

13 лет назад, # |

У меня одного 404 not found на ссылку из условия?)

→ Ответить

hydrastuff

13 лет назад, # ^ |

нет

→ Ответить

MBabin

13 лет назад, # |

У кого нибудь скачиваются условия?

→ Ответить

Jokser

13 лет назад, # |

Условия придумывайте сами :)

→ Ответить

CherryTree

13 лет назад, # |

-18

Аццкий спойлер: E на реализацию. Если, конечно, это та самая E...

→ Ответить

MBabin

13 лет назад, # |

Судя по названиям задач вот ссылка на условия: http://acm.msu.ru/200710/problems.pdf

→ Ответить

agul

13 лет назад, # |

Кто-нибудь знает, почему мне в Messenger'е после посылки выдалось:

17:39

H:1 - null

→ Ответить

aropan

13 лет назад, # ^ |

я тоже много раз отправлял задачу J и получал такой же вердикт... в системе минусы не ставились... я не знал что делать, но потом на третий получил "Compilation error", но у меня же компилиться... вспомнил что там вижла, а не девспп который у меня... переименовал x1,y1,x2,y2 в X1,Y1,X2,Y2 (там проблемы вроде когда cmath подключаешь)... повторим... прошла...

→ Ответить

PER	13 лет назад, # \| 0 ага у меня также было только по задаче G. А после отправки стал compilation error. Что на MS что на GNU компиляторе... Может кто сталкивался и знает в чем проблема?) → Ответить

PER	13 лет назад, # ^ \| 0 все хорошо, теперь прошло)) → Ответить

yahooo

13 лет назад, # |

← Rev. 2 →

-16

я конечно кадр, неправильно понял условие J(про 200ft), начал решать B, сдал ее с +12 еле, еле, потом оказалось что в J обычный бфс(( дописать не успел(((

P.S. и вообще это бл**во, неужели нельзя делать условия rus и en?

→ Ответить

primorial

13 лет назад, # ^ |

← Rev. 2 →

В J обычная жадность решала :)

P.S. А ещё, вполне вероятно, можно было бы и формулу какую вывести.

→ Ответить

yahooo

13 лет назад, # ^ |

← Rev. 2 →

да факт, то что я думал город НхМ, я про футы не понял, что на самом деле (N/200) * (M/200) (ведь так? или я дважды что то не так понял)

→ Ответить

PER	13 лет назад, # ^ \| 0 да это так → Ответить

goryinyich

13 лет назад, # ^ |

Ну вообще от M и N в задаче вообще ничего не зависит (я их после считывания выкидываю), не понимаю, чего вы так кипятитесь =)

→ Ответить

PER	13 лет назад, # \| 0 все таки никак не могу придумать...как же все таки решается А? → Ответить

MBabin

13 лет назад, # ^ |

Рекурсивно. Для нечетных n это сумма арифм. прогрессии, я для четных вызываемся рекурсивно для n/2 - 1. Итого сложноcть O(logn)

→ Ответить

NALP	13 лет назад, # \| ← Rev. 2 → +5 почему нет логинов? мы зарегистрировались давным давно... → Ответить

Edvard

13 лет назад, # |

Кто-нибудь в курсе командные логины вообще могут появиться?

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 19.11.2024 11:41:57 (l2).

Десктопная версия, переключиться на мобильную.

При поддержке