Edited by author 08.05.2006 13:57

didn't you ment memory limit ?

Or do you mean only future problems?

Edited by author 08.05.2006 14:38

Do you mean problems, which have Memory limit more than 16 MB now or ALL the problems?

ML will be increased for most of problems with ML < 16 MB. Some exclusions: 1220, 1275, 1306, 1307. The full list will be announced later.

What about
 1176
 1238
 1276
?

So, some little bit easier solutions will be accepted for 1176 and 1276. It's not the problem.

What's the problem with 1238?

Edited by author 08.05.2006 23:42

Many people had solved problems with the old limitation so I think the new limitation should be applied only for new problems.
The limitation of memory sometimes makes programmers optimize their code, use less memory and I think it's a part of programming.

You are right. But people use this server to train in programming ICPC-style problems. At the most of ICPC competitions contestants are provided a lot of memory for their programs (usually, 16-64 MB). So, we want to keep our rules up to date.

Besides, not so many problems force programmers to optimize their memory use now. A part of them keep its ML unchanged.

Historically most our first problems (volumes 1-3) were desined to be solvable with DOS compilers. From this it follows that default ML was 1000 KB for a long time. But now  everybody use 32-bit compilers and this constraint is useless.

Edited by author 09.05.2006 13:34

1238
http://acm.timus.ru/forum/thread.aspx?space=1&num=1238&id=9917&upd=632218806268738340

1276
I use [0..40/4,0..40/3,0..40/2,0..40/1]
but with 16Mb it possible do with
  [0..40,0..40,0..40,0..40]
it so easy.


and what about 1253?

I think it's not so important.
And this is too ;-)
besides, array[0..40,0..40,0..40,0..40] of int64 is 21MB !!!
Ok, what if ML will be 4MB for this problem?
Solution with 10^6 of memory is not so easier than optimal solution.

Edited by author 09.05.2006 15:23

These problems will keep its current MLs:
1220 - 0.75 MB
1275 - 0.5 MB
1306 - 1 MB
1307 - 2 MB
1395 - 4 MB

These problems will have bigger MLs but lower than 16 MB:
1144 - 4 MB
1148 - 4 MB
1171 - 4 MB
1175 - 2 MB
1269 - 8 MB
1276 - 4 MB

Any suggestions?

Edited by author 12.05.2006 13:56

1320 - Should be solved without adjacency matrix. Otherwise become much easier.
1367 - The trick is to fit ML. And I think 8 Mb (instead of 10  Mb now) is quite enough.
1269 - Suffix trees should not waste memory.
1100 - The trick is to fit ML.
1137 - The trick is to fit ML.
1048 - Just read my mail.

I might find some more...

1320, 1137 - using adjacency matrix will not make problem MUCH easier. Because these problems are VERY EASY now.
1100 - can be solved without any memory tricks now. Most of people solved it such way.
1367 - some additional memory will not make problem mush easier, but allow to use handier structures.
1269 - it's a debatable question. Maybe memory limit will be keeped unchanged
1048 - Just read my mail

1269 is a problem with practical applications, and speed is more important than spent memomy in this case. So increase memory to at least 10Mb please, then it will be possible to get AC by Aho-Corasick mega-DFA in 0.05 sec (I hope).

My Aho-Corasick required 2 MB only

Of course, 2Mb is satisfactory, but I tryed to make as hasty program as possible and added bit array with size 100000*256/8 that notes if exits new condition of DFA. So, additional memory could speed up Aho-Corasick more and more.

Yes, it would be nice. I think, ML should be 8 MB.
Do you agree?