Now program has ML 16 Mb. It allows reading whole input into memory.

But original conditions in year 2000 were completely different. Turbo Pascal and 500 kb of heap. And original solution uses O(1) memory.

Is it possible to lower ML for this problem to 1 Mb, so that it would be impossible to read whole input into memory?

I think 1MB is too small memory limit.
I solved this problem without using arrays on C#, but my memory equals 2625КБ ~ 3MB
Code here: [deleted]
Or there exist some ways to optimize my solution?

Edited by author 13.07.2010 21:54

Edited by author 24.07.2010 11:16

I don't know C# very well, but I know Java which is very similar to C# in memory requirements.

I think that static void print(object o) { Console.Write(o); } in your solution (by the way, correct solutions are disallowed by the rules of this forum) may create up to 1 000 000 temporary objects (garbage). Try to output bytewise without any intermediate objects. I don't know if it is possible in C#, but in Java it allowed me to use less than 1 Mb in problems marked in FAQ as unsolvable in Java/C#.

Thx. I am going to write new read/write functions using bytewise idea.
Sorry for AC code, I have already deleted it.

PS
Can you show me your JAVA template with read/write functions?
I cannot find anything about reading/writing data bytewise in C#... even some examples.

Edited by author 24.07.2010 11:29

import java.io.*;
import java.util.*;

class Scanner {

   InputStream in;
   char word[] = new char[4];
   char c;

   Scanner(InputStream in) {
      this.in = in;
      nextChar();
   }

   void asserT(boolean e) {
      if (!e) {
         throw new Error();
      }
   }

   void nextChar() {
      try {
         c = (char)in.read();
      } catch (IOException e) {
         throw new Error(e);
      }
   }

   void skipSpace() {
      while (c == ' ' || c == '\r' || c == '\n') {
         nextChar();
      }
   }

   char[] next() {
      skipSpace();
      int pos = 0;
      while ('A' <= c && c <= 'Z') {
         word[pos] = c;
         pos++;
         nextChar();
      }
      asserT(pos > 0);
      while (pos < 4) {
         word[pos] = 0;
         pos++;
      }
      return word;
   }

   int nextInt() {
      skipSpace();
      asserT('0' <= c && c <= '9');
      int value = 0;
      while ('0' <= c && c <= '9') {
         int digit = c - '0';
         asserT(value <= (Integer.MAX_VALUE - digit) / 10);
         value *= 10;
         value += digit;
         nextChar();
      }
      return value;
   }
}

class PrintWriter {

   OutputStream out;
   int digits[] = new int[10];

   PrintWriter(OutputStream out) {
      this.out = out;
   }

   void println(int value) {
      try {
         int pos = 0;
         do {
            digits[pos] = '0' + value % 10;
            pos++;
            value /= 10;
         } while (value > 0);
         while (pos > 0) {
            pos--;
            out.write(digits[pos]);
         }
         out.write('\r');
         out.write('\n');
      } catch (IOException e) {
         throw new Error(e);
      }
   }

   void close() {
      try {
         out.close();
      } catch (IOException e) {
         throw new Error(e);
      }
   }
}

thanks a lot!

This problem so fun if ML 16mb.In first I have 3 arrays, but ML 4 test, then I delete 1 array and rewrite one of the two arrays with input.After very boring summing 2 arrays and AC 1,1sec and (so fun) 13mb.So this problem simple long sum 2 arrays...

Edited by author 07.10.2011 00:15