at1's blog

By at1, 9 years ago, In Russian,

Контест

  Мне контест очень понравился, как отличная тренировка решения ботвистых задач. Мне не нравится, когда условие неполно, некорректно, неоднозначно. Здесь же все условия интуитивно понятные (мне) и, вроде, абсолютно корректные.
  Также, по задачам подготовлены очень хорошие тесты (могу оценивать только то, что дорешал A-C).
  Так что, к авторам вообще не может быть претензий, они подготовили оригинальный, качественный сет  задач. Лично мне контест очень понравился, хоть и поверг мой рейтинг в пучины отчаяния =).
  В каждой комнате все равны перед задачами и взломами, поэтому не вижу проблем с "неравенством" положений, о которых все пишут. Ну сразу же понятно, что в A всякие крайние случаи сыплются, а значит либо аккуратно на бумажке придумываешь решение, либо злостный тест, а лучше и то и другое. А дальше все покажет опыт, как и на других контестах.

Read more »

 
 
 
 
  • Vote: I like it
  • +16
  • Vote: I do not like it

By at1, 9 years ago, In Russian,
Да, мы действительно написали n*log(n). И действительно TL. Видимо бага.
Если кто-то найдет её в алгоритме или пошлет мне хороший тест буду очень признателен.

// Генерил рандомные деревья (через снм), ежей, цепочки и т.п., на ноуте за 1.5 сек работает.

Условие:

В дерево T ответить на запросы radius[v, i] - количество вершин достижимых из v не более, чем за radius[v, i].
|T| <= 105; |{radius[v, i]}| <= 3*105

Read more »

 
 
 
 
  • Vote: I like it
  • +33
  • Vote: I do not like it

By at1, 9 years ago, translation, In English,
This blog entry and comments give me a lot of ideas about rating system, and I am doubling ideas in my blog.

I think color changes are always give a lot of fun for competitions, so recent changes (increasing number of colors) are liked by me.

I have an idea that one can interpolate colors by some main values:
on interval [ai, ai+1] the color value will be colori * (ai+1 - rating) + colori + 1 * (rating - ai))

With such formulas one can get different amazing effects (for example, around top interval use non-linear interpolation to some target color).

Something as this:


the same but with initial interval:

(this main values of colors maybe not suitable, this pictures just for clarity)

Also, one can interpolate not by rating but by absolute place of competitor.
For my opinion this will be more interesting system.

Read more »

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

By at1, 10 years ago, In Russian,

A. Треугольник

Из трех палочек с длинами a, b, c > 0 можно составить треугольник ненулевой площади тогда и только тогда, когда:
|a - b| < c < a + b (+)
При вырожденном случае в (+) одно из неравенств обращается в равенство. (Для обоснования можно построить окружности радиуса a и b с центрами в концах отрезка длины c, и проверить когда они пересекаются).

Таким образом, можно перебрать все тройки чисел из данных 4-х и проверить (+).

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By at1, 10 years ago, translation, In English,

A. Watermelon

Only if w can be presented as 2m + 2k watermelon can be divided to two even parts.
So w = 2(m+k), where m, k1, that is
(w 4 и w - even) - necessary and sufficient condition for watermelon dividing.

Read more »

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it