PROGRAMMAR's blog

praying for help in java
By PROGRAMMAR, history, 8 years ago, In English

I'm very tired with this "lightoj.com" problem. I tried to find java code from internet but couldn't find. since this judge requires "registration"; i share the problem here followed by my code. I know the logic. even i did it using c++ and got ac. I'm knew in JAVA. it will be helpfull if you say why my code facing "MLE"

1009 — Back to Underworld(problem name) Time Limit: 4 second(s) Memory Limit: 32 MB

The Vampires and Lykans are fighting each other to death. The war has become so fierce that, none knows who will win. The humans want to know who will survive finally. But humans are afraid of going to the battlefield.

So, they made a plan. They collected the information from the newspapers of Vampires and Lykans. They found the information about all the dual fights. Dual fight means a fight between a Lykan and a Vampire. They know the name of the dual fighters, but don't know which one of them is a Vampire or a Lykan.

So, the humans listed all the rivals. They want to find the maximum possible number of Vampires or Lykans.

Input Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case contains an integer n (1 ≤ n ≤ 10^5), denoting the number of dual fights. Each of the next n lines will contain two different integers u v (1 ≤ u, v ≤ 20000) denoting there was a fight between u and v. No rival will be reported more than once.

Output For each case, print the case number and the maximum possible members of any race.

Sample Input Output for Sample Input

2

2

1 2

2 3

3

1 2

2 3

4 2

Case 1: 2

Case 2: 3

https://ideone.com/so3oF3

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

Comments Comments (7)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hello , Are you sure that 1 <= n <= 105 ???

if that is true, that you can compress those u,v values from [1,20000] to [1,105] ,,,

I hope this helps ...

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Probably bounds are too tight for java, because JVM needs some memory by itself, so it may be too much, especially with your 20000 ints and 20000 ArrayList. Many online judges have problems that are simply not solvable in java. Also, try not to use Scanner, it is very slow; instead use BufferedReader and PrintWriter.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    my c++ code(same style) takes 4500 kb(4 MB). on the other hand 30MB is not enough for java? sqrtdecompton suggested me to do using BFS. but I wanted it using DFS. I don't want to believe 30 MB is not enough while 4 MB for c++. As I'm new in java so i don't know in which part my code should be optimized. is their any fault in "memory clearance"? my c++ code http://ideone.com/eRdcIP

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Then it is not possible to solve in java.

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I'm not able to submit my solution on lightoj, because I haven't received the confirmation email from them yet :( But I've got AC with this code on bnuoj (your code get MLE there also). There are cases where dfs produces a wrong answer in this problem.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        moreover, have you noticed that memory limit is 32768 kb but your ac code uses about 65000 kb and judge doesn't show MLE. but why? do you know the reason?

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Real memory limit is about 1e5kb (maybe it takes into account jvm?). You can do several improvements:

          1. Scanner — Its threshold for buffer flushing is to large for constraints of this problem and causes MLE.
          2. BitSet — 1 bit to mark element as used instead of 8 (boolean).
          3. System.gc() — call garbage collection manually before each test. If call too frequently it'll cause TLE.

          It was done just for fun and I'll never use Java in such problem. Point 2 and 3 increase time and are possible here because of large time limit (4s).

          → Reply