ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1713. Key Substrings

Time limit exceeded
Posted by Mervin 25 Oct 2009 00:16
I find many solutions are less than 1 second. Could any one give me some hint to improve efficiency. Thanks in advance.
Re: Time limit exceeded
Posted by Igor9669(Tashkent IAC) 25 Oct 2009 00:21
I think that solutions which runs less than 1 sec. use hash table!
Re: Time limit exceeded
Posted by Mervin 25 Oct 2009 00:28
How to construct Hash Table. If use substring of each command as the key, construction may consume too much time.
Re: Time limit exceeded
Posted by Igor9669(Tashkent IAC) 25 Oct 2009 00:31
to construct all substrings we need O(N*MaxLen^2) it is enough here!
I solved it without hash table,that is why my solution works more than 1 sec.

Edited by author 25.10.2009 00:35
Re: Time limit exceeded
Posted by Mervin 25 Oct 2009 00:38
What is mean of "MaxLen". Does it mean max command string length?
Re: Time limit exceeded
Posted by Igor9669(Tashkent IAC) 25 Oct 2009 00:40
Yes! it is 100!
Re: Time limit exceeded
Posted by Mervin 25 Oct 2009 00:49
oh
If more than one command string have same substring. Do you consider it as same key value.
Re: Time limit exceeded
Posted by Igor9669(Tashkent IAC) 25 Oct 2009 00:51
Read statement! it is clear to understand it yourself!
Re: Time limit exceeded
Posted by Mervin 25 Oct 2009 00:58
Thanks.
Actually, I could not find clear connection between Hash Table and this problem.
Re: Time limit exceeded
Posted by Igor9669(Tashkent IAC) 25 Oct 2009 01:03
Look at previous post, there is another solution, without hash table!
Re: Time limit exceeded
Posted by Mervin 25 Oct 2009 01:04
I would feel more appreciated if you could offer me some explanation or Reference Material.
Thanks
Re: Time limit exceeded
Posted by Igor9669(Tashkent IAC) 25 Oct 2009 01:07
Re: Time limit exceeded
Posted by Mervin 25 Oct 2009 01:08
I am a new beginner on this website.
Could I get algorithm rationale of solution posted by other programmers? if yes, How?
How aboult test data. Where can I get?
Re: Time limit exceeded
Posted by Igor9669(Tashkent IAC) 25 Oct 2009 01:12
You could look at Statistics of each problem!
You couldn't get test data. You could create your own, and somebody will answer on it!
Re: Time limit exceeded
Posted by Mervin 25 Oct 2009 01:14
email: glbian@yahoo.com.cn
MSN: glbian@live.com