Форум DL

Мой профиль

Гомель: 2048 манулов:

Михаил Долинский:

с 10.31 до 12.54 - почти 2.5 часа на сдано ни одной задачи - так нельзя. Почему так получилось?

После сдачи Виталиком 6-ой задачи у Саши были уже идеи на 3 задачи(A, C, J). Виталик прочитал Сшку, Саша рассказал идею, тот согласился и Саша пошёл её писать.
После того, как Саша словил WA, Виталик уже прочитал J и Саша ему рассказывает свою идею. Так как Виталик не знал, как пишется 0-1 BFS, вместо него написал обычную Дейкстру(в авторском оказалось, что надо было писать 0-1 BFS). Виталик задачу кодил очень долго, тем временем Саша искал баги в С на листочке. Виталик заслал, получил WA36 и начал искать баги(у Саши в этот момент ничего не нашлось). Через какой-то промежуток времени решили вдвоём поискать баги в С, тем самым переписав некоторые куски кода на более точные по работе. Заслали - сдали.
После сдачи С Саша рассказал идею на А. Виталик смутился в ней и не согласился давать ему комп. Решили искать баги в J. Исправляли некоторые моменты в коде - безуспешно. А найти тест, где падали эти моменты в коде, не могли. Перед тем, как Саша уговорил Виталика писать А, Саша придумал ещё задачу F

1. Стратегически

Как оказалось,
были придуманы (после первых 6 сданных) ещё 4 задачи
A C J F
- C сдали, но потратили 2.5 часа на неё
- J не сдали вообще (потратили те же 2.5 часа или даже больше поскольку работали по одному)
- A сдали минут за 40
- F не писали (а какова оценка по времени её реализации?)
Может выбор порядка написания задач был не совсем верным?
Вы оцениваете время на реализацию?
Учитываете это время при выборе, что писать?
Может если на задачу требуется 2.5 часа
есть смысл подумать (хотя бы какое-то ограниченное время)
и попытаться придумать решения других задач?

2. Тактически

- здорово, что вы ВМЕСТЕ справились с задачей С
- здорово, что пытались вместе сдать задачу J
... плохо, что не справились с ней
... повторюсь, надо продумать и ЗАФИКСИРОВАТЬ тактику поиска ошибок
- а Дейкстрой решается задача J?
- BFS 01 - ставить некоторые элементы, как обычно, в конец очереди,
... а некоторые - в начало (сокращая размер очереди)
... мне кажется, тут большого предварительного опыта и не требуется

- может всё-таки надо было задачи C и J сразу писать вместе (сначала одну задачу, потом другую)
- как правильно определять, когда переходить на совместное написание решений?

Мой профиль

Дорешал J с плюса
0-1 бфс и Дейкстра у меня зашли
В отличие от Виталика, я всегда пишу как можно больше процедур и функций, чтобы легче было искать баги в коде и легко его читать
Восстановление ответа я реализовал совсем по-другому, нежели Виталик

Мой профиль

Как искать ошибки:
1) Чтение кода
2) Ручные тесты
3) Генератор тестов + брут для проверки

Мой профиль

Библиотека крайних случаев

Геометрия - вертикальные и горизонтальные отрезки

Мой профиль

Я уверен, Вы все трое Саша, Виталий, Дима должны бороться за поездку на IOI 2022

Андрей Костяной при обсуждении результатов IOI 2021 сказал, что главная его проблема была
в том, что он не смог придумать решения.
Он даже высказал мысль, что «придумывать решения» - это вообще способность «от рождения».

Я с ним категорически не согласен.

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

На лето задание такое

1. Решение и дорешивание воскресных командных олимпиад.

Обсуждение во время олимпиад позволяет Вам обмениваться идеями и опытом.
Дорешивание и знакомство с авторскими идеями расширяет Ваш арсенал.
Замечу также, что задачи ВКОШП, которые мы решаем по воскресеньям –
особенно те, что посложнее - тоже во многом на придумывание идей

2. Аналогично надо регулярно решать раунды Codeforces,
дорешивая задачи которые лежат в зоне Вашего ближайшего развития

3. Прочитать книгу Пойа "Как решать задачу"
(это про задачи по математике и написано очень много лет назад)
И тем не менее, уверен внимательное и критичное прочтение позволит Вам составить собственную версию
«как решать задачу» для нынешних реалий.

4. Порешать задачи Кенгуру, Бобёр, Kangaroo и Bebras на DL (курс "Математика" )
Лучше всего по годам от свежих старым.
По времени – например 3 часа. Хотя бы два раза в неделю.
Можно от старших классов к младшим.
А можно и наоборот – в порядке возрастания сложности.
У младших тоже есть заковыристые задачи, которые заставят поломать голову.

5. По результатам 3 и 4 составить и выложить в форуме свою версию «Как решать задачу».
Для последующего совместного обсуждения.

В сентябре пойдём дальше.

Мой профиль

Я не хотел сказать, что заниматься вообще не имеет смысла.

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

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

Мой профиль

ВКОШП 2012

Саша - A, D, G, K
Виталик - B, E, I
Дима - D

