Это мое первое участие в соревнованиях Codeforces, и вроде даже удачное. Задачки довольно простые, но на то он и второй дивизион.
В соревновании участвовало 404 человека, и сервер довольно долго проверял решения. Этот момент внёс некоторые особенности в тактику. Так, в условии задачи C, как я ни искал, я не нашёл того, что после "подсказки" никнейм с номером попадает в базу. Тем не менее я чудом угадал что имели в виду авторы. Т.к. я не был уверен в первом решении, я сразу поправил его и отправил снова, с другим пониманием условия. C задачей D я поступил так же, после первого сабмита рекурсивного решения, я написал второй вариант уже без рекурсии, из-за опасения тайм лимита и/или багов.
В итоге я послал 6 решений на 4 задачи и все они прошли все тесты. Это произошло главным образом из-за того, что очень много сабмитов, и система не успевает быстро их все проверять. Забавно, но это только увеличило число сабмитов, думаю не я один такой, кто посылал ещё решение, не дождавшись вердикта.
Надеюсь выбранная мною тактика не станет особенностью соревнований. В связи с этим предлагаю:
1) Не проверять решения по тем задачам, которые уже сданы.
2) Рассмотреть возможность распараллеливания проверки.
распараллеливаются разные участники, или проверка одного решения распараллеливается на несколько серверов?
второе думаю может тормозить.
Пусть открытка это конверт с номером 0, остальные занумеруем от 1 до n. Теперь нам нужно нулевой конверт вложить в максимальное число других, ясно что отношение "вкладывается" не содержит циклов, т.к. размер того конверта, в который мы складываем должен быть строго больше по обоим измерениям.
ДП: определим D(x) как максимальное число конвертов, в которые можно вложить конверт x, пересчитывается очень просто - просто перебираем конверт y в который непосредство вложим конверт x и D(x) = Max(D(y) + 1) по всем y в которые вкладывается x
код:
http://www.everfall.com/paste/id.php?hyznn3vt1bqm
В сэмплах же буквы строчные :)