если кому-то интересно покопаться в третьей задаче с тренировки выше - я вроде подобрал код который получает tl5 и ac (и 5 тест за 700ms/2s). Я хоть убей не понимаю в чем большая разница для перфа
въебал в это суммарно час времени, наверное, хочется выучить урок - но пока непонятно, какой
https://codeforces.com/contest/2072/submission/315920027
https://codeforces.com/contest/2072/submission/315920181
въебал в это суммарно час времени, наверное, хочется выучить урок - но пока непонятно, какой
https://codeforces.com/contest/2072/submission/315920027
https://codeforces.com/contest/2072/submission/315920181
Forwarded from Kostya Amelichev
типа solve_naive делает абсолютно то же самое,только она делает одну итурацию, а эта хуйня тут в цикле
Forwarded from Kostya Amelichev
все ифы которые до этого момента зовутся тоже тупорылые за О(1)
Forwarded from Kostya Amelichev
ну то есть асимптотически код одинаковые, все операции память не задействуют, ну может в два раза по константе отличаться должно
закрыл тренировку
1800-2000-2100-2300
https://codeforces.com/problemset/problem/1867/D
https://codeforces.com/problemset/problem/2037/G
https://codeforces.com/problemset/problem/1762/D
https://codeforces.com/problemset/problem/1706/E
17-29-88-111, перф 2355
первая задача какая-то не очень - авторы придумали стремную операцию ради стремной операции и решения в три строки
вторая задача абсолютно дефолтный ицпц на "возьмите 2^различных простых делителей"
третья пиздец выбесила - задача красивая, решение чем-то напоминает k-ю статистику за линию. но только там лимит ну какой-то очень плотный, и надо рандомить элемент, но не попадать в единицу - и я час всякие трюки вертел, чтобы это обойти
четвертая какая-то дефолтная задача на краскала и связности — я может не совсем оптимально решил, но времени было мало - я ебанул снм в снме, один поддерживает компоненты и триггерит обновления снма с запросами, который по факту делает small to large. прикольно, мне понравилось
1800-2000-2100-2300
https://codeforces.com/problemset/problem/1867/D
https://codeforces.com/problemset/problem/2037/G
https://codeforces.com/problemset/problem/1762/D
https://codeforces.com/problemset/problem/1706/E
17-29-88-111, перф 2355
первая задача какая-то не очень - авторы придумали стремную операцию ради стремной операции и решения в три строки
вторая задача абсолютно дефолтный ицпц на "возьмите 2^различных простых делителей"
третья пиздец выбесила - задача красивая, решение чем-то напоминает k-ю статистику за линию. но только там лимит ну какой-то очень плотный, и надо рандомить элемент, но не попадать в единицу - и я час всякие трюки вертел, чтобы это обойти
четвертая какая-то дефолтная задача на краскала и связности — я может не совсем оптимально решил, но времени было мало - я ебанул снм в снме, один поддерживает компоненты и триггерит обновления снма с запросами, который по факту делает small to large. прикольно, мне понравилось
не закрыл тренировку
https://codeforces.com/problemset/problem/2005/C
https://codeforces.com/problemset/problem/1951/D
https://codeforces.com/problemset/problem/2009/G2
https://codeforces.com/problemset/problem/1895/E
10-90-119-x, перф 2212
первая какая-то не задача, просто на то чтобы написать первую пришедшую в голову дп
вторая ну дефолтный конструкив где нужно просто чтобы щелкнуло - у меня полтора часа щелкало
третья на слить две базовые идеи, но я очень хуево успевал по времени, там достаточно много писать и есть формулы на облажаться - в итоге я заслал с пройденного семпла на последней минуте и зашло
https://codeforces.com/problemset/problem/2005/C
https://codeforces.com/problemset/problem/1951/D
https://codeforces.com/problemset/problem/2009/G2
https://codeforces.com/problemset/problem/1895/E
10-90-119-x, перф 2212
первая какая-то не задача, просто на то чтобы написать первую пришедшую в голову дп
вторая ну дефолтный конструкив где нужно просто чтобы щелкнуло - у меня полтора часа щелкало
третья на слить две базовые идеи, но я очень хуево успевал по времени, там достаточно много писать и есть формулы на облажаться - в итоге я заслал с пройденного семпла на последней минуте и зашло
В сб писали финал 15го - ну и две задачи недорешали, их примерно до медалей и не хватило.
На мне было как-то много задач с имплементацией и периодически что-то не шло. В самом начале тура ушел писать минкост в С, пока пацаны что-то другое придумывали. В какой-то момент мне рассказали неправильное условие и неправильное решение F, я сел писать и чуть застрял. Потом переписал и получил TL на дейкстре - пришлось сколько-то времени пихать, чтобы сделать что-то типа бфс-а со стоимостями. Из-за этого тайминги остальных задач съехали: сдал I и сказал, что мне нужно заранее сесть писать М, потому что там тяжело — ну в итоге как-то заранее не получилось, Димон с Е засел. Ну и М отдебажить не успели. За это время еще и Леха H придумал, чтобы обиднее было
ну для меня основной урок в том что на 3.30 имея задачу на разработку, уже плохая идея идти копаться в сложных задачах, надо написать какую-то часть кода, сделать себе отладочный вывод и пойти отлаживаться.
На мне было как-то много задач с имплементацией и периодически что-то не шло. В самом начале тура ушел писать минкост в С, пока пацаны что-то другое придумывали. В какой-то момент мне рассказали неправильное условие и неправильное решение F, я сел писать и чуть застрял. Потом переписал и получил TL на дейкстре - пришлось сколько-то времени пихать, чтобы сделать что-то типа бфс-а со стоимостями. Из-за этого тайминги остальных задач съехали: сдал I и сказал, что мне нужно заранее сесть писать М, потому что там тяжело — ну в итоге как-то заранее не получилось, Димон с Е засел. Ну и М отдебажить не успели. За это время еще и Леха H придумал, чтобы обиднее было
ну для меня основной урок в том что на 3.30 имея задачу на разработку, уже плохая идея идти копаться в сложных задачах, надо написать какую-то часть кода, сделать себе отладочный вывод и пойти отлаживаться.
два раунда еще успел написать и слил рейтинга порядочно
D1+D2 писал после тренировки выше сразу, и как-то уже тяжело было. в Dшке понял что надо делать какую-то математику дефолтную на инварианте, но так впадлу было думать, проскипал. А там в Ешке что-то нормальное выглядело — но я все равно не угадал и не решил. Плохой колл, короче
Примерно то же самое с D2 - там был выбор E/F, я проскипал E, потому что много ок-ов по F было — тоже плохой колл, не справился, а Е простая. половина челов надо мной в див2 - серые (и не только) с чатгпт-посылками, много стал думать о судьбах родины
D1+D2 писал после тренировки выше сразу, и как-то уже тяжело было. в Dшке понял что надо делать какую-то математику дефолтную на инварианте, но так впадлу было думать, проскипал. А там в Ешке что-то нормальное выглядело — но я все равно не угадал и не решил. Плохой колл, короче
Примерно то же самое с D2 - там был выбор E/F, я проскипал E, потому что много ок-ов по F было — тоже плохой колл, не справился, а Е простая. половина челов надо мной в див2 - серые (и не только) с чатгпт-посылками, много стал думать о судьбах родины
И сегодня за обедом в офисе закрыл тренировку
1800-2000-2100-2300
https://codeforces.com/problemset/problem/1990/D
https://codeforces.com/problemset/problem/1702/G2
https://codeforces.com/problemset/problem/1821/E
https://codeforces.com/problemset/problem/1977/D
16-45-57-89, перф 2428
первая прикольная, но я как будто подобную видел. но мне энивей было прикольно придумать жадное доказательство
вторая дефолтное упражнение, только подебажиться надо, минут 15 в помойку
третья прикольная таска, я думал-думал, понял как функцию совсем просто переписать и там решение тогда тривиальное (видно сколько я сдавал, а я за это время успел сходить в туалет и чай заварить). Не понял зачем там ограничение k=5
D прикольная, я сначала долго думал и не знал, как хорошо делать, потом понял, что если дифф между двумя челами равен двум, то это то же самое что от одного отступить единицу, от другого отступить единицу, и посчитать сумму в таких точках. Тогда понятно почему работает сразу, а дальше упражнение на хеши
1800-2000-2100-2300
https://codeforces.com/problemset/problem/1990/D
https://codeforces.com/problemset/problem/1702/G2
https://codeforces.com/problemset/problem/1821/E
https://codeforces.com/problemset/problem/1977/D
16-45-57-89, перф 2428
первая прикольная, но я как будто подобную видел. но мне энивей было прикольно придумать жадное доказательство
вторая дефолтное упражнение, только подебажиться надо, минут 15 в помойку
третья прикольная таска, я думал-думал, понял как функцию совсем просто переписать и там решение тогда тривиальное (видно сколько я сдавал, а я за это время успел сходить в туалет и чай заварить). Не понял зачем там ограничение k=5
D прикольная, я сначала долго думал и не знал, как хорошо делать, потом понял, что если дифф между двумя челами равен двум, то это то же самое что от одного отступить единицу, от другого отступить единицу, и посчитать сумму в таких точках. Тогда понятно почему работает сразу, а дальше упражнение на хеши
не закрыл тренировку
1800-2000-2200-2300
https://codeforces.com/problemset/problem/1824/B1
https://codeforces.com/problemset/problem/1815/B
https://codeforces.com/problemset/problem/1736/D
https://codeforces.com/problemset/problem/1849/E
84-114-х-х, перф ~2050
первую было тяжело решать потому что я неудачно стартовал контест - ко ине внезапно подошел рукль и мы стали работу обсуждать. Из-за этого я вайб плохо поймал и долго дебажил хуйню — в какой-то момент я написал нормально код, но не справился считать ребра дерева в обе стороны, и отлавливал полчаса, наверное.
вторую я уже видел, и задача хорошая - но я уже знал как решать. ну ничего, появился стимул написать, там не очень тривипльно пишется.
третья мне с прочтения показалась не очень сложной, но до деталей реализации я не дошел уже.
1800-2000-2200-2300
https://codeforces.com/problemset/problem/1824/B1
https://codeforces.com/problemset/problem/1815/B
https://codeforces.com/problemset/problem/1736/D
https://codeforces.com/problemset/problem/1849/E
84-114-х-х, перф ~2050
первую было тяжело решать потому что я неудачно стартовал контест - ко ине внезапно подошел рукль и мы стали работу обсуждать. Из-за этого я вайб плохо поймал и долго дебажил хуйню — в какой-то момент я написал нормально код, но не справился считать ребра дерева в обе стороны, и отлавливал полчаса, наверное.
вторую я уже видел, и задача хорошая - но я уже знал как решать. ну ничего, появился стимул написать, там не очень тривипльно пишется.
третья мне с прочтения показалась не очень сложной, но до деталей реализации я не дошел уже.
Codeforces
Problem - 1824B1 - Codeforces
Codeforces. Programming competitions and contests, programming community
ненавижу тч, не закрыл тренировку
https://codeforces.com/problemset/problem/1846/F
https://codeforces.com/problemset/problem/1941/G
https://codeforces.com/problemset/problem/1729/G
https://codeforces.com/problemset/problem/1932/G
9-20-43-[123], перф ~2250
первая не задача — это интерактивка которая сдается за девять минут, о чем речь
вторая не прям плохая, но просто простая — я еще сначала думал как решать с запросами, а потом прочитал и понял что запросов нет — тогда вообще халява на то, чтобы граф пожать
третья немного странная — там понятно, как минимум считать, и понятно, что все выглядит как жадная конструкция, но откуда-то все равно вылезет динамика. написал динамику, увидел что там подмчет способов плохо работает. поставил какую-то полужадную отсечку, стало работать.
четвертая задача это буквально напишите дейкстру и решите a + bt = c + dt mod M. к сожалению я не умею решать такие вещи нормально и каждый раз заново разбираюсь. забыл поделить на гцд, не сдал.
https://codeforces.com/problemset/problem/1846/F
https://codeforces.com/problemset/problem/1941/G
https://codeforces.com/problemset/problem/1729/G
https://codeforces.com/problemset/problem/1932/G
9-20-43-[123], перф ~2250
первая не задача — это интерактивка которая сдается за девять минут, о чем речь
вторая не прям плохая, но просто простая — я еще сначала думал как решать с запросами, а потом прочитал и понял что запросов нет — тогда вообще халява на то, чтобы граф пожать
третья немного странная — там понятно, как минимум считать, и понятно, что все выглядит как жадная конструкция, но откуда-то все равно вылезет динамика. написал динамику, увидел что там подмчет способов плохо работает. поставил какую-то полужадную отсечку, стало работать.
четвертая задача это буквально напишите дейкстру и решите a + bt = c + dt mod M. к сожалению я не умею решать такие вещи нормально и каждый раз заново разбираюсь. забыл поделить на гцд, не сдал.
вчера писали тренировку с пацанами — отрешали херовенько, но че поделать.
я очень обидно нас подставил, потому что в геометрию в М написал проверку на принадлежность точки отрезку сам, а не скопировал с тимбука — из-за этого не зашло на последней минуте.
в остальном я дважды въебал много времени в недоработанные решения. В G мне рассказали какой-то сведенный вариант оригинальной задачи, в которой миллион случаев. Я оригинальное решение не знал, поэтому мы писали кучу тестов и подкладывали заплатки, которых там не хватало.
пока я писал эту задачу, пацаны долго не могли придумать D. Я послушал их сведение и чтобы побыстрее их разгрузить, сказал что пойду делать решение с корнячкой — и тоже над ним завис, там формулы неприятные оказались. После контеста поняли, что там в ДО такую же операцию можно поддерживать, но чуть приятнее.
Остальные интересные задачи я либо не видел, либо даже близко не решил. Ну вот восемь могли сдать, по факту сдали семь. Не фонтан, но пойдет, наверное.
я очень обидно нас подставил, потому что в геометрию в М написал проверку на принадлежность точки отрезку сам, а не скопировал с тимбука — из-за этого не зашло на последней минуте.
в остальном я дважды въебал много времени в недоработанные решения. В G мне рассказали какой-то сведенный вариант оригинальной задачи, в которой миллион случаев. Я оригинальное решение не знал, поэтому мы писали кучу тестов и подкладывали заплатки, которых там не хватало.
пока я писал эту задачу, пацаны долго не могли придумать D. Я послушал их сведение и чтобы побыстрее их разгрузить, сказал что пойду делать решение с корнячкой — и тоже над ним завис, там формулы неприятные оказались. После контеста поняли, что там в ДО такую же операцию можно поддерживать, но чуть приятнее.
Остальные интересные задачи я либо не видел, либо даже близко не решил. Ну вот восемь могли сдать, по факту сдали семь. Не фонтан, но пойдет, наверное.
0x6ABD
ненавижу тч, не закрыл тренировку https://codeforces.com/problemset/problem/1846/F https://codeforces.com/problemset/problem/1941/G https://codeforces.com/problemset/problem/1729/G https://codeforces.com/problemset/problem/1932/G 9-20-43-[123], перф ~2250…
к слову про ТЧ — в субботу писал КФ, такая же проблема — отрешал пару халявок, следующая тоже сравнительно простая на ТЧ. А я уравнение ебучее решить не могу :(. Так что поднял сравнительно мало рейтинга, но хоть оранжевого вернул.
Forwarded from Алиса копается
purplesyringa's blog
Why performance optimization is hard work
I’m not talking about skill, knowledge, or convincing a world focused on radical acceleration that optimization is necessary. Performance optimization is hard because it’s fundamentally a brute-force task, and there’s nothing you can do about it.
This post…
This post…
не закрыл сегодня тренировку
1800-2000-2200-2300
https://codeforces.com/problemset/problem/1965/B
https://codeforces.com/problemset/problem/1682/D
https://codeforces.com/problemset/problem/1840/F
https://codeforces.com/problemset/problem/1699/D
19-57-83-х, perf 2239
первая какая-то не очень сожержательная — явно тип на авторе просто узнал про рюкзак за s sqrt и решил задачу дать на способ создавать веса.
вторая прикольная, но как бы конструктив и конструктив — разве что я вначале неправильно докрутил критерий, пришлось огрести лишний штраф
третья просто напишите бфс, только надо аккуратно чтобы по памяти и времени влезло
четвертая норм такая - надо правильный критерий выдать, а потом на его основе динамику сделать. Я сделал правильный критерий вместе с каким-то продвинутым жадником и не зашло. ну, что поделать, уже досдал
1800-2000-2200-2300
https://codeforces.com/problemset/problem/1965/B
https://codeforces.com/problemset/problem/1682/D
https://codeforces.com/problemset/problem/1840/F
https://codeforces.com/problemset/problem/1699/D
19-57-83-х, perf 2239
первая какая-то не очень сожержательная — явно тип на авторе просто узнал про рюкзак за s sqrt и решил задачу дать на способ создавать веса.
вторая прикольная, но как бы конструктив и конструктив — разве что я вначале неправильно докрутил критерий, пришлось огрести лишний штраф
третья просто напишите бфс, только надо аккуратно чтобы по памяти и времени влезло
четвертая норм такая - надо правильный критерий выдать, а потом на его основе динамику сделать. Я сделал правильный критерий вместе с каким-то продвинутым жадником и не зашло. ну, что поделать, уже досдал
не закрыл тренировку
1800-2000-2200-2400
https://codeforces.com/problemset/problem/1718/A1
https://codeforces.com/problemset/problem/1763/C
https://codeforces.com/problemset/problem/1996/G
https://codeforces.com/problemset/problem/1750/E
15-53-85-x, перф 2276
первую задачу я решал когда-то в хард варианте, но не решил — в этот раз посчитал что надо сделать обе сразу. Постарался и сдал, но подумать пришлось
вторая блин абсолютно бешеная див2С. Там более-менее понятное наблюдение есть, которое отсекает все тесты кроме n=3, но для n=3 там нужно какой-то миллион вариантов вручную проверить (ну или симулировать, но мне впадлу было)
третья выглядит как дефолтная задача на сканлайн + до — ну немного мерзкие индексы и немного мерзкое ДО. может проще можно было
четвертая хорошая, но у меня не было шанса решить — во-первых я неправильно прочитал условие, во-вторых там даже если понять условие правильно, критерий не самый простой. И даже для простого критерия там считать ответ неприятно, я бы не успел
1800-2000-2200-2400
https://codeforces.com/problemset/problem/1718/A1
https://codeforces.com/problemset/problem/1763/C
https://codeforces.com/problemset/problem/1996/G
https://codeforces.com/problemset/problem/1750/E
15-53-85-x, перф 2276
первую задачу я решал когда-то в хард варианте, но не решил — в этот раз посчитал что надо сделать обе сразу. Постарался и сдал, но подумать пришлось
вторая блин абсолютно бешеная див2С. Там более-менее понятное наблюдение есть, которое отсекает все тесты кроме n=3, но для n=3 там нужно какой-то миллион вариантов вручную проверить (ну или симулировать, но мне впадлу было)
третья выглядит как дефолтная задача на сканлайн + до — ну немного мерзкие индексы и немного мерзкое ДО. может проще можно было
четвертая хорошая, но у меня не было шанса решить — во-первых я неправильно прочитал условие, во-вторых там даже если понять условие правильно, критерий не самый простой. И даже для простого критерия там считать ответ неприятно, я бы не успел
не закрыл тренировку
1800-2000-2200-2300
https://codeforces.com/problemset/problem/2022/C
https://codeforces.com/problemset/problem/1827/B1
https://codeforces.com/problemset/problem/1985/H2
https://codeforces.com/problemset/problem/2089/B2
13-34-98-x, перф 2227
первая дефолтная на ебануть дп по плитке, удивлен что за 13 сдал
вторая простая подзадача от B2 Div1, но вроде наблюдение все равно прикольное. я не понял как от лога избавиться в квадрате, ну и ладно
третья выбесила - там более-менее понятно, что надо написать какую-то структурку, чтобы все быстро заработало - ну я написал nsqrt чистый, а он не заходит. ну я сначала пихал бешено, потом забил и додумал как от корня избавиться — не очень просто так-то
четвертую шансов никаких не было - я абстрактно понимаю, что можно сделать в первой подзадаче, и то не целиком — как переносить это на сложную вообще непонятно
1800-2000-2200-2300
https://codeforces.com/problemset/problem/2022/C
https://codeforces.com/problemset/problem/1827/B1
https://codeforces.com/problemset/problem/1985/H2
https://codeforces.com/problemset/problem/2089/B2
13-34-98-x, перф 2227
первая дефолтная на ебануть дп по плитке, удивлен что за 13 сдал
вторая простая подзадача от B2 Div1, но вроде наблюдение все равно прикольное. я не понял как от лога избавиться в квадрате, ну и ладно
третья выбесила - там более-менее понятно, что надо написать какую-то структурку, чтобы все быстро заработало - ну я написал nsqrt чистый, а он не заходит. ну я сначала пихал бешено, потом забил и додумал как от корня избавиться — не очень просто так-то
четвертую шансов никаких не было - я абстрактно понимаю, что можно сделать в первой подзадаче, и то не целиком — как переносить это на сложную вообще непонятно