Пасхалки Тимуса

13 лет назад, # ^ |

← Rev. 2 →

-14

Или зелёную спираль.

Upd. Мне почему-то подумалось про оболочку прямоугольника. Видимо имелся в виду прямоугольник с внутренностями. :-)

→ Ответить

blazerer

13 лет назад, # ^ |

+85

по-моему это круто :)
реализация :)

→ Ответить

JKeeJ1e30

13 лет назад, # ^ |

А зачем была решена 1393? Точка, как бы?

→ Ответить

Ferlon

13 лет назад, # ^ |

Имеется подозрение, что это, например, будущий восклицательный знак или картинка.
Но что больше всего хотелось бы узнать, так это реакцию Иры =)

→ Ответить

13 лет назад, # ^ |

А может Александр увидел интересную задачу, и не удержался...

→ Ответить

Milanin

13 лет назад, # ^ |

Прошу прощения за задержку. Хоть это и не тема поста, но, поскольку вопросы адресованы лично мне, то отвечу.

Задача 1393 - это просто неприятная случайность. Никаких скрытых смыслов.

Реакцию Иры я, к сожалению, не знаю. Надеюсь, что понравилось.

→ Ответить

dalex

13 лет назад, # |

А что, если вывести в топ Релейную защиту? :)
Надо всего лишь угадать буквы из айдишника, 676 вариантов - не так и много

→ Ответить

KirillB

13 лет назад, # ^ |

Лучше тогда создать аккаунт Codeforces и вывести совместно его в топ. Хорошо бы еще рисунок какой замутить)

→ Ответить

13 лет назад, # |

А что за скрипт по оценке решенных задач и их сложности? Можете рассказать?

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Кажется речь о http://vspu.org/timus_rating.jsp
Кстати я не понимаю в чём сложность отпарсить новую страницу. (можно например загрузить скриптом эту страницу и парсить код, а можно просить пользователя вставлять код.)

→ Ответить

13 лет назад, # ^ |

Как человек, который тоже написал парсер тимуса, могу сказать, что тимус меняет оформление страницы в среднем раз в 4 месяца. Тупо надоедает :).

→ Ответить

13 лет назад, # ^ |

+10

Расскажите, пожалуйста, с какой целью вы парсите Тимус. Может быть, на сайте не хватает какой-то функциональности?

→ Ответить

13 лет назад, # ^ |

Вывести список конкретных людей и конкретных задач.

→ Ответить

13 лет назад, # ^ |

То есть таблицу с плюсами и минусами? Такая задача есть в наших планах

→ Ответить

13 лет назад, # ^ |

Рад. Хотя все равно бы не отказался от какого-нибудь API, позволяющего как минимум делать запрос о посылках конкретного участника, а как максимум - делать посылку и узнавать результат. Было бы очень здорово.

→ Ответить

13 лет назад, # ^ |

Да, я тоже парсил для получения такой таблицы. Правда скрипт получался медленный, ибо это нужно много страничек загрузить и это как то медленно... На самом деле было бы очень удобно иметь такую возможность, ну или API, как замечено выше.

→ Ответить

OSt

13 лет назад, # ^ |

← Rev. 3 →

После последних нововведений скрипт пришлось переписывать.

Раньше, чтобы получить всю нужную информацию достаточно было просто на странице автора скопировать содержимое страницы в поле ввода скрипта.

Буквально вчера скрипт был переписан и теперь желающим им воспользоваться придется скопировать уже исходный текст страницы автора.

Раньше всячески избегалась идея о автоматическом получении содержимого страницы автора в силу разных причин, но ввиду последних нововведений каким-то образом всё равно придется передавать скрипту содержимое страницы. Сейчас вроде есть в планах всё-таки максимально безопасно реализовать "вытягивание" данных непосредственно с сайта дабы убрать эту функцию с неповинного пользователя.

→ Ответить

13 лет назад, # ^ |

Главное анти-флуд не забудьте прикрутить какой-нибудь адекватный и будет всё ок.

А Timus.API было бы вообще хорошо. :3

→ Ответить

13 лет назад, # ^ |

