Getting TLE on 433B problem

Блог пользователя dev_il

Автор dev_il, 9 лет назад, По-английски

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.

tle, partial sum, sorting

dev_il
9 лет назад
13

Комментарии (12)

Показать архивные | Написать комментарий?

ayush_awasthi

9 лет назад, # |

← Rev. 2 →

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.

→ Ответить

dev_il

9 лет назад, # ^ |

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

→ Ответить

Guliash

9 лет назад, # |

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

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

→ Ответить

dev_il

9 лет назад, # ^ |

And so how to sort arrays?

→ Ответить

Guliash

9 лет назад, # ^ |

Shuffle before sorting or use Objects.

→ Ответить

dev_il

9 лет назад, # ^ |

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

→ Ответить

Guliash

9 лет назад, # ^ |

There is a testcase where the sort is O(n²). If you do not shuffle then of course you are going to get O(n²) perfomance. But if you shuffle the probability that your array is the same as the testcase is very very small.

→ Ответить