Форум DL

Мой профиль

01.02.2021 - 21.01.2021

Давно я не отписывался, начну, пожалуй, с дорешки (это, конечно, не вся дорешка, я еще писал сборы и USACO, но об этом позже):
1) https://codeforces.com/contest/1476/problem/F задача с Educational на ДП + ДО;
2) https://codeforces.com/contest/827/problem/D задача на Крускала;
3) https://atcoder.jp/contests/abc191/tasks/abc191_f (ABC 191) задача на теорию чисел;
4) https://codeforces.com/contest/1470/problem/C задача на sqrt-эвристику + диха;
5) https://codeforces.com/contest/1481/problem/F задача на sqrt-эвристику + ДП + жадник;
6) https://codeforces.com/contest/1479/problem/D (CF 700) задача на параллельный дих + хеши + ДО;
7) https://codeforces.com/contest/1479/problem/B2 (CF 700) задача на ДП + жадность;
8) https://codeforces.com/contest/1479/problem/C (CF 700) задача конструктивная, построение определенного графа, используя log вершин;
9) https://codeforces.com/contest/1481/problem/E задача на ДП (догадаться, что с конца писать легче);
10) https://codeforces.com/contest/1474/problem/E задача на математику + жадность;
11) https://codeforces.com/contest/1467/problem/E задача на Эйлеров обход дерева;
12) https://www.codechef.com/problems/ATWNT задача на, своего рода, Meet-in-the-Middle (до корня -- предподсчет, больше корня -- делаем явно, пока не перейдем в число меньше корня);
13) https://www.codechef.com/FEB21A/problems/MULGAME задача на теорию игр (совсем немного) + sqrt-декоммпозиция;
14) https://codeforces.com/contest/1439/problem/D красивейшая задача на ДП.

Теперь стоит поговорить о сборах. Писали мы открытые олимпиады с 13/14 до 17/18 годов. Задачи были хорошими, в каждый год была хотя бы одна задача, которая меня чему-то научила. В целом писал неплохо, совсем плохо написал последний контест со сборов, потому что зациклился на одной задаче. + очень важный вывод, который я сделал за все контест -- часто, когда у меня не работает решение, я отношусь к нему как к "рабочему" и считаю, что проблема в чем угодно, только не в моем коде. Это нужно искоренить. Если решение не работает -- значит я где-то накосячил.

Дорешал все задачи, кроме 2-ух:
1) Задча на ДП, у меня зашла на 98, писал свою идею (как у авторов) на 100;
2) Задача на геометрию + параллельный трих, зашла на 96, писал авторское;

Написал codeforces 700 Div 1. Сдал только A и B1 (слил рейтинг). На контесте долго думал B2 и C, в конце уже решил, что все равно нечего терять и прочитал D. И я ее придумал. Если бы я прочитал D сразу, вместе с B2 и C, то успел бы сдать ее во время контеста.
Дорешал D (своей идеей), B2 и C.

Написал atcoder beginner contest 191. Не сдал F задачу. На контесте придумал все необходимое, но не догадался, что делаю лишние действия в одном месте. С этой оптимизацией сдал задачу.

Написал atcoder beginner contest 192, сдал все задачи, но со несколькими лишними отсылками.

Написали тренировку COCI round 1. Сдал A,B,E полностью, C,D частично. Над С много думал на контесте, но не догадался подумать в сторону РиВ (когда прочитал это слово в разборе, в голове сразу до конца сложился пазл). В Д придумал, что нужно смотреть поддеревья близкие к n/2, но не почему-то не применил это для полного решения.

Написал две тренировки USACO Platinum (December и January). Задачи были довольно сильными, за два дня полностью я решил только одну задачу (еще одну сдал за O(n^3), а нужно было за O(n^2), поэтому тоже много баллов получил). В целом придерживался тактики и все было более менее неплохо. Все задачи уже дорешал.