А зачем пользоваться этим скриптом, если примерно то же самое можно увидеть в архиве задач, если упорядочить задачи по сложности?

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Видимо потому что это не отражает реальной статистики, ибо есть много людей, которые давным давно что-то решали и потом забили. Таким образом задача примерно из последних томов с 200-300 АС нормально решается, а задача из первого тома с таким количеством АС для многих настоящий ад.

UPD. А в этом скрипте более менее они выстроены по сложности.

→ Ответить

13 лет назад, # ^ |

Что ж, предложите адекватную формулу расчета сложности, и мы ее реализуем.

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Я не знаю точно, но кажется на vspu люди сами составляли рейтинг задач. Хотя может это и не так: можно просто ввести рейтинг по количеству сдавших, умножая на какой-то коэффициент зависящий от номера тома. Либо можно ограничить количество учтённых авторов, то есть учитывыть например только АС тех авторов, которые за последний год-два решили хотябы одну задачу.

→ Ответить

13 лет назад, # ^ |

Ну, мне кажется, хорошая формула должна как-то соотносить количество авторов по задаче с количеством авторов ближайших задач. Это будет нивелировать эффект "накопления" авторов со временем. Другое дело, что нужно еще как-то учитывать "эффект контеста" - ближайшие задачи могут дать bias, потому что на сложных контестах мало авторов вследствие их сложности, а не эффекта времени. Мне кажется, неплохая модель для ожидаемого количества авторов задачи (предполагая, что сложность всех задач одинакова) - это A*exp(B*t), где A и B - это некоторые константы, а t - это время, прошедшее с даты публикации задачи. Константы можно оценить ОЛСом в логарифмическом виде по всей выборке задач на тимусе. Тогда мы получим для каждой задачи некоторое число Ei - среднее ожидаемое количество авторов, скорректированное на эффект времени. Тогда Di = Ei/(реальное количество авторов задачи i) будет ее сложностью (чем число выше - тем выше сложность). Ну и можно это как-то отнормировать при желании, например Ni = (1-exp(-Di))/(1+exp(-Di)) - сложность от 0 до 1

→ Ответить

OSt	13 лет назад, # ^ \| 0 >соотносить количество авторов по задаче с количеством авторов ближайших задач. Рейтинг VSPU использует подобную идею и как видно - весьма не плохо. >предполагая, что сложность всех задач одинакова Мне кажется это не так. → Ответить

13 лет назад, # ^ |

Ну так это предпосылка для расчета сложности - соотносить реальное количество авторов с количеством авторов, которое было бы, если бы сложность всех задач была одинаковая.

→ Ответить

13 лет назад, # ^ |

Про скрипт уже ответили. :)
А спам удалят? ^_^

→ Ответить

13 лет назад, # |

Интересно, почему на новый вид не переведена например эта страница http://acm.timus.ru/author.aspx?id=64655

→ Ответить

Baurzhan

13 лет назад, # ^ |

по ходу на новый вид переведены только те авторы, у которых >=100 решенных задач.

→ Ответить

13 лет назад, # |

Как пользоваться Тестером для java кода? На примере покажите пож-та.

→ Ответить

13 лет назад, # ^ |

Очень просто :)
!test.exe java Solution

→ Ответить

13 лет назад, # ^ |

Имею ввиду как настроить .ini файл, чтобы программа проходила через n наборов теста. Допустим у меня есть input.txt, output.txt, A.java. Не могли бы по по пунктам написать как протестировать java код?

→ Ответить

13 лет назад, # ^ |

Скопируйте input.txt в tests/01, а output.txt - в tests/01.ans

В !test.ini поменяйте:

RunProgram = java A

Остальные параметры оставьте как есть.

Следующий тест назовите 02 и 02.ans и т.д.

→ Ответить

13 лет назад, # ^ |

ERROR: No input files were found. Не видит входной файл.
Разве у меня не будет только один файл? Т.е допустим программа сложения двух чисел A+B. В input.txt:
2 3
1 1
4 5
В output.txt:
5
2
9
При запуске нужно писать:

!test.exe java A ?

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Вообще-то, тестер предназначен для запуска на серии тестов. Чтобы запустить программу просто для файлов input.txt и output.txt выполните

!test.exe -run:"java A"

Учтите, что файл output.txt в этом случае перезапишется

→ Ответить

13 лет назад, # ^ |

