dev_il's blog

Getting TLE on 433B problem
By dev_il, 10 years ago, In English

Problem: 433B - Kuriyama Mirai's Stones

This is my solution: 11326002

I use partial sums for initial array and then for sorted. Don't understand where can be a bottleneck.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
10 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Your approach and implementation of the problem are correct but you seem to use scanner class for taking input which is slow (though i am not a regular JAVA user but that is the only fault i can find in your code) . Try to use faster I/O methods. I think it will get accepted after that because your approach and implementation are correct. For faster I/O you can refer to codes of top rated coders who use JAVA as their language.

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

    Oh, thank you very much. I think you are right. I even forgot about FastScanner.

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

The bottleneck is quite well-known. Should not use Arrays.sort for primitive types.

http://mirror.codeforces.com/contest/433/submission/11329247

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

    And so how to sort arrays?

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

      Shuffle before sorting or use Objects.

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

        How shuffling can help in this case? Arrays.sort function never wraps primitive type in Integer/Long objects.

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

    I will answer here.

    Because ArrayList is a list of Objects. You can't create ArrayList< int >.

    → Reply