Problem in Memory Limit Exceeded during mock ICPC-2020

Hello Everyone, today I tried to solve the problem Subsegment xor sum during the mock ICPC-2020 contest. But to my surprise, my java code didn’t pass and showed MLE. However the same code got accepted when was submitted in cpp by translating my java code. I also faced this issue many times during practicing in codedrills.

However, when i removed my fast-IO of my java, it showed TLE verdict on the same-testset, Test-Set 2. I am pretty sure ther might be a problem on the Codedrills java-compiler. Anybody who solved the problem using JAVA, please share your views or your accepted code. I don’t know why is this issue arising as my fast-IO code gets passed on different competitive websites.

@admins pls look into this matter as we might end up getting penalty due to this problem or issue. My codes always get MLE, in Codedrills however the same-logic cpp codes get passed.

I am hereby attaching my codes and verdicts received from Codedrills.

JAVA Code

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

class Main {
    static long mod = (long) 1e9+7;
    public static void main(String[] args) throws IOException {
        Soumit sc = new Soumit();

        int t = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        while (t-->0){
            int n = sc.nextInt();
            long[] arr = sc.nextLongArray(n);

            long[][] ans = new long[31][n];
            long[][] dp = new long[31][n];
            for(int i=0;i<n;i++){
                for(int j=0;j<ans.length;j++){
                    ans[j][i] = (arr[i]&(1L<<j))==0?0:1;
                }
            }

            /*for(long[] i: ans){
                System.out.println(Arrays.toString(i));
            }
            System.out.println();*/

            for(int i=0;i<dp.length;i++){
                long last = 0;
                for(int j=0;j<n;j++){
                    if(ans[i][j]==1){
                        last = j-last+1;
                    }
                    dp[i][j] = last;
                }

                //System.out.println(Arrays.toString(dp[i]));
                for(int j=1;j<n;j++){
                    dp[i][j] = (dp[i][j]+dp[i][j-1])%mod;
                }
            }

            /*System.out.println();
            for(long[] i: dp){
                System.out.println(Arrays.toString(i));
            }*/

            long sum = 0;
            for(int i=0;i<dp.length;i++){
                sum = (sum + (dp[i][n-1] * ((1L<<i)%mod)) %mod) %mod;
            }

            sb.append(sum).append("\n");
        }

        System.out.println(sb);

        sc.close();
    }

    static class Soumit {
        final private int BUFFER_SIZE = 1 << 18;
        final private DataInputStream din;
        final private byte[] buffer;
        private PrintWriter pw;
        private int bufferPointer, bytesRead;
        StringTokenizer st;

        public Soumit() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Soumit(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public void streamOutput(String file) throws IOException {
            FileWriter fw = new FileWriter(file);
            BufferedWriter bw = new BufferedWriter(fw);
            pw = new PrintWriter(bw);
        }

        public void println(String a) {
            pw.println(a);
        }

        public void print(String a) {
            pw.print(a);
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[3000064]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public void sort(int[] arr) {
            ArrayList<Integer> arlist = new ArrayList<>();
            for (int i : arr)
                arlist.add(i);

            Collections.sort(arlist);
            for (int i = 0; i < arr.length; i++)
                arr[i] = arlist.get(i);
        }

        public void sort(long[] arr) {
            ArrayList<Long> arlist = new ArrayList<>();
            for (long i : arr)
                arlist.add(i);

            Collections.sort(arlist);
            for (int i = 0; i < arr.length; i++)
                arr[i] = arlist.get(i);
        }

        public int[] nextIntArray(int n) throws IOException {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }

            return arr;
        }

        public long[] nextLongArray(int n) throws IOException {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextLong();
            }

            return arr;
        }

        public double[] nextDoubleArray(int n) throws IOException {
            double[] arr = new double[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextDouble();
            }

            return arr;
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            /*if (din == null)
                return;*/
            if (din != null) din.close();
            if (pw != null) pw.close();
        }
    }
}

CPP code

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define s second
#define f first
#define vi vector<int>
#define pii pair<int,int>
#define vii vector<pii>
#define vl vector<ll>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define mii unordered_map<int,int>
#define mod 1000000007
#define nextline cout<<"\n"
int gcd(int a,int b)
{
    if(b == 0)
        return a;
    return gcd(b , a % b);
}
int lcm (int a,int b)
{
    return (a*b)/(gcd(a,b));
}
bool isPowerOfTwo(ll n)
{
   if (n == 0) 
        return 0; 
    while (n != 1) 
    { 
        if (n%2 != 0) 
            return 0; 
        n = n/2; 
    } 
    return 1;
}
ll power(ll x, ll n, ll p) {
    ll res = 1;
    if(n == 0) return 1;
    if(n == 1) return x%p;
    if(n%2 == 1) res = x%p;
    ll temp = power(x,n/2,p);
    return res*((temp*temp)%p)%p;
}
bool compare(pair<ll,ll> a,pair<ll,ll> b)
{
    if(a.f != b.f)
        return a.f<b.f;
    else return (a.s<b.s);
}

void solve(){
    ll b,c,n;
    cin>>n;
    ll a[n];
    for (int i = 0; i < n; ++i)
    {
        cin>>a[i];
    }
    ll ans[31][n];
    ll dp[31][n];
    for (int i = 0; i < n; ++i)
    {
        for(int j = 0; j < 31; j++)
        {
            ans[j][i] = (a[i]&(1L<<j))==0?0:1;
        }
    }
    for(int i=0;i<31;i++)
    {
                ll last = 0;
                for(int j=0;j<n;j++)
                {
                    if(ans[i][j]==1)
                    {
                        last = j-last+1;
                    }
                    dp[i][j] = last;
                }
                for(int j=1;j<n;j++)
                {
                    dp[i][j] = (dp[i][j]+dp[i][j-1])%mod;
                }
            }
                ll sum = 0;
            for(int i=0;i<31;i++)
            {
                sum = (sum + (dp[i][n-1] * ((1L<<i)%mod)) %mod) %mod;
            }
            cout<<sum<<"\n";
}

int main()
{
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int t;
    cin>>t;
    //t = 1;
    while(t--)
    {
        solve();
    }
    return 0;
}

Please help me. Thanks in advance

1 Like

Thanks for the detailed report @Soumit_Saha - it was really easy debugging thanks to all the code and links you provided :slight_smile:

It seems Java generally takes much more memory than the equivalent C++ program. Here the memory limit was 256 MB but the solution took about 500 MB. I have now increased the memory limit to 512 MB for the problem so your solution passes. We will keep Java in mind when deciding memory limit for all the problems so that it doesn’t MLE. We are also considering if we should keep a memory addition/multiplier for Java like we do for time limit. If you face this issue in any other problem while practicing, just share the solution link (can be accessed from submission history tab) with us and we will use those as a data point when selecting memory limit and multipliers.

2 Likes

Starting now, an extra 256 MB will be added to the memory limit for Java and Kotlin submissions. More details here.

2 Likes