Вторая командная интернет-олимпиада (neerc.ifmo.ru/school/io/)

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

Хотелось бы узнать решение задачи А

→ Ответить

nerd	13 лет назад, # ^ \| 0 А если перебирать sinx. И каждый раз строить две линии и проверять. Я сам не пробовал, но была идея. → Ответить

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

Интересует не идея, а решение, проходящее тесты.

Сами перебирали угол с точностью до 10^-5и проводили две прямые, но получали WA33

→ Ответить

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

Ну ещё бы.
Чтобы отличить вектор a = (5e8 - 1, 5e8 - 2) от вектора b = (5e8 - 2, 5e8 - 3) нужно тыкнуться в интервал шириной $\text{[math]}$ . Вы не успеете проверить столько интервалов, да и точности стандартных типов близко не хватает.
Целочисленная арифметика спасает мир. Понятно, что существует решение, где прямая разбиение попадает в одну из свечей с отклонение в ε. Как проще всего отклониться от вектора v на эпсилон в целых - находим вектор kv, не лежащий внутри торта, и берём, например, вектор kv + (0, 1). Его координаты будут взаимно просты, значит строго внутри угла между векторами kv и kv + 1 не будет целых точек в торте.
Вот и перебираем для каждой свечи вектора kv + ( ± 1, ± 1) в качестве направляющих в разрезе. Пишется архипросто.

→ Ответить

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

← Rev. 2 →

мы искали такой порядок из данных 4 векторов, что численное векторное произведение любых двух подряд идущих больше нуля (почти сортировка по углу). если таких нет, то NO

после этого в найденном порядке смотрели для противоположных векторов в нем угол между ними. если один из этих углов меньше либо равен 90 - NO

иначе YES

→ Ответить

evg-zhabotinsky

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

← Rev. 2 →

У меня прошло такое:

Пусть каждый кусок имеет свой номер (от 1 до 4 против часовой стрелки).

Очевидно направление кратчайшего поворота вокруг центра между свечами на последовательных кусках (например от свечи на 1 к свече на 2, порядок важен) должно быть положительным (против часовой стрелки), т.е. синус угла этого поворота положителен, а значит положителен модуль векторного произведения радиус-векторов этих свечей, т.е. X1*Y2-X2*Y1>0 для кусков 1 и 2 ( (X1;Y1) и (X2;Y2) это координаты свечей на кусках 1 и 2). Для остальных аналогично.

Также очевидно, что угол поворота между свечами на не соседних кусках (например 1 и 3) больше 90, т.е. косинус угла этого поворота отрицателен, а значит отрицтельно скалярное произведение радиус-векторов этих свечей, т.е. X1*X3-Y1*Y3<0

Теперь переберем все возможные расстановки свечей по кускам и проверим их на соответствие указанным условиям (утверждается, что их выполнения достаточно для корректности расстановки). Если хотя-бы одна расстановка корректна, ответ 'YES', иначе 'NO'.

PS: не забываем, что указанные выше значения могут не влезть в 32-битное целое

→ Ответить

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

← Rev. 2 →

Интересуют решения задач: А, D, E, F, G, H в сложной номинации;

Больше всего интересно Д, кто-нибудь?

→ Ответить

agul	13 лет назад, # ^ \| 0 Аналогично + задача B. → Ответить

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

← Rev. 2 →

Задача Б:

Отсортируем все коробки по количеству конфет в них (пусть это будет массив a)

Далее для каждого запроса будем бинарным поиском искать ту позицию(p), начиная с которой наглость позволяет съесть по одной конфетой (для каждого i: p ≤ i выполнялось a_i > = x, где x - запрос).

После того как мы нашли такую позицию, ответ будет n - p + 1. Теперь обновим с помощью дерева отрезков наш отрезок [p, n] отняв от него единицу. Так как уменьшается только на единицу, отсортированность останется.

→ Ответить

agul	13 лет назад, # ^ \| 0 У меня были мысли по этому поводу, но вот как делать дальше? Ведь при изменении отрезка мы не напрямую изменяем элементы, а только откладываем операцию. → Ответить

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

← Rev. 2 →

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

