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

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

← Rev. 2 →

-10

Вопрос по задаче C: Почему такие ответы на тесах из условия? (У меня получилось Unique ("aaa") и Impossible соответственно)? Условие несколько раз перечитал и не понял.

→ Ответить

agul	12 лет назад, # ^ \| 0 если строка была палиндромом изначально, мы в начало и в конец добавили палиндромы, то получившаяся строка тоже палиндром => дедушка ошибся. → Ответить

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

-9

Что-то до меня не доходит... Я понял так: загадано "aaa", слева дописали 'a': "aaaa" - палиндром, справа дописали 'a': "aaaaa" - тоже палиндром. Другой палиндром загадать невозможно, значит ответ unique. Что здесь не так?

→ Ответить

vilcheuski

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

← Rev. 2 →

В конце не должен получаться палиндром. Т.е. какая не была бы начальная строка, являющаяся палиндромом - в конце дописываний получится палиндром.

→ Ответить

agul	12 лет назад, # ^ \| 0 Можно загадать палиндром BBB, CCC, DDD, ..., QQQQ, ... → Ответить

Sereja

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

В конце не должно быть палиндрома. А если брать ааа, то в результате будет ааааа, что не подходит.

→ Ответить

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

-9

Всё. Понял, что игра до первого непалиндрома а не определённое кол-во ходов.

→ Ответить

agul	12 лет назад, # \| 0 Как решать B, E, F? → Ответить

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

B. Понятно, что штаб должен быть центром дерева. Мне сложно строго это доказать, но интуитивно понятно. Ищем центр дерева и проверяем симметрию. Берем два дерева, корнями которых будут соседи центра. Для каждого уровня каждого дерева выпишем все степени вершин и отсортируем их. Проверим на равенство два набора списков. Если равны - ДА, не равны - НЕТ.

→ Ответить

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

Задача B:

Я сначала подвесил дерево за вершину, из которой проходит ровно одно ребро. Затем подсчитал cnt[i] - количество вершин в поддереве, вершиной которого является i-я вершина. Нам будет подходить такая вершина x, что кол-во соседей у нее 2(назовем их l и r) и cnt[x] *2+1= n. Таких вершин не более 1. Если мы нашли такую вершину, подвесим дерево за нее. Теперь пересчитаем cnt. Запишем эти значения в два разных массива (если путь от i-й вершины до x-й проходит через l, то в первый массив, иначе во второй). Отсортируем по возрастанию числа в этих массивах. Если массивы совпадают, то YES иначе NO

→ Ответить

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

← Rev. 2 →

Контртест к обоим этим решениям:

1 5

2 6

3 6

4 7

5 8

6 9

7 9

8 10

9 11

10 11

11 12

23 19

19 16

20 17

21 18

22 18

16 14

17 14

18 15

14 13

15 13

13 12

Штаб – вершина 12, с номерами меньше 12 – левая часть, остальные – правая.

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

→ Ответить

malcolm

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

Мы написали хеширование деревьев. Хеш для одной вершины - константа. Для дерева - сортируем хеши всех поддеревьев, которые можно достигнуть по одному ребру, а далее берем какой-нибудь полиномиальный хеш от полученного отсортированного массива.

→ Ответить

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

А по какому тогда основанию должен быть полиномиальный хеш?

→ Ответить

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

← Rev. 2 →

Да, пожалуй, мое решение не верно. Хотя вполне возможно, что оно пройдет этот тест.

UPD: ан нет. не проходит

→ Ответить

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

интересно, у гены этот тест пройдет?

→ Ответить

Kostroma

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

это прошло тесты жюри?

→ Ответить

vilcheuski

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

Подскажите кто-нибудь, как решать задачу E(Зарплата) и C(Игра).

→ Ответить

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

