ruchir28's blog

By ruchir28, history, 6 weeks ago, In English

I am using an approach that will work within the time limit and even the same approach is accepted in C++ but gives TLE in java I have also used Fast IO but still TLE. Can anyone help me with this. Problem Link : https://codeforces.com/contest/986/problem/A Submission : https://codeforces.com/contest/986/submission/132535284

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ruchir28 (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

even the same approach is accepted in C++

Did you try implementing your approach in C++ then?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, But I have seen a similar implementation

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      There are 2 options now:

      1. Someone optimizes your code for you.
      2. You generate test cases and profile your code.

      Option 1 is unlikely given how messy the code is. Moreover, there is a possibility that you might have analyzed the time complexity of your code wrongly (then it would be a waste of time for others to try to study your code).

      I recommend that you generate some large test cases and profile your code to see where the bottleneck in your code is.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You're using linked list and accessing random indices, therefore it becomes n^2 and is way too slow

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey I am using LinkedList as a queue where the operations would be just removing the first element and adding to last both are O(1)

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are using LinkedList for no reason instead of array/ArrayList for the goods variable.

      Didn't look to carefully at your code, but the complexity is probably fine. To get AC you need to make sure the constant is low as well.

      I got TLE in C++ because I used a multiset in the last loop instead of sorting. Also changing dist[n][k] to dist[k][n] almost halved the execution time (I assume here the cache misses really hurt the performance).

      So look at other java solutions that get AC and keep tweaking your solution until you get AC (my guess is that you have to ditch the LinkedList altogether).

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        the complexity is wrong

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks,I have corrected the LinkedList part,Also when I saw some submissions in java for this problem I noticed that they have used a jagged array to represent their graph instead of List<List> so I did that and it got accepted. Maybe that resize operation in Arraylist might have consumed time(for larger inputs) or something else.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Re-read the original comment and then read this

                  for(int i=0;i<n;i++){
                      list.add(new ArrayList<>());
                      int good = s.nextInt();
                      good--;
                      goods.get(good).add(i);
                  }
      
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank for pointing out I have corrected that.