CP_Sucks's blog

By CP_Sucks, history, 3 months ago, In English

Hi i can someone tell how can i overcome TLE in this problem using java

Problem : https://cses.fi/problemset/task/1164/

My Solution : https://hastebin.com/ilexoqukuw.csharp

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

»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

If you are sure you have the right time complexity, it's most likely because you are using Java in CSES.

If you really want AC, use C++, otherwise don't worry about it.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    I've already aced using c++ before but using same complexity wanted to ac in Java too (to shift to java completely).

»
3 months ago, # |
  Vote: I like it +42 Vote: I do not like it

Why are you submitting solutions, I thought CP_Sucks?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -38 Vote: I do not like it

    Coz your mom told me to and I love your mom so much

»
3 months ago, # |
Rev. 4   Vote: I like it +14 Vote: I do not like it

Reading the comments of C++ fanboys makes me want to laugh.

Jokes aside. Before I give you the actual answer, there are a few things that you need to take note of:

  1. You did not close your reader. You need to learn to release system resources even if sometimes the system does it automatically for you.

  2. You used a HashSet Iterator as though you expected it to always return you the minimum element in the Set. That's not correct. According to the Javadocs of HashSet, its iterator returns elements in no particular order. You are probably looking for a TreeSet.

Okay. Here are the updates that I did to your code that earned AC:

  1. The tm property of your Event class can be set as int instead of long because you are storing int in that property anyway. This gives a slight (but not significant) speedup.

  2. After studying the way you used HashSet, I realised that you want a data structure to do 3 operations: add, extract smallest element and remove smallest element. This can be done using a Priority Queue, which has better empirical performance compared to a TreeSet (which can also do the same things). This yielded considerable speedup.

  3. The most significant speedup was to improve the IO performance of your code. I replaced your FastReader class with the fastest implementation that I could find on GeeksForGeeks. This was the final optimization that yielded the AC.

On a side note, you don't seem to know Java well. Please learn to write it properly. Don't try to glue pieces of code that you peeled off the net into "something that simply works". This nonsense is typical of high school kids that don't know what they are doing. Learn your programming language well and it will carry you far beyond the world of CP.

AC Java Code
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Nobody sees the C++ fanboys you're referring to, did you injure yourself while making that stretch?

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

      LTDT actually got more flexible, because he's just orz like that

  • »
    »
    3 months ago, # ^ |
    Rev. 4   Vote: I like it -40 Vote: I do not like it

    Ok apart from useless pointless insult basically faster io passes it. Second you don't have to use treeset coz roomorder of room assigned doesn't matter (wish u were not dumb enough to see that) and hashset runs faster than priority queue. Also what made your dumb mind thing I copied something from internet , only fast io is copied from net. So simple reply could have been use faster no (XD). Thanks anyway

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Second you don't have to use treeset coz roomorder of room assigned doesn't matter (wish u were not dumb enough to see that) and hashset runs faster than priority queue.

      LOL. That makes you the fool. Because, in that case, you don't need a HashSet. What you want is a data structure that can return elements in any order (while ensuring uniqueness). There are much better ways to do that without the overhead of hashing. Seeing your arrogant mindset, I shall withhold the answer and leave you to think about it.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How will you add remove and query if something exists in particular set in logn without hashset ? Oh I'm being arrogant ? Read your answer again. And do whatever fuck you want like anyone in world cares XD