damon2598's blog

Why is O(n) solution exceeding time limit?
By damon2598, history, 6 years ago, In English

in the educational Codeforces Round 53 , problem B (1073B) my solution gives TLE ,but I don't think it should. My submission is : http://codeforces.com/contest/1073/submission/44858358 can someone suggest the bugs in my code ,if any ?

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Try adding this line in the beginning of the main function: ios_base::sync_with_stdio(false);

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

    Yes , it worked . Thanks for the reminder . Usually I use fast io but on codeforces ,it didn't seem necessary . Still, I am astonished how slow cin ,cout actually is. Thank you again.

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

One way to speed up your program and get accepted even without using ios_base::sync_with_stdio(false); is to just do all input reading in one go.

With ios_base::sync_with_stdio(false); 748 ms

Without ios_base::sync_with_stdio(false); and reading all input in one go: 514 ms

With ios_base::sync_with_stdio(false); and reading all input in one go: 124 ms

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

    I didnt realize it would be this slow. Thanks a lot .

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

first of all your code is not in O(n) but in expected O(n) wich may or maybe not be a huge difference since there could be hash collision test... (but i dont know)

and second why using a hashmap at all when you know that the input is a permutation? you can just use an array?

and another issue is reading the input just partly... this seems to be quite slow: https://codeforces.com/contest/1073/submission/44907426

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

    I even used an array instead of hashmap. Still ,I was getting tle. Now I know where I slowed things down, I actually used a global array(size 2e5+5) for hashing . The memset must have slowed things down . Thanks for the vector illustration .

    → Reply