В итоге O(mlog²n)

→ Ответить

agul	13 лет назад, # ^ \| 0 Все, понятно, спасибо. → Ответить

evg-zhabotinsky

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

← Rev. 2 →

Можно M log N, если строить дерево для минимумов и в нем искать границу

→ Ответить

pva701

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

вообще, можно было уменьшать значение на 1цу в точке p, а бинпоиском перебирать, и смотреть x <= a[m] - dec[m], где dec[m] сумма всех отнятий на префиксе [1..m], для этого решения хватало и фенвика

→ Ответить

notEphim

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

D элементарна. Создаем массив, в котором будем на i-том месте хранить скорость на i-том километре. Читаем исходный массив, и пока встречаем нули, заполняем массив скоростей последовательными числами. Как только встречаем число, большее нуля, то начинаем идти обратно также записывая последовательные числа начиная с максимальной скорости, пока в какой-то момент последовательность скоростей не станет правильной (т.е такой, как она описана в задаче). Если же максимальная скорость больше возможной, то записываем эту возможную. Так продолжаем до самого конца. Ну, и чтобы найти время, естественно надо просуммировать все числа, обратные скоростям.

Покажу как будет изменяться по такому алгоритму массив скоростей на первом тесте:
0 0 2 0 0 0 1
1 2 2 0 0 0 1
1 2 2 3 4 5 1
1 2 2 3 4 2 1
1 2 2 3 3 2 1- искомый массив скоростей.

→ Ответить

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

А можно по-подробнее, почему это работает на ограничениях быстро? Как Вы создаете массив 10⁵ * 10⁵ = 10¹⁰?

→ Ответить

agul	13 лет назад, # ^ \| 0 Это, вроде, линейный массив, а он просто показал то, как он изменяется по ходу выполнения программы. → Ответить

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

← Rev. 3 →

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

 ........... 
........._. 
.._....._._ 
._...._..** 
..**__*_*.. 
_*..**.*... 
*.......... 

Где горизонтальная черта - это максимальная скорость на соответствующем участке, а звёздочка - величина скорости на этом участке в оптимальном ответе. Можно было взять каждый ограничивающий отрезок и пустить от него лучи вверх и влево-вправо под углом в 45 градусов. А потом пообъединять получившиеся углы.

Можно было понять по-другому. Понятно, что если A[i] - массив ограничений, а V[i] - массив скоростей в оптимальном ответе, то очевидно необходимым является ограничение - V[i] <= A[j] + |j - i| для любого j - действительно, необходимо успеть разогнаться от скорости не выше A[j] до скорости V[i] за |j - i| участков. Значит V[i] <= min{A[j] + |j - i|}. А если взять V[i] просто равным такому минимуму, то несложно заметить, что |V[i + 1] - V[i]| <= 1, то есть такая последовательность скоростей удовлетворяет условию.

Массив V[i] насчитывается очевидным образом за два прохода.

→ Ответить

agul	13 лет назад, # ^ \| 0 А почему бы такое решение, как у товарища, не зашло? Линейное время, все ок → Ответить

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

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

→ Ответить

notEphim

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

← Rev. 2 →

Не не не, мы из сложного, и у нас все прошло

→ Ответить

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

← Rev. 2 →

~~Ага, слабые тесты детектед!~~
Ах блин, не углядел линейное решение.

Извиняюсь за поклеп)

→ Ответить

agul	13 лет назад, # ^ \| 0 Ура, я все-таки был прав (: → Ответить

evg-zhabotinsky

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

← Rev. 3 →

Это решение работает за квадрат, что может не вписяться по времени (например на тесте 100000 99999 99998 ... 3 2 1)

Решение за линейное время: 0)считаем данные в массив a.

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

b[n+1]:=1000000;

for i:=n downto 1 do

begin

b[i]:=b[i+1]+1;

if b[i]>a[i] then b[i]:=a[i];

end;

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

c[0]:=0;

for i:=1 to n do

begin

c[i]:=c[i-1]+1;

if c[i]>b[i] then c[i]:=b[i];

end;

4)Посчитаем, за какое время он с посчитанными выше скоростями пройдет весь путь (сумма обратных скоростям величин)