Прошла олимпиада университета Иннополис (она шла 4 часа). Отрешал на диплом 3-ей степени. Теперь о том, как это было:
Прочитал задачи, сразу решил написать B и сдал ее на +- 48-ой минуте. Решил написать что-нибудь на А. Получил по ней 54 на +- 80-ой минуте (хотя писал, как я думал, на 100). Решил еще подумать над А, потому что она была самой сдаваемой. Придумал контр-тест, стал писать исправленное решение. И весь это процесс придумывания "улучшений решения" и получения очередных WA у меня продолжался до 135-ой минуты, когда я решил, что пора переключиться. К этому времени у меня уже была идея (как я думал) на 80 баллов по задаче D. Я относительно быстро написал это решение и на +- 165 минуте отослал. И получил 0 баллов. Еще минут 10 я воевал, пытался придумать контр-тест, но ничего не выходило. Немного исправил решение, чтобы оно набрало хотя бы 20 баллов (получил я их на +- 180 минуте). У меня оставался час, поэтому я решил забить на все попытки исправить D и пошел набирать баллы брутами по всем задачам. За 20 минут набрал 10 баллов по Е и 37 по С. Еще через 10 минут получил +22 балла по А. После этого я решил вернуться к Д. Попытался написать брут, чтобы взять еще 20 баллов (писал я его на основе старого решения) -- получил 0. И в этот момент, за 20 минут до конца, я осознал, почему мое решение по Д неправильное. Все мои надежды исправить его на 80 и хоть как-то исправить свое положения рассыпались как карточный домик. В этот момент я просто с безумной скоростью начал строчить новый брут, чтобы получить хотя бы еще 20 баллов по задаче Д. И я получил по ней +20 баллов за 8 минут до конца.

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

Мой профиль

Андрей Костяной:

01.02.2021 - 21.01.2021

Дорешал все задачи, кроме 2-ух:
1) Задача на ДП, у меня зашла на 98, писал свою идею (как у авторов) на 100;
2) Задача на геометрию + параллельный трих, зашла на 96, писал авторское;

Я считаю, надо "слезть с пьедестала" и оптимизировать свои реализации.
И авторские решения зашли при установке,
и Саша Лосев сдал обе задачи

1 Лосев Александр  Log Беларусь Гомель СШ 27        10а 800 400 400 
2 Костяной Андрей  Log Беларусь Гомель Гимназия №51 11  794 398 396

Иннополис:
Почти весь контест для меня получился как что-то вроде "придумал-написал-получил-0". Возможно мне стоит попробовать на контесте думать намного больше, чем писать. Потому что сейчас у меня много времени уходит на написание всяких брутов-проверок-жадосов. Возможно стоит сначала все придумать (может даже доказать), а потом уже писать. Да, есть риск, что я неправильно пойму условие и все пройдет плохо. Но сейчас у меня все проходит просто кошмарно.

"Происходит кошмарно" далеко не всегда.
Мне кажется
- думать больше полезно
- отказываться от написания брутов вредно
Как правило, брут пишется быстро, а если он получает 0, то другие решения точно писать бессмысленно.

При том, что ты регулярно отписываешься, очень много решаешь и дорешиваешь,
мне кажется
ты недостаточно качественно анализируешь неудачи и не делаешь правильные выводы из них ...
Поэтому и бывают "сбои", когда "что-то почему-то идёт не так".
Собственно, ты даже свою тактику решения не озвучил до сих пор.
А, по-моему, её надо ЗАФИКСИРОВАТЬ в форуме, и после каждой неудачи вносить в неё улучшающие коррекции.

Мой профиль

Иннополис Опен

Это мой первый анализ, так что постараюсь расписать как можно подробнее.

В начале контеста я прочитал все задачи(10 минут). На первую пришло в голову решение с бинпоиском, на вторую сразу же придумал дп, на 3-5 вообще не представлял что могло быть.

Решил писать первую задачу, а вторую оставить на потом. Написал свою идею, она взяла 54 балла а дальше ловила WA. Я попытался её пооптимайзить, но она всё равно ловила WA. В итоге на конце первого часа у меня было 54 балла.

