ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1196. Экзамен по истории

Java Tips
Послано Dan Manastireanu 28 мар 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
Послано ISDemidoff 14 авг 2011 14:00
I had 0.515 with StringTokenizer ans HashSet :)
Re: Java Tips
Послано Eugene_Aslanov[SSAU_627] 24 июн 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
Послано ElPsyCongroo 28 май 2014 00:40
0.375 BufferredReader + HashSet.

Thanks for the tip thread starter :).

Thanks,
ElPsyCongroo.
Re: Java Tips
Послано KuptsovKonstantin 15 окт 2014 22:05
0.296 bufferedreader + hashset