islam-al-aarag's blog

By islam-al-aarag, 12 years ago, In English

Can someone tell me how this code exceeds 256MB? where n is at most 5k.

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.LinkedList;

public class G {
    public static void main(String[] args) throws NumberFormatException,
            IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int n = Integer.parseInt(in.readLine());
        Point[] E = new Point[n];
        HashMap<String, Integer> H = new HashMap<String, Integer>();
        String[] N = new String[n * 2];
        int index = 0;
        for (int i = 0; i < n; i++) {
            String[] S = in.readLine().split(" ");
            if (!H.containsKey(S[0]))
                H.put(S[0], index++);
            if (!H.containsKey(S[1]))
                H.put(S[1], index++);
            int x = H.get(S[0]);
            N[x] = S[0];
            int y = H.get(S[1]);
            N[y] = S[1];
            E[i] = new Point(x, y);
        }
        boolean[][] F = new boolean[index][index];
        for (int i = 0; i < n; i++)
            F[E[i].x][E[i].y] = F[E[i].y][E[i].x] = true;
        short[][] C = new short[index][index];
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int o1 = -1, o2 = -1;
                if (E[i].x == E[j].x) {
                    o1 = E[i].y;
                    o2 = E[j].y;
                } else if (E[i].x == E[j].y) {
                    o1 = E[i].y;
                    o2 = E[j].x;
                } else if (E[i].y == E[j].x) {
                    o1 = E[i].x;
                    o2 = E[j].y;
                } else if (E[i].y == E[j].y) {
                    o1 = E[i].x;
                    o2 = E[j].x;
                }
                if (o1 == -1)
                    continue;
                if (!F[o1][o2]) {
                    C[o1][o2]++;
                    C[o2][o1]++;
                }
            }
        out.println(index);
        for (int i = 0; i < index; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = 0; j < index; j++)
                max = Math.max(max, C[i][j]);
            int cnt = 0;
            for (int j = 0; j < index; j++)
                if (C[i][j] == max && !F[i][j] && i != j)
                    cnt++;
            out.println(N[i] + " " + cnt);
        }
        out.flush();
        out.close();
    }
}
  • Vote: I like it
  • -6
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I would be really glad if one of those -ve vote owners actually commented and helped me.

»
12 years ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

short[][] C = new short[index][index]; boolean[][] F = new boolean[index][index];

index can be at most 10k? So this 2 arrays can use about 290 Mb memory.

»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Your variable index can be at most 10^4. So your F and C 2D arrays need approximately 100MB and 200MB (100MB+200MB>256MB) memory space respectively.