Спасибо! Разобрался. Удобная программа, когда проверяешь на большом наборе тестов.
Но было бы еще удобнее, если набор тестов и ответов были в одном .in и .ans файлах соответственно.
п.с.: Не знаете можно настроить так? :)

→ Ответить

13 лет назад, # ^ |

Назовите ваши файлы 01.in и 01.ans, а в настройках укажите

TestInput = 00.in

TestAnswer = 00.ans

→ Ответить

13 лет назад, # ^ |

Все классно, но когда все тесты кидаешь в один 01.in, 01.ans файлы программа завершается не тестируя второй пример. Не удобно создавать порядка 20 in, ans файлов, чтобы протестировать 20 примеров.

→ Ответить

13 лет назад, # ^ |

My eyz, my eyz!! Im blinded!!

→ Ответить

13 лет назад, # ^ |

Что это было?

→ Ответить

13 лет назад, # ^ |

1) лучшее решение проблемы - создать необходимое число файлов тестов по шаблону выше. муторно? возможно. зато в дальнейшем будет удобно пользоваться. 2) самый простой вариант - переделать программу так, чтобы она работала по принципу мультитестов и считывала данные пока ей их дают. но тогда встанет серьёзный вопрос об оценке времени выполнения.

→ Ответить

13 лет назад, # |

Не знаете почему частенько выходит ошибка: crach (ACCESS_VIOLATION) ?

→ Ответить

13 лет назад, # ^ |

Может, обращаетесь к памяти, которая вам не принадлежит? Можно взглянуть на код?

→ Ответить

13 лет назад, # ^ |

Конечно.

import java.io.*;

import java.util.*;

public class A {

public static void main(String[] args) throws IOException {

new A().run();

}

PrintWriter pw;

Scanner sc;

public void run() throws IOException {

sc = new Scanner(new File("input.txt"));

pw = new PrintWriter(new File("output.txt"));

int a = sc.nextInt();

int b = sc.nextInt();

pw.print(a+b);

pw.close();

System.exit(0);

}

→ Ответить

13 лет назад, # ^ |

Вы бы FAQ почитали, он для этого и создан. Там без файлов все.

→ Ответить

dalex

13 лет назад, # ^ |

Кстати, недостаток Тимуса: если написать System.exit(1), не будет Crash.
Будет либо AC, если в выходной поток уже выведен верный ответ, либо WA в противном случае

→ Ответить

OSt	13 лет назад, # ^ \| 0 Да поможет вам в вашем dirty debug throw new Error() → Ответить

dalex

13 лет назад, # ^ |

Это фикс со стороны участника, а хотелось бы - со стороны Тимуса...

→ Ответить

yeputons

13 лет назад, # ^ |

Да там еще и Exception'ы кидать нельзя в C++. Раздражает.
Думаю, они просто не дописали несколько строк в своей "обёртке", которая цепляется к программе как дебаггер и ловит исключения процессора. А вижак кидает свои точно также, но с другим кодом. Вот этот код сейчас никто отличать не умеет.

→ Ответить

13 лет назад, # ^ |

А зачем Вы кидаете исключения в acm-овских программах, на вход которым почти всегда поступают корректные данные? Вы пытаетесь строить на этом логику работы?

А если по существу, то скажите, на каких acm-соревнованиях можно кидать исключения в C++? Лично я этот вопрос не изучал, и считаю, что даже если на каком-то одном соревновании так можно делать, то все равно найдутся другие, на которых так делать будет нельзя (и об этом не будет объявлено заранее).

→ Ответить

yeputons

13 лет назад, # ^ |

===================================
Например, мне удобно так писать геометрию. Определили структуру "прямая", оператор &, и кидаем исключение, если прямые не пересекаются. Конечено, если не требуется выполнять такую операцию тысячи раз - всё-таки выброшенное исключение тормозит.

Не изучал этот вопрос. Разумеется, где-то будет нельзя. Это обычно выясняется на пробном туре и запоминается. А вот на тренировках хотелось бы концентрировать внимание на решении и написании задачи, без проблем с ограничением на стэк 8МБ (IOI, могут быть проблемы с сложным DFS'ом - надо эмулировать стек ручками или писать BFS) и запрещёнными исключениями.
Казалось бы, в рамках одной конкретной проверяющей системы их отфильтровать от всего остального не очень сложно. Поправьте, если ошибаюсь

→ Ответить

13 лет назад, # ^ |

===================================

Не понимаю такого подхода, по-моему на тренировках надо писать так же как и на соревновании. Зачем для этого какой-то отдельный стиль?

→ Ответить

yeputons

13 лет назад, # ^ |

==========================
Я не совсем правильно употребил слово "тренировка". Имелось ввиду не пятичасовое командное прорешивание за несколько недель до олимпиады, а регулярная сдача нескольких задач в день "для поддержания формы".
Казалось бы, тут главное не приближенность к соревнованию, а решение.

→ Ответить

OSt	13 лет назад, # ^ \| +5 Помнится на Java выкинуть исключение - самый быстрый способ выйти из рекурсии :-) → Ответить

13 лет назад, # ^ |

Возможно исключения и другие плохие завершения программы есть смысл кидать, чтобы подобрать тест к нерадивой задаче. :-)

Пример. :-)

