ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1181. Разрезание окрашенного многоугольника

Wrong limitations
Послано Fyodor Menshikov 25 дек 2008 12:08
From moment of creation of this problem (16 Feb 2002) and till 6 Jun 2006 there was no solution that uses more than 1Mb of memory.

I think that original ML was 1 Mb.

Now problem has ML 16 Mb, and there are ~40 solutions (<10% of all) that use more than 1 Mb.

Is it possible to lower memory limit of this problem to 1 Mb?

1Mb does not allow DP table of size N*N/2 of 2-byte integers.
Re: Wrong limitations
Послано Vedernikoff Sergey (HSE: EconomicsForever!) 25 дек 2008 18:15
Following you logic, let's instead increase N to, say, 5000. It's not correct to change rules of the game after they were established and some authors ACed solutions under new limitations!
Re: Wrong limitations
Послано Fyodor Menshikov 25 дек 2008 21:09
Beauty of this problem in that it looks like trivial DP but can be solved using original algorithm much more effective.

There is no much sense in having one more standard DP problem. But there is much more benefit for solvers in creating absolutely new algorithm and obtaining new knowledge.

I think that current state is fault of people who 2 years ago increased ML for almost all problems not thinking of side effects. As result some problems become meaningless and silly.

I think that 2 years is not so long time, and its possible to return meaning to problems that lost it after ML increase.
Re: Wrong limitations
Послано Fyodor Menshikov 25 дек 2008 21:21
Vedernikoff Sergey (HSE: EconomicsForever!) писал(a) 25 декабря 2008 18:15
Following you logic, let's instead increase N to, say, 5000.

I considered this idea. To create new problem with the same statement and greater limitations. But after problem statistics analysis (<10% solutions would fail that new problem) I came to conclusion that it would be better to remove AC from 10% than force 90% to submit identical solutions to two problems.