Дальше я принялся писать вторую. Написал её минут за 30, а на дебаг ушло больше часа. В итоге сдал её за 1,5 часа. Дальше я прооптимайзил первую до 76(20 минут). У меня оставался час с копейками, и я попытался попридумывать 3, т.к. много у кого по ней было 37. В итоге после получаса я не смог придумать ничего толкового.И сел придумывать и писать 4. На четвёртой идею на 20 придумал за 5 минут и сел писать её. Но в итоге заслав на предпоследней минуте она словила WA.

И по итогу я получил 176 баллов. За последний час получил 0 баллов.

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

Мой профиль

Дмитрий Горбатовский:

Иннополис Опен
Я думаю, что моя основная ошибка - много думаю, но мало пишу.

Не уверен, что это ошибка, но предлагаю ЗАФИКСИРОВАТЬ тактику. А в ней и распределение времени между пишу/думаю. И затем, при необходимости, менять это распределение в нужную сторону.

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

АБСОЛЮТНО ТОЧНО.
И вот подтверждающие цифры:
Твой основной соперник на ближайшие три года
Полынь Станислав из Мозыря https://codeforces.com/profile/stanislau

всего решил        1438 задач
за последний год    510
за последний месяц   27

Ты https://codeforces.com/profile/topovik

всего решил         249 задач
за последний год    181
за последний месяц   10

Сделать правильные выводы - уже полдела.
Но и вторую половину тоже нужно сделать - интенсифицировать ДОРЕШИВАНИЕ.
- на DL
- на Codeforces

Мой профиль

Прошёл распределительный контест в ЗКШ. Подумал, что стоит отписаться, так как ошибок было много, но сам их не знаю.

Дали 6 задач на 4 часа.
Задачу А сдал на 4-ой минуте с небольшими затупами, так как из-за спешки не дочитал, что нужно строить квадрат.
Прочитал задачу В, решил написать проверку на двудольность + жадник. В итоге словил WA2 и не ОПЯТЬ не дочитал условие(надо было выводить лексиграфически меньшую строку).

С этого момента я вошёл в ступор, так как не было никаких идей в голове. Пошёл читать задачи дальше. Прочитал Сшку, была идея с жадником, но я не смог доказать его правильность. Е показалась мне очень простой. Написал на неё ДО + ДП и словил WA4. В этот раз я недопонял условие задачи. Написал жадник и словил WA8, что мне показалось подозрительным намёком на идею с фуллом.

Переключился на Вшку и дописал туда ДП, которое я придумал перед прочтением Eшки, и сдал с +2(2 неверных посылки были неверными иедями).
И снова я переключился на Ешку, решил написать "разделяй-и-властвуй" на неё, основываясь на жаднике. В итоге сдал с +10(все 10 неверных посылок - неверные идеи).

Прочитал Dшку, придумал решение сразу и сдал с плюсика. Решил на Сшку написать тот жадник, который придумал изначально, но не доказал. Сдал с плюса.
На Fку была идея через повороты на 90 градусов точек на плоскости, но все варианты решений ловили WA2(не знаю почему именно).

В итоге отрешал на 60-ое место с огромейнешим штрафом в виде 789 минут.

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

Мой профиль

Александр Лосев:

ошибок было много, но сам их не знаю.

А мне показалось, что ты их явно указал, перечислю

1. Спешка
- как результат - недочитывание условий (задачи A и B)

2. Спешка
- как результат - недопонимание условий (задача E)

3. Спешка
- как результат - реализация неверных идей (10 штук в задаче E)

Но это дело поправимое - надо просто успокоиться и перестать спешить.

Из положительного

1. Умеешь "держать удар"
- после всех проблем всё-таки сдал 5 задач,
значит и знания/умения есть и крепкие нервы.

2.

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

Положительные качества - усиливать,
от отрицательных (спешки для начала) - избавляться.

Мой профиль

Андрей Костяной не в той ветке отписался, а за ним и я, и Данченко Алексей (выпускник СШ 27, двухкратный медалист IOI)