→ Ответить

13 лет назад, # ^ |

Жесть... три какие то палевные решения (саратовский жаргон случайно вырвался :) ).. потом убитая ночь и 750 попыток.. а стоило всего-лишь сесть подумать и вечерком сдать.

→ Ответить

13 лет назад, # ^ |

Как говорится, мопэд не мой)

→ Ответить

13 лет назад, # |

В этой теме всплыла ссылка на скрипт http://www.vspu.org/timus_rating.jsp , а какие еще есть полезные ресурсы для людей, прорешивающих Тимус?

→ Ответить

13 лет назад, # ^ |

Хочется больше задач :) ...а то они как-то редко добавляются.

→ Ответить

kuzmichev_dima

13 лет назад, # |

На Тимусе появилась "сложность" задач и возможность сортить по ней
PS вроде никто раньше не писал, это появилось только сегодня

→ Ответить

13 лет назад, # ^ |

Прикольно. И вроде бы не совпадает с рейтингом vspu.
Но не сказать, чтобы очень адекватно... 1822 совсем простая - бинпоиск по ответу и поиск в глубину. А находится ниже (сложнее чем) 1828 (производная) и 1706 (кмп/z/хэши). Хотя это лишь ИМХО.

→ Ответить

OSt	13 лет назад, # ^ \| 0 Есть сильное подозрение, что на vspu не зря рейтинг обновляется примерно 1 раз в год. За это время добавляется солидное число задач и рейтинг новых задач весьма "устаканивается". → Ответить

13 лет назад, # ^ |

Ну с новыми задачами что-то тоже надо делать. Если рейтинг будет обновляться в онлайне и устаканиваться по мере жизни задачи, то вроде бы ничего плохого не случится.

→ Ответить

13 лет назад, # |

+11

Сегодня я добавил экспериментальную формулу сложности задачи. Теперь задачи можно упорядочивать по сложности в архиве задач и в карте решенных задач в профиле. Жду ваших предложений/замечаний.

В двух словах о формуле. Она учитывает только количество сдавших задачу авторов и возраст задачи. Считается, что за все время жизни задачу сдают примерно с одинаковой интенсивностью, и только в самом начале ее сдают активнее (например, во время онлайн-контеста). Кроме того, считается, что чем раньше задача расположена в архиве, тем вероятнее ее будут решать. Данная модель позволяет более-менее адекватно автоматически упорядочивать задачи по сложности.

→ Ответить

I_love_Tanya_Romanova

13 лет назад, # ^ |

Спасибо! Формула довольно качественно подобрана, так как посмотрел на своем примере - посортировал, сначала галочки все есть, потом начинаются пробелы иногда, потом уже галочек меньше половины, а дальше проскакивают "случайные успехи".

Теперь наглядней вижу, что можно в первую очередь сдавать.

→ Ответить

mmaxio

13 лет назад, # ^ |

Было бы неплохо вернуть кнопку перехода к следующему/предыдущему тому.

→ Ответить

13 лет назад, # ^ |

← Rev. 13 →

Я провел некоторый эконометрический анализ - и оказалось, что лучшая зависимость между количеством авторов и временем - это ln(authors) = a + b*t, где t - это время от публикации задачи до сегодня, как я и писал раньше (R^2 около 35%, что неплохо, учитывая разброс по сложности). Исходя из этого я построил свой рейтинг задач, и он довольно неплохо работает (с вашим хорошо коррелирует, но не во всем). Если интересно - могу прислать результаты моего мини-исследования. Кроме того, я нашел неплохую нормировку рейтинга от 0 до 1.

