farmersrice's blog

Unexpected TLE?
By farmersrice, history, 8 years ago, In English

So, I was recently trying to solve this problem: http://codeforces.net/contest/727/problem/F submission at http://codeforces.net/contest/727/submission/21647053

My algorithm should be O(n2 * log1012 + mlogn). First, I determine the lowest possible prefix sum for a certain amount of removed problems. This is done with a binary search and greedy. I binary search on the condition "If we can remove a certain number of problems, can the minimum prefix sum be greater than or equal to the target?" (This is always of form TTTT...FFF). To find that condition I greedily add numbers to a running sum, and if the running sum is less than or equal to target, I remove the smallest value that occurs before or at the current index. Then, I read all m queries and binary search for the correct answer on those.

Can anyone help me understand why I'm getting TLE? Thanks.

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

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

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

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

First, your complexity analysis is slightly incorrect: it's , because you have a priority queue inside your binary search.

And that's precisely where your TLE comes from. Java standard library collections are usually quite slow, so you would have had better luck using your own heap implementation: 21686518

(If you don't want to rewrite the whole standard library, perhaps you might want to switch to C++? :P)

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

    No way. It's never been a problem of Java or C++. You can calculate the minimum initial mood required so that it will never drop to negative when reading from problem i to the end using dp.

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

    Ah, I understand now. Thanks for the help! (By the way, if there's any IDE that has auto-import in C++, could you please tell me?)

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

      Well, what basically all C++ coders do is just include the whole standard library with the line #include <bits/stdc++.h>. The only possible downside to that would be a higher probability of some standard function having name clashes with the variables in your program, but if you're really worried about that you can leave them all in the std namespace.

      To actually answer the question, I think CLion has something of the sort, but that IDE seems to be free only for students.

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

    One could simulate a decently-performing priority queue in Java using TreeSet. A way to comply with the definition of totally ordered set (a set is not exactly a priority queue) is to implement some class with values <key, index> and an appropriate comparison method.

    → Reply