bgbgbg's blog

4C — Time limit exceeded
By bgbgbg, history, 7 weeks ago, In English

Hi all,

I tried to solve problem 4C Registration System. My submission (in Java) is 99974226.

Test 7 fails because the time limit is exceeded.However, I have no clue as to how I can optimize my solution. Could you please help me out?

Any help is greatly appreciated!

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

Comments Comments (4)
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Use a dictionary (map in c++)

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem with using the list method .contains() is that it has a time complexity of O(n). You will be better suited if you used a HashMap or a HashSet instead whose containsKey() or contains() method respectively has a time complexity of O(1). One more thing to note is that string concatenation has a time complexity of O(n+m) in java , although I don't this particular issue impacts this problem much.

For more help look at my solution : https://codeforces.com/contest/4/submission/91741139

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

[user:https://codeforces.com/profile/Atoev__Urvatullo]

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks so much for your help everyone.

I am new to algorithms and Big O. It is not always easy for beginners to correctly evaluate the time complexity of a given solution.

Using a Map was the key to solving this excercise. I was able to simplify the implementation to a great extent.

→ Reply