Собственно, ниже картинка, показывающая обнаруженную зависимость (не знаю, почему не отображается, но можно в новом окне открыть)

→ Ответить

13 лет назад, # ^ |

Можете пояснить, что значат эти графики?

Я изучал графики количества авторов, сдавших конкретную задачу. Это количество растет линейно в течение всего времени, кроме первых 4 месяцев. В первые месяцы задача сдается чаще. Эту ситуацию можно вообще не рассматривать, так как подавляющее большинство задач старше 4 месяцев. Текущая формула немного завысит сложность новых задач, но я не вижу в этом ничего страшного.

→ Ответить

OSt

13 лет назад, # ^ |

А почему бы не сделать так, чтобы пользователи сами устанавливали рейтинг задачи? Понятно, что решение в стиле - "отметить по шкале от 1 до 10 сложность задачи" не катит. Но а что, если бы пользователю предлагалось на сравнение 2(?) задачи и он бы выбрал - какая из них показалась ему сложнее. В фильме "социальная сеть" это правда уложило сеть универа, но всё-таки :-)

→ Ответить

13 лет назад, # ^ |

1) Сложность для каждого участника достаточно редко будет объективна.
2) Не все захотят ставить эту сложность.
3) Проблема флешмобов а-ля "давайте выведем сокобан в самые простые".

→ Ответить

13 лет назад, # ^ |

← Rev. 3 →

Графики построены в эконометрическом пакете EViews. По оси x - фактически время, прошедшее с даты публикации (на самом деле - задачи в тимусе по порядку, но на графике это почти то же самое, по оси y - логарифм <количества авторов + 1>. Имхо, линейная зависимость между этими величинами неплохая. Как я написал, я проверял чисто линейную зависимость (которую используете вы) - результаты намного хуже по всем критериям (Akaike, Schwartz, общая значимость регресии и R^2, хотя он здесь плохо применим). График классический: красным - показано фактическое количество логарифма авторов, зелененьким (почти прямая линия - непрямая потому что публикация задач не совсем равномерна во времени) - матожидание количества авторов, синим - остатки регрессии. Как видите, fit совсем неплохой, большие отрицательные ошибки около 400-го наблюдения отражают сложные задачи в конце 4-го тома, что согласуется с реальностью.

Если вы пришлете мне графики количества авторов, сдавших конкретную задачу, я смогу провести более подробный анализ. Ведь вполне может оказаться, что линейная зависимость, обнаруженная на глаз - вполне может быть экспоненциальной зависимостью с не очень большим коэффициентом роста. Кстати, в моих результатах так и есть: регрессия вида LAUTH = 4.42832683 + 0.0007194597997*T, или, если взять экспоненту:

(авторы) = e^4.42 * exp(0.0007 * (время с даты публикации в днях))

P.S. Формула с логарифмом учитывает тот факт, что сначала задача сдается "Активно" (при t=0 сразу имеем кол-во авторов ~ e^4.42), а потом - более размеренно (коэффициент роста со временем ~ в e^0.25 раз в год

→ Ответить

Trytrytry

13 лет назад, # |

Тоже хочу решить весь тимус.

→ Ответить

I_love_Tanya_Romanova

13 лет назад, # ^ |

У меня пока менее крутая цель - сделать связными верхнюю и нижнюю строку списка задач (если двигаться можно только по зеленых).

Пока у меня можно добраться еле-еле до второго тома))) А если двигаться и по диагонали тоже - до четвертого.

Сделаю это - глядишь, начну гоняться за полностью решенными строками/столбцами...

А там уже можно будет и весь сайт сдавать)

→ Ответить

13 лет назад, # |

Сегодня обнаружил давно желанную фичу - сравнение карты задач двух авторов. Пример.

→ Ответить

13 лет назад, # ^ |

Скажите, пожалуйста, для чего вы используете сравнение карт решенных задач двух авторов? Сравниваете только себя и других авторов или двух произвольных авторов? Нам нужно это знать, чтобы сделать этот инструмент удобнее.

→ Ответить