Мой профиль

22.02.2021 - 01.03.2021

Начну с дорешки:
1) https://csacademy.com/contest/romanian-ioi-2017-selection-1/task/rooms/statement/ задача на ДП + крутая идея, похожа на одну из задач USACO;
2) https://codeforces.com/contest/1485/problem/E задача на ДП + жадность;
3) https://codeforces.com/contest/1485/problem/F задача на ДП;
4) https://codeforces.com/contest/1487/problem/G ДП + жадность + немного комбинаторики;
5) https://codeforces.com/contest/1492/problem/E задача идея + жадность;
6) https://codeforces.com/contest/1486/problem/F задача на ССД + чуть-чуть комбинаторики;

Сейчас начались сборы ЗКШ. Прошел распределительный контест + 3 контеста тренировочных. Распределительный, 1-ый и 2-ой тренировочные я написал хорошо.

Хочу обсудить 3-ий, который написал совсем не очень. Было 4 задачи проходные, сдал их на +- 1 час 40 минут. Оставалось 2 задачи: G -- геометрия, H -- какая-то задача на графы. Естественно я выбрал H (дополнительным поводом стало то, что к этому времени ее уже сдали на контесте). Я думал над этой задачей довольно долго, около часа, писал проверки всякие, но ничего не выходило. Поэтому я решил, что нужно переключиться и пошел думать G. Придумал ее минут за 20 и начал печатать. Где-то за 30 минут до конца я закончил писать, но тут подумал, что моя идея совсем не правильная и решил переключиться на H. По итогу до конца контеста я так ничего и не сдал.

Но самое обидное произошло, когда я открыл разбор. Потому что на задачу G было +- мое решение. И я его довольно быстро смог подправить и сдать.

Выводы:
1) все равно не отклоняться от стратегии (пункт, что я думаю над задачами по очереди), даже если задача не на любимую тему / еще не сдана или сдана небольшим кол-вом людей;
2) если у меня в конце контеста есть хоть что-то по одной задаче, но ничего по другой (а именно так у меня и было с задачами G и H), то я пытаюсь добить задачу, где у меня что-то написано.

Все задачи со всех контестов ЗКШ уже дорешал.

Также написал CF Global 13. Написал его не очень + задача упала на систестах, но был очень положительный момент.
На контесте к 1 часу 30 минутам у меня были сданы только A и B, я был совершенно подавлен. У меня уже бывало такое на контестах (и на олимпиадах тоже) и обычно это заканчивалось тем, что я просто в таком настроении плохо заканчивал контест. Но в этот раз пришла мама и просто посидела рядом со мной. Я начал вслух рассказывать решения и придумал задачу Е! После этого у меня поднялось настроение и я быстро сдал C и D (в которых до этого тупил и не мог придумать решения).

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

Дорешал с этого контеста F, H, также планирую дорешать G.

Мой профиль

Андрей Костяной:

22.02.2021 - 01.03.2021

Оставалось 2 задачи: G -- геометрия, H -- какая-то задача на графы. Естественно я выбрал H (дополнительным поводом стало то, что к этому времени ее уже сдали на контесте). Я думал над этой задачей довольно долго, около часа, писал проверки всякие, но ничего не выходило. Поэтому я решил, что нужно переключиться и пошел думать G. Придумал ее минут за 20 и начал печатать. Где-то за 30 минут до конца я закончил писать, но тут подумал, что моя идея совсем не правильная и решил переключиться на H. По итогу до конца контеста я так ничего и не сдал.

Классический случай
- "за двумя зайцами погонишься, ни одного не поймаешь"
- "проблема буриданова осла"

Но я не понял.

1. " ... подумал, что идея не правильная".
- ты придумывал, потом ПИСАЛ(!) и только потом "... подумал, что идея не правильная"
А как на самом деле была идея правильная или не правильная?
Мне кажется, надо исключить "как класс" такие ситуации, когда ты
- придумываешь решение
- ПИШЕШЬ КОД
- а после завершения написания кода понимаешь, что идея не правильная.
КАК?
Тебе и придумать!