C. Представим нашу строку как граф. Вершины - символы. Ребра между символами будут обозначать равенство этих символов. Забьем начальную строку вопросами. Далее будем добавлять строки, которые говорит девочка. Каждый раз будем проводить ребра 0 --- (n-1) 1 --- (n-2) и так далее. То есть так, чтобы строка становилась палиндромом. Для последней полученной строки не будем этого делать. Когда добавили все строки, запустим дфсы из всех символов, не являющихся вопросами и будем красить всю компоненту связности в нужную букву. Если встретили противоречие, т.е. мы хотим покрасить одну букву в другую - кидаем impossible. Если все хорошо, допишем последнюю строку и проверим, что не получается палиндрома. Если получается - impossible. Иначе, если есть вопросы, то ambiguous, нет - unique.

→ Ответить

Skird

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

В задаче Е достаточно заметить, что все кубы будут не длиннее 54 знаков (на самом деле даже 49), а дальше просто искать первый и последний куб данной длины. Первый куб данной длины можно найти из последнего куба предыдущей, а последний, например, бинарным поиском. Потом необходимо определить, к кубу какой длины относится позиция k и вывести нужную цифру нужного куба. В этом решении нужна длинная арифметика.

→ Ответить

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

← Rev. 2 →

а без длинки нельзя? вы же пишите: все кубы будут не длиннее 54 знаков, зачем длинка?

P.S. ~~я ебнулся~~ я ошибся((( у меня 54 ассецировалось со степенью(то есть я подумал 2^54, думаю, че такого, long long и 63 держит) =)

→ Ответить

Joshik

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

А в какой тип данных помещается 10⁵⁴? :)

→ Ответить

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

да ошибся я) выше написал

→ Ответить

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

А кто как решал H? Я возводил матрицу смежности в степень k. За n^3*logk/64. Я почти уверен, что есть решение попроще и побыстрее.

→ Ответить

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

Там обыкновенный бфс по состояниям.

→ Ответить

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

Поясните, пожалуйста.

→ Ответить

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

Построим граф. Вершинами будут состояния(i,0) и (i,1) для всех i от 1 до n, ребрами будут переходы из (u[i],k)в (v[i],1-k),где k=0,1; i от 1 до m. Запустим на этом графе BFS. Тогда дедушка Марат мог остановиться в i-м доме, если кратчайшее расстояние от (1,0) до (i,k mod 2) не превосходит k. Это вроде работает(ну у меня точно).

→ Ответить

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

О, да, точно, спасибо. Красивое решение.

→ Ответить

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

Я тоже сначала хотел возводить в степень, потом сдал это с кривыми руками за +3.

→ Ответить

Zhandos

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

← Rev. 2 →

Можешь код показать? Я вроде также решил, но 14 тест WA.

→ Ответить

http://pastie.org/2852664

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

Писал на Delphi 7:

→ Ответить

Snipx

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

в тесте 14 надо проверять чтобы минимальное расстояние до i-ой вершины было >= k

→ Ответить

Snipx

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

Как F решать?

→ Ответить

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

Идея состоит в том, что при повороте плоскости на 45 гр. против часовой стрелки и домножении координат точек на sqrt(2) мы приходим к ситуации, когда часовые стоят в точках (х-у;х+у) и освещают часть плоскости, границы которой параллельны осям координат. То есть если направление 'N', фонарик освещает всех часовых с x<=x',>=y'. Если 'E', то x>=x', y>= y' и так далее.

Приходим к задаче, когда нам надо уметь отвечать на запросы offline типа "все точки, у которых x<=(>=)x' и y<=(>=)y' ". Такое я делал с помощью дерева отрезков.

→ Ответить

wackloner

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

Нет, ну, задача про зарплату доставила, простая ужасно, но, тем не менее, минут 20 не могли найти ошибку, а ошибка, похоже распространенная, в том, что номера месяцев не в интервале [1..12], а просто увеличиваются на 1 каждый новый месяц :\

→ Ответить

vilcheuski

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

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

→ Ответить

CherryTree

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

Там не закономерность. Если вкратце, перебираем сколько цифр будет в кубе очередного числа, там не больше 60 цифр. Потом дихотомией подбираем минимальное и максимальное число с таким числом цифр в своем кубе. Потом, зная это можно определить что число имеет больше цифр чем мы пытаемся подобрать сейчас или что кубу какого числа принадлежит k-й символ.

→ Ответить