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

Автор noobCoderUltraProMax, история, 5 лет назад, По-английски

My Code link:https://codeforces.me/contest/1678/submission/156355337

My Logic: Store all Pairs [Ai,Aj] where Ai>Aj in a 2D Vector and similarly do for Ai<Aj. Now Make 4 length arrays using these two arrays as they have required Pa < Pc and Pb>Pd pairs. If they meet the given condition check if position of elements of subsequence in original array is sorted or not using map, if sorted increment the answer.

Problem: It TLE's.

Thinking: I tired to think of optimization but unable to come up with. So can anyone help?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +18 Проголосовать: не нравится

Your code runs in O(n^4). The size of each of the two arrays you create is O(n^2), and you iterate through all pairs.

A computer can do roughly 10^8 operations per second, but you're asking it to do roughly 5000^4, which is about 10^14, so this would take about a million seconds to finish on the largest allowed input.

You can read the solution in the editorial here.