2.

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

Но самое обидное произошло, когда я открыл разбор. Потому что на задачу G было +- мое решение. И я его довольно быстро смог подправить и сдать.

А поподробнее, что значит "ничего не выходило", а после открытия разбора "+-моё решение"?
Этот более подробный анализ также нужен для того, чтобы исключить "как класс" и такие ситуации.
Когда ты отрекаешься от "+- правильного решения",
то есть "в 15 минутах работы от правильного решения"

Все задачи со всех контестов ЗКШ уже дорешал.

Это очень правильно.

написал CF Global 13. На контесте к 1 часу 30 минутам у меня были сданы только A и B, я был совершенно подавлен. У меня уже бывало такое на контестах (и на олимпиадах тоже) и обычно это заканчивалось тем, что я просто в таком настроении плохо заканчивал контест. Но в этот раз пришла мама и просто посидела рядом со мной. Я начал вслух рассказывать решения и придумал задачу Е! После этого у меня поднялось настроение и я быстро сдал C и D (в которых до этого тупил и не мог придумать решения).

У тебя крутая мама, и у Вас отличная коммуникация.
НО, предлагаю в следующий раз в такой ситуации, даже при решении задач дома, действовать "как в бою".
- заведи себе талисман, который возьмёшь на контест с собой и рассказывай ему.
- или просто ЗАПИШИ СВОЙ рассказ на бумаге
- и, главное, ВЕРЬ В СЕБЯ - у тебя очень крутая подготовка и помни про "лягушку в сметане"

Мой профиль

А как на самом деле была идея правильная или не правильная?

Идея была в целом правильная. Я свел задачу к двум:
1) посчитать ф-цию для отрезков (эта часть полностью правильно была придумана и написана на контесте);
2) посчитать ДП, используя ф-цию из 1-ого пункта. Вот тут я все правильно придумал с dp[l][r], но когда дописал, то я подумал, что тут ДП не подходит, потому что есть плохой случай. А на самом деле этого случая не было;

А поподробнее, что значит "ничего не выходило", а после открытия разбора "+-моё решение"?

+- мое решение уже объяснил, что значит.

Ничего не выходило: я не мог придумать, за что зацепиться в задаче. Все наблюдения были поверхностными.

Мой профиль

Андрей Костяной:

2) Вот тут я все правильно придумал с dp[l][r], но когда дописал, то я подумал, что тут ДП не подходит, потому что есть плохой случай. А на самом деле этого случая не было;

Гоголь рукопись сжёг - якобы плохо написал - в литературе оценка субъективна
Но у тебя счётная позиция
Как это ты обнаружил плохой случай, если его не было?
Надо как-то в тактику внести алгоритм НАДЁЖНОЙ проверки таких ситуаций.

Вспомнилось по аналогии - Коржик -Дзвинковский, писать много, устно расскажу если спросишь.

А поподробнее, что значит "ничего не выходило", а после открытия разбора "+-моё решение"?

+- мое решение уже объяснил, что значит.
Ничего не выходило: я не мог придумать, за что зацепиться в задаче. Все наблюдения были поверхностными.

Так подожди, у тебя просто не было решения,а не "+- моё решение".

Мой профиль

В разборе было +- мое решение по задаче G (которое я успел написать на контесте). Я говорю +- мое, потому что они по-другоиу решали 1-ый пункт, но это существенной роли не играет.

По задаче H у меня действительно не было никакого решения.

Мой профиль

Да, извини, я немного запутался в этом.

Мой профиль

how can i improve my thinking ability

Полезно почитать ответы

Из новенького

Also, I started keeping a Google doc of difficult/interesting problems that I couldn't solve on my first try. I find that doing a short write-up of a difficult problem after you solve it really helps you to understand the ideas, which is important because that's what will help you when solving similar problems in the future.

Solve questions not for color but for fun.

Мой профиль

Андрей, мои поздравления
Досрочно закрытый контест и первое место