ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1048. Superlong Sums

Wrong limitations
Posted by Fyodor Menshikov 25 Dec 2008 01:44
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?
Re: Wrong limitations
Posted by SKYDOS [Vladimir SU] 13 Jul 2010 21:54
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
Re: Wrong limitations
Posted by Fyodor Menshikov 24 Jul 2010 03:17
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#.
Re: Wrong limitations
Posted by Andrew Hoffmann aka SKYDOS [Vladimir SU] 24 Jul 2010 11:18
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
Re: Wrong limitations
Posted by Fyodor Menshikov 26 Jul 2010 02:10
Andrew Hoffmann aka SKYDOS [Vladimir SU] wrote 24 July 2010 11:18
Can you show me your JAVA template with read/write functions?

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);
      }
   }
}
Re: Wrong limitations
Posted by Andrew Hoffmann aka SKYDOS [Vladimir SU] 26 Jul 2010 02:48
thanks a lot!
Re: Wrong limitations
Posted by rodge(Vologda SPU) 3 Oct 2011 21:00
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