PS: Как-то объемисто получилось... Никто не подскажет, как сообщения компактнее форматировать? (Уменьшить интервалы хотябы)

→ Ответить

agul	13 лет назад, # ^ \| 0 Мне все равно кажется, что его решение легко оптимизируется до линии. → Ответить

notEphim

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

Вообще-то введеный вами тест даже не требует возвращений назад в массиве скоростей

1 99999 ... 3 2 1
1 2 ... 3 2 1
...
1 2 ... 50000 49999... 3 2 1 (50000-ная итерация) и еще 50000 ничего не изменяющих итераций. Итого 100000 итераций, что проходит за секунду

→ Ответить

sola_93

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

В чём фишка задачи D в базовой номинации? Половину олимпиады думали только над этой задачей..

→ Ответить

nerd	13 лет назад, # ^ \| -7 Там решение за O(1). Закономерность легко находится. → Ответить

agul	13 лет назад, # ^ \| +1 Что за бред, говорить, что там легкая закономерность? Вы скажите эту закономерность, человек же конкретно про решение спрашивает, а не про то, легкая, или нет, там закономерность. → Ответить

nerd	13 лет назад, # ^ \| 0 Координаты: (1;1) ____ (2;1) (1;2) ____ (1;3) (2;2) (3;1) _____ (4;1) (3;2) (2;3) (1;4) _____ (1;5) (2;4) (3;3) (4;2) (5;1) ____ (6;1) .... Постарайтесь найти сами. → Ответить

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

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

→ Ответить

dalex

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

← Rev. 2 →

В первой диагонали 1 дробь, во второй - две, в третьей - три, и т.д.

У нас арифметическая прогрессия, с помощью формулы или бинпоиска находим нужную диагональ, дальше все понятно.

Забавно, сам недавно делал почти такую же задачу (чуть посложнее), условие тут

Станкевич задачи у меня ворует, что же делать, что же делать

→ Ответить

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

Простите, http://www.spoj.pl/problems/CANTON/

Разве что там ограничения хлюпенькие..

→ Ответить

dalex

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

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

→ Ответить

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

Эта задача была придумана младшекурсниками НИУ ИТМО по мотивам лекций по матану :)

Изначально называлась "Кантор".

→ Ответить

Saimon_Saret

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

Делал так же, только находил номер наибольшей дроби, меньший искомого номера из левого столбца с помощью бинпоиска.

→ Ответить

NVAL

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

Около часа решал задачу, сокомандники, увы, посчитали, что A самая легкая и упорно убили на нее все 210 минут, решая на бумаге.
Нашел диагональ(id> n) с четными показателями i, j, потом двигался по ней единичными шагами на уменьшение id. Когда понял, что на 10¹⁸ работает за >10 сек, пришлось оптимизировать до более разумного подхода без единичных шагов, но <1.5 сек сделать не удалось, к счастью для принятия задачи этого хватило.
Расстроила ошибка в примерах, на которой ломал голову, понимая где я что не так понял.

→ Ответить

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

Совет - если даже задача кажется очевидной, но мало кем сдается - значит что-то с ней не так просто :)

→ Ответить

sola_93

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

Это сразу понятно, что там закономерность. Но конкретно какая, так и недодумали. Может кто подскажет?

→ Ответить

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

Если выписать дроби подряд в указанном порядке, посмотрим сумму числителя и знаменателя для каждой дроби. Будет ряд 2, 3, 3, 4, 4, 4 и так далее.

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

t * (t - 1) / 2 < x <= t * (t + 1) / 2

(можно решить дихотомией, например)

и суммой будет t + 1

потом находим порядковый номер искомой дроби в ряду с полученной суммой числителя и знаменателя как n = x - t * (t - 1)

ну а там уже в зависимости от четности t ряд с данной суммой будет выглядеть как 1/n, 2/(n-1), 3/(n-2) и так далее, либо n/1, (n-1)/2, (n-2)/3

ответ уже вывести несложно, нужно найти n-ое число в ряду с постоянной суммой числителя и знаменателя

как-то так

→ Ответить

