islam-al-aarag's blog

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

I was coding problem 384D - Вулканы after reading the editorial.
I keep getting wrong answer. I traced the code and tried all the small tests in the test cases but still can't find the bug.
The test case I fail in is large so I can't get a hold of it
Help is really appreciated. Here is my code:

[Edit]: I found the bug, thanks :)

Full text and comments »

  • Vote: I like it
  • -9
  • Vote: I do not like it

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

I've been debugging this for a while and I still can't tell why it exceeds the memory limit.
Can somebody help me?
Submission: 5723491

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

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

I was solving problem C from the last testing round 386C - Diverse Substrings
The idea I got was to handle substrings starting at different indices separately:
   1. You will do a precomputation next[i][26] telling you the next occurrence of each of the lower case letters from index i.
   2. You start at index i and each time you jump to the unseen character (using the precomputed array) with the least next occurrence    say k and all substrings starting at i and ending between the last jump and the current jump has diversity of the size of seen    characters so far.
The implementation was direct 5706503 and it was accepted.
I was playing around to optimize it when I thought I shouldn't loop on all characters and check what has been seen or not but instead maintain an actual set of the unseen characters so far and loop over them exclusively. The implementation was direct too 5706533.
To my surprise, this code timed out. I still can't explain why, it's supposed to be doing less loop iterations and hence less comparisons.
Any help would be appreciated.

Full text and comments »

  • Vote: I like it
  • -10
  • Vote: I do not like it

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

I expected a new year's eve round :(

Full text and comments »

  • Vote: I like it
  • +33
  • Vote: I do not like it

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();
    }
}

Full text and comments »

  • Vote: I like it
  • -6
  • Vote: I do not like it

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

I can't register unofficially for the next Div2 round. Is it not possible anymore?

Full text and comments »

  • Vote: I like it
  • +18
  • Vote: I do not like it

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

Is there a way to check all your old comments on posts?

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

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

Is wild card 2 rated???

Full text and comments »

  • Vote: I like it
  • -19
  • Vote: I do not like it

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

I can not view any of the submitted codes of any contestant. Is the system in safe mode or is it just a bug??

Full text and comments »

Tags bug
  • Vote: I like it
  • -4
  • Vote: I do not like it

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

How can I join today's round virtually? to see where I would come if I joined.

Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it

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

I found a bug concerning replying on comments. If you click reply more than once, you get more than one text area to write your comment. The more you click, the more areas you get.

Full text and comments »

  • Vote: I like it
  • +7
  • Vote: I do not like it

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

Announcements were not working correctly today, I didn't know my solution was hacked because I got an announcement with the word (undefined) so I just ignored it. Same for the public announcement, I saw it when I was asking a question.

Full text and comments »

  • Vote: I like it
  • +12
  • Vote: I do not like it

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

What does Judgement Failed mean?

I got it 4 times in a row.

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it