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 1220. Stacks

Memory Limit. Dont know why. Pls help me to understand where i am wrong.
Posted by intueor 20 Aug 2015 16:42
I hope somebody will explain me what's wrong with my program, cause I really dont understand why i get out of memory (900KB) when my program should use only about 700KB (no more than 750KB definetly!).
So pls help me smb. Now i try to explain my problem.
The only memory i use, i define out of main scope and i dont use any dynamic allocations. So, the definition looks like:

unsigned int length[MAXIMUMSTACKS];
unsigned int maxlength[MAXIMUMSTACKS];
unsigned int base[MAXIMUMSTACKS];
unsigned int stackPtr[MAXIMUMSTACKS];
unsigned char opbuf[OPSIZE * MAXOP];
unsigned int stack[MAXOP / 2];

where MAXIMUMSTACKS = 1000, OPSIZE = 5, MAXOP = 100000.

So, let's count all memory we may use: 4*1000 + 4*1000 + 4*1000 + 4*1000 + 500000 + 4*50000 = 16*1000 + 500000 + 200000 = 716000 bytes! I is about 700KB to be honest.
So, i dont inderstand, why my program get Memory Limit Error and use (as Timus says) 900KB(!). Pls, help me to fix it. Tell me what i dont understand. I give you the code of programm below.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MASK(k) ((1 << k) - 1)
#define OPSIZE 5
#define POPCODE 1000000001
#define MAXIMUMSTACKS 1000
#define MAXOP 100000

unsigned int N;
unsigned int length[MAXIMUMSTACKS];
unsigned int maxlength[MAXIMUMSTACKS];
unsigned int base[MAXIMUMSTACKS];
unsigned int stackPtr[MAXIMUMSTACKS];
unsigned char opbuf[OPSIZE * MAXOP];
unsigned int stack[MAXOP / 2];
char op[5];

unsigned short stnum;
unsigned int value;
unsigned int indx;


int main(int argc, char *argv[]) {

//    freopen("input.txt", "r", stdin);

    // init
    scanf("%u", &N);
    memset(opbuf, 0, N * OPSIZE);
    memset(length, 0, MAXIMUMSTACKS * sizeof(unsigned short));
    memset(maxlength, 0, MAXIMUMSTACKS * sizeof(unsigned short));

    // fill opbuf
    for (unsigned int i = 0; i < N; ++i) {

        scanf("%s%hu", op, &stnum);
        --stnum;

        indx = OPSIZE * i;

        opbuf[indx] = *((unsigned char*)&stnum);
        opbuf[indx + 1] = *((unsigned char*)&stnum + 1) & MASK(2);

        if (op[1] == 'U') {
            scanf("%u", &value);

            value = (value << 2);
            for (unsigned int j = 0; j < 4; ++j)
                opbuf[indx + 1 + j] += *((unsigned char*)&value + j);

            ++length[stnum];
            if (length[stnum] > maxlength[stnum]) {
                maxlength[stnum] = length[stnum];

                if (maxlength[stnum] > MAXOP / 2)
                    maxlength[stnum] = MAXOP / 2;
            }

        } else {
            value = (POPCODE << 2);
            for (unsigned int j = 0; j < 4; ++j)
                opbuf[indx + 1 + j] += *((unsigned char*)&value + j);

            --length[stnum];
        }
    }

    // create big memory block for stacks
    unsigned int prevLength = 0;
    unsigned int prevBase = 0;
    for (unsigned int i = 0; i < MAXIMUMSTACKS; ++i) {
        if (maxlength[i] == 0)
            continue;

        base[i] = prevBase + prevLength;
        stackPtr[i] = base[i];
        prevBase = base[i];
        prevLength = maxlength[i];
    }

    // process through opbuf
    for (unsigned int i = 0; i < N; ++i) {
        stnum = 0;
        value = 0;
        indx = OPSIZE * i;

        stnum += opbuf[indx];
        stnum += ((opbuf[indx + 1] & MASK(2)) << 8);

        for (unsigned int j = 0; j < 4; ++j)
            *((unsigned char*)&value + j) = opbuf[indx + 1 + j];

        value = ((value >> 2) & 0x3fffffff);

        if (value == POPCODE) {

            if (stackPtr[stnum] == base[stnum]) {
                stackPtr[stnum] = base[stnum] + maxlength[stnum] - 1;
            } else {
                stackPtr[stnum]--;
            }

            printf("%u\n", stack[stackPtr[stnum]]);
        } else {
            stack[stackPtr[stnum]] = value;

            if (stackPtr[stnum] == base[stnum] + maxlength[stnum] - 1)
                stackPtr[stnum] = base[stnum];
            else
                stackPtr[stnum]++;
        }
    }

    return 0;
}

Edited by author 20.08.2015 16:44
Re: Memory Limit. Dont know why. Pls help me to understand where i am wrong.
Posted by Manciu Ion 9 Feb 2017 19:28
source program only uses about 300KB + 700 = MLE. So you should use about 520000 Byte = 500 KB .My advice is to use a chunk of memory that we split into pieces (for example size 8) in the first part where you keep information about previous segment of the current stack and keep the information in the stack remaining 7.Be excused my english, if you do not clear reply and will present in more detail.
Re: Memory Limit. Dont know why. Pls help me to understand where i am wrong.
Posted by ToadMonster 10 Feb 2017 14:56
Allocated big buffers:
commands - 5*MAXOP = 500K
stack - 4*MAXOP/2 = 250K
Total - 750K buffers only

As empty C++ program takes about 100K you have MLE

If you wont analyze save commands
stack - 4*MAXOP = 500K (all pushes) + some chunks info

How your program will work if input sequence is something like
33K * "PUSH 1 100" // less then MAX_OP/2
33K * "PUSH 2 100" // less then MAX_OP/2
33K * "PUSH 3 100" // less then MAX_OP/2
POP 1
POP 2
POP 3

Your program should allocate 3 stacks with total 99K size in the 50K array.