diogen

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

заметим, что в одной диагонали сумма числителя и знаменателя постоянна и равна n+1, где n - количество элементов. причем первое число диагонали, в зависимости от четности либо 1/n, либо n/1 и каждое следующее число диагонали отличается и в числителе и в знаменателе на единицу от предыдущего. тогда зная номер диагонали на которой наше число, легко найти самое число.
так же понятно, что в каждой следующей диагонали на 1 больше, чем в предыдущей. тогда первый номер элемента диагонали имеет вид x * (x - 1) / 2 + 1, последний - x * (x + 1) / 2 для некоторого x. находим x дихотимией(или как-нибудь хитро за О(1)).
тогда если x - четно, то ответ (x + 1 - k) / k, иначе k / (x + 1 - k), где k - номер элемента на диагонали, равный n - x * (x - 1) / 2

→ Ответить

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

интересует решение задачи Е усложненной номинации (граф)

верно ли, что остовное дерево+жадность не проходит?

→ Ответить

agul	13 лет назад, # ^ \| 0 Мы получали TL 11. → Ответить

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

Значит что-то криво написали.

→ Ответить

agul	13 лет назад, # ^ \| 0 Странно. Писали DFS (для определения связности) + Краскала (MlogN) + жадность. Где не так? → Ответить

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

Ну попробуйте сами оценить асимптотику. O(M + MlogN + MlogN). Не больше десяти миллионов операций.

От себя: дфс можно было и не писать - Краскал спокойно работает и на несвязных графах.

→ Ответить

agul	13 лет назад, # ^ \| 0 Ну мы его писали для того, чтобы определять случай, когда Impossible. → Ответить

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

← Rev. 2 →

Извините, это про задачу Honeywar?

UPD: перекачал условие, видимо это задача "Прыгать!"

→ Ответить

agul	13 лет назад, # ^ \| 0 Нет, это про задачу "Прыгать!" → Ответить

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

А если был крускал, то почему бы просто не проверить, все ли вершины в одном множестве СНМ?

→ Ответить

agul	13 лет назад, # ^ \| 0 Ну тупые, не придумали( → Ответить

agul	13 лет назад, # ^ \| 0 По сути можно было вообще так: если (количество_ребер_в_каркасе) != (количество_вершин - 1), то Impossible. → Ответить

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

← Rev. 2 →

Проходит со свистом.

UPD:

Расскажи задачку про перестановки, интересно.

→ Ответить

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

← Rev. 4 →

блин, я криворукий дебил. точнее, нервы к концу контеста сдали, видимо, не додебажил((

ВА5 словил

кода наворотил, конечно)

UPD нашел баг. мы корявые психи, конечно

по перестановкам - все вопросы к Вике)) я не читал) там решение за линию, и пишется довольно быстро, вот все что знаю)

→ Ответить

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

Ясно. ИОИ == Исхаков-Останин-Игошина?

→ Ответить

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

← Rev. 2 →

да)

но на самом деле теперь вместо Исхакова играет Боков.

так что название придется придумывать)

не зарегали еще одну команду, чтоб играть в усложненной)

→ Ответить

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

хочу посмотреть нормальный код по задаче про распил бревна

→ Ответить

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

Это точно не к нам. Олег такую мутотень там понаписал :-)

→ Ответить

Vaness

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

← Rev. 2 →

Я готов повеситься :( Полконтеста пытался найти баги, но остановился на WA15. У меня там жесть случаев разных.

→ Ответить

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

← Rev. 2 →

а мы кроме этой 2 халявы так и не сдали((

на эту задачу около получаса убили, уже на 3м тесте упали) потом забили и стали писать несданную халяву

→ Ответить

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

Нормальный код будет у жюри:)

Мы скоро выложим тесты и решения.

→ Ответить

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

это радует:)

а открытие полноценной дорешки в планы жюри пока не входит, да?

→ Ответить

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

При текущей нагрузке на сервер это не планируется. И так временами тормозит:(

Возможно, в какой-то момент будет открыто дорешивание всех интернет-олимпиад.

→ Ответить

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

Вот и выложили все архивы.

→ Ответить