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.

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!

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.

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.