noobCoderUltraProMax's blog

Help Needed In Recent Contest's Problem C.
By noobCoderUltraProMax, history, 3 years ago, In English

My Code link:https://codeforces.net/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?

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

Comments Comments (4)
| Write comment?
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

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

    https://codeforces.net/contest/1678/submission/156346740 I think above solution is o(n2logn) can u help me why its TLE?

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

      [Deleted] I was wrong!

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

      The constraints are actually made to prevent n^2 * log(n) solutions from passing. I believe the author didn't expect some of the submissions to make it through or rather at least the ones with high constant factor and therefore made a quick edit before releasing the final editorial. (It's just a possibility don't take it for real)

      at n = 5000 attempting a n^2 * log sol is pretty risky, therefore you make use of really well optimized code for a data structure (like iterative segment trees and I/O optimizations which some people do, or a Fenwick which is more lightweight, etc.)

      or just be cautious and don't go for the log(n) solution :) that's what struck me initially too (so I spent some time thinking and considered holding back on it till I ran out of time)

      → Reply