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

Обсуждение задачи 1028. Звёзды

Java TL
Послано [SPbSPU]crazylammer 6 авг 2007 23:34
To admins: Don't you think that it would be correct to increase Java-TL for this task to, e.g, 0.5 seconds (if it is possible)?
When I tried to submit this problem first time, I used prewritten RB-Tree code, using generics and classes for every node. This class is not so slow, a bit faster that java.util.TreeSet. When I'd got TL9, I rewrote it, using only primitive types and arrays. But it became TL10. That code, rewritten letter-by-letter in pure C, became AC in 0.031...
Сertainly, another(simplier?) data structure can lead to Java-AC, but probably it is incorrect to force Java-writers to use non-asymptotical optimizations (especially Java is the official language of ACM competition).

Edited by author 06.08.2007 23:34

Edited by author 06.08.2007 23:37

Edited by author 07.08.2007 00:01
Re: Java TL
Послано Vladimir Yakovlev (USU) 7 авг 2007 03:54
Unfortunately, TL for this problem can't be increased. Bruteforce solution works very fast even with Java. You can try your sophisticated algorithms solving problem 1090. But this problem have to be solved using fastest algorithm in all senses
Re: Java TL
Послано Alias (Alexander Prudaev) 8 авг 2007 21:05
What do you use to read input?
maybe some optimizations in this direction can help
Re: Java TL
Послано Meni Packeou 21 ноя 2007 10:58
I think do not problem Java program.Problem I think  this he algortms.I working this 1028 solution at the Java but
came back TL time=0.296. You are use algortms quiksort or
binarysearch.
Re: Java TL
Послано Alex Tolstov 13 мар 2009 14:27
AC in Java 0.234sec using java.util.Scanner and fenwick's tree.

And AC in Java 0.125sec using java.io.StreamTokenizer instead of java.util.Scanner
Re: Java TL
Послано Fyodor Menshikov 13 мар 2009 22:43
Alex Tolstov писал(a) 13 марта 2009 14:27
AC in Java 0.234sec using java.util.Scanner and fenwick's tree.

And AC in Java 0.125sec using java.io.StreamTokenizer instead of java.util.Scanner

Because of Timus processor upgrade this autumn. :-) And what time of the simplest O(n^2) solution now? :-) Maybe less than 0.25...
Re: Java TL
Послано KALO 7 окт 2009 14:22
No, I use insertionsort and TL#9.