ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1196. History Exam

Java Tips
Posted by Dan Manastireanu 28 Mar 2010 17:38
Here are some tips for passing with Java code.

      Read      |    Data/Search   | Result
Scanner         |      TreeSet     | TLE on 8
Scanner         |      HashSet     | TLE on 8
Scanner         |a[n]&binary search| TLE on 5 ???
StringTokenizer |      TreeSet     | 0.765
StringTokenizer |      HashSet     | 0.546
StringTokenizer |a[n]&binary search| TLE on 5 ???

Conclusions:
Use StringTokenizer(Scanner is very slow) and HashSet.
I think HashSet outperforms TreeSet for two reasons:
1. data doesn't cause too many collisions
2. inserting in a tree is still O(log(n)) even for sorted data,while for HashSet it is O(1)

Question: I have no clue why the simple binary search I wrote took so long ...
It should have outperformed at least the treeset(no insertion costs; search is the same O(log(n)) but with no overhead from method calls...)
Re: Java Tips
Posted by ISDemidoff 14 Aug 2011 14:00
I had 0.515 with StringTokenizer ans HashSet :)
Re: Java Tips
Posted by Eugene_Aslanov[SSAU_627] 24 Jun 2013 03:01
Also 0.515 with StreamTokinizer and HashSet, but 5 816 KB.
0.531 and 476 KB with StreamTokinizer and binarySearch.
Re: Java Tips
Posted by ElPsyCongroo 28 May 2014 00:40
0.375 BufferredReader + HashSet.

Thanks for the tip thread starter :).

Thanks,
ElPsyCongroo.
Re: Java Tips
Posted by KuptsovKonstantin 15 Oct 2014 22:05
0.296 bufferedreader + hashset