A +4 (неверно понял один момент в условии)
B +
D +
E +
G +
I +6 (неверные формулы)
K +6 (не проверял повторяющиеся ответы в выводе)

Ошибки:
1) Саша долго провозился в K, а если точнее, то целый час
2) В общем долго над лёгкими задачами возились, из-за чего не осталось времени на сложные

Мой профиль

Мой конспект книги Пойа "Как решать задачи"

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

- внимательно, многократно и с разных сторон рассмотреть главные элементы задачи
- если возможно - сделать чертёж/графическое представление задачи
- должен быть опыт решения задач
- известна ли Вам какая-то родственная задача – с тем же неизвестным
- можно ли сформулировать нашу задачу иначе
- если не удаётся решить исходную задачу – поставить и решить подводящую
- все ли данные использованы?

- Что я могу сделать?

Рассмотрите задачу с различных сторон. 
Делайте упор на различные элементы.
Исследуйте различные детали.
Исследуйте одни те же детали по нескольку раз с различных точек зрения.
По-разному сопоставляйте детали, подходите к ним с различных сторон.
Пытайтесь усмотреть новое в каждой детали.
Некоторую новую интерпретацию задачи в целом.

Краткий эвристический словарь

Аналогия

Без большого напряжения нельзя решить задачу. 
Но от напряжённого сосредоточения внимания на одном предмете быстро наступает усталость.
Чтобы удержать внимание, предмет, на который оно направлено, должен постоянно меняться.
Способы варьирования задачи, которые часто полезны:
    - возвращение к определениям
    - разложение и составление новых комбинаций
    - введение вспомогательных элементов
    - обобщение
    - специализация
    - использование аналогии

- сумма кубов чисел есть квадрат суммы   (чисел 1,2,..n)

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

Мой профиль

ВКОШП 2011

Дима - A, F, I
Виталик - E, K
Саша - D, G, H, I

A +
D +
E +1 (мелкие баги)
F +
G +
H +4 (сначала не отсортил по времени, потом выводил неправильно, так как забыл номера сохранить

)
I +1 (первым решением была неверная идея)
K +2 (изначально Виталик не так понял условие(думал, что надо считать колво детей на расстоянии не менее k) + неверно написанный small-to-large)

Саша предлагал Виталику написать на K решение проще и быстрее, чем small-to-large с ordered_set, тем самым словив минимальное количество багов. Но Виталик написал свою идею
Саша прочитал разбор: некоторые моменты он рассказал так же, как и в разборе, но не подумал о том, что сортировку стеком можно заменить ПСП

Мой профиль

ВКОШП 2010

Саша - D, F, I
Виталик - C, E, J, G

C +13 (0 в степени 0 является неверной операцией)
D +2 (в условии выйгрывает тот, кто больше либо равно n набирает, а Саша понял иначе)
E +
F +
G +
I +
J +

ВНИМАТЕЛЬНО ЧИТАТЬ УСЛОВИЕ!!!

Мой профиль

ВКОШП 2009

Саша - B, D, F
Виталик - G, H
Дима - I, K

B +13 (куча мелких недочетов)
D +
F +
G +5 (одна посылка - брут, в остальных - забыли модуль в одном месте поставить)
H +2 (неверная идея)
I +
K +

Мой профиль

ВКОШП 2008

Саша - B, C, F, G
Виталик - A, D, G, H
Дима - D, E, G

A +3 (неверно понял условие)
B +
C +1 (забыл continue)
D +5 (неверно проверяли, какие ребра можно добавлять)
E +
F +1 (неверно восстанавливал ответ)
G +1 (писали отрезок как [; ], а не как [; ) )
H +5 (все минусы - поиск багов)

Как понять, что решать надо вместе?
1) когда решаешь задачу более 30 минут(+штрафное время, 10 минут за посылку)
2) когда не можешь придумать идею за 20-30 минут
3) когда на задачу рассчитывается много времени(40+ минут), то сразу за комп добавляется второй человек

Мой профиль

Гомель: 2048 манулов:

Саша - B, C, F, G
Виталик - A, D, G, H
Дима - D, E, G

Так ненаглядно, может лучше как-то так

Саша    - B, C, F,    G
Виталик - A, H,    D, G
Дима    - E,       D, G

Мой профиль

отбор на ВКОШП 2020

Саша - A, B, C, D, E, F, I, K

A +
B +4 (неверные формулки)
C +2 (не дочитал условие)
D +8 (взял в одной книге идею для построения выпуклой оболочки множества точек - не зашло, взял из другой - зашло)
E +1 (слишком много перебирал)
F +
I +2 (изначально неверно оценил время работы кода, из-за чего брало тл)
K +

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

Мой профиль

отбор на ВКОШП 2020

Саша - A, B, C, D, E, F, I, K

A +
B +4 (неверные формулки)
C +2 (не дочитал условие)
D +8 (взял в одной книге идею для построения выпуклой оболочки множества точек - не зашло, взял из другой - зашло)
E +1 (слишком много перебирал)
F +
I +2 (изначально неверно оценил время работы кода, из-за чего брало тл)
K +

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