ulna's blog

By ulna, history, 4 years ago, In English

Lately I have been solving this problem, lucky array. I implmented a O(m log n + 30 * n log n) where n, m <= 1e5(my submission). My solution got tle in some test cases. And I have found that the solution in the editorial is the same as mine. Then I tried using bottom-up segment tree instead of top-down but it didn't aid the issue.

I think the main reason that causes the tle is because the execution time is multiplied by 2. And that is too much. I had once encounter the same issue but with different tasks, I managed to optimized well and passed. But I couldn't this time. I think that maybe the time limit should be increased if the execution time have to be multiplied by 2 ? Or it would become a constant optimizing problem.

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

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

The reason for multiplied execution time is new testing servers, more powerful and fast

»
4 years ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

Have you tried to copy/paste a solution from other contestant?, I mean, you don't have to see the solution just copy-paste and submit, if that solution get accepted, then there is a solution fo the problem, could be with some constant optimizations, or maybe just another algorithm.

  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Of course I know there is a way to solve the problem. The main point is that the execution time calculated for old problems is not very fair. E.g. I just copied Arios's solution which pass in 3380 ms. Then I submit it again and it receive tle.

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

      Ok, I agree with you, Has to be guaranteed that at least every solution that got accepted in a contest have to get accepted with the new constraints.

      I think in that case, will be fair.

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

I tried to submit the same code with GNU C++14, in the hope, that the more advanced compiler will do some magic, but that also TLE'd...