Блог пользователя Sereja

Пятая индивидуальная интернет-олимпиада
Автор Sereja, 14 лет назад, По-русски
Сегодня прошла пятая индивидуальная интернет-олимпиада на сайте neerc.ifmo.ru/school. Давайте здесь обсуждать решения задач.
  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Давайте.
Кто как решал задачи C и D?
→ Ответить
  • 14 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
    Я свел C к тому чтобы найти длину самого длинного отрезка на котором сумма 0. Отнимем от всех чисел K и найдем такой отрезок - это и будет ответ.
    → Ответить
    • 14 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      а как искать отрезок с заданной суммой?
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится
        Предподсчитаем суммы на префиксах. Получаем массив sum от 0 до n. Сумма на отрезке [l..r]=sum[r]-sum[l-1]. Нужно найти в массиве два числа с заданной разницей (в данном случае - два равных). Бежим справа налево и делаем пометки в массиве (или заносим в set) числа, которые уже были. Когда наткнулись на число, прибавили к нему требуемую сумму на отрезке и посмотрели, были ли такие числа. Если надо найти макс. по длине отрезок - храним только самое правое.
        → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        С суммой 0 можно map-ом или сортировкой+дихотомией. В map-е храним когда первый раз встретился префикс с такой суммой. Потом перебираем правую границу. Пусть сумма до нашей правой границы равна X. Тогда левая граница это следующий за наименьшим по длине таким префиксом, сумма которого равна X.
        → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    не решал, посмотрел условия... По С идея такая...
    Считаем отклонения от среднего и храним в мапе последний номер на котором получается данное значение. Для первого ищем положение Z=0, для второго Z = Z - K + A[1] и тд... Получаем O(n*log(n))
    → Ответить
14 лет назад, # |
← Rev. 4   Проголосовать: нравится +6 Проголосовать: не нравится
Напишу про свои решение(не знаю будет ли у меня по всем 100, но вроде должно быть):
1я задача:
когда идем по строке , просто смотрим был-ли у нас такой символ раньше, если был то не делаем ничего , иначе к ответ добавляем этот символ и помечаем его
2я задача:
Написал скольжение , но походу можно было делать и так:
пишем перебор для маленьких , и видим что ответа для Н=9 уже нету, то есть там нужно всего несколько забить в константу.
3я задача:
Сначала напишем такое решение:
Sn=A1+A2+...+An
отрезок [j+1;i] подходит если (Si-Sj)/(i-j)=k => Si-Sj=k*i-k*j => Si-k*i=Sj-k*j,
то есть все что нужно сделать, так это отсортировать все такие значения, и для равных найти мин/мах номер, зная их знаем решение.
ну и 4я задача:
сначала посчитал для каждого кол-ва гласных, можно-ли его получить. Потом нашел все "нужные" суффиксы и отсортировал их . Если в какой-то группе равных суффиксов есть два возможных "окончания", то беру их и строю с ними в конце. Посмотреть можно или нет, поставить что-то в конец делаю с помощью того пред посчитанного массива , можно-ли получить какую-то сумму. За это задачу как-раз сомневаюсь больше всего...

→ Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Выбирал между ней и CF55Div2, в итоге выбрал второе. Как оказалось, не зря)
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Я тоже=))
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится
      Ну я как-то и то и то написал =) Все-же 3 часа довольно достаточно что-бы решить хотя-бы большую часть задания.
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Не, для меня это сложновато) Видно, опыта подобных соревнований пока не хватает.
        → Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
В 4-й задаче надо было использовать обязательно все слова?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Я использовал не все слова)
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Вывод для примера
    cat cat cat cat cat my
    cat cat cat cat happy
    прошел первый тест.
    → Ответить
    • 14 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
      Значит я условие понял неправильно :)
      Но все равно как-то странно, если можно использовать не все слова то задача совсем простая.
      → Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Странно что никто не спрашивает.
А где результаты ? 
Вроде день прошел, а их все нет и нет :)
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    На этих же задачах (на английском) в тот же день, но в 9 утра по Москве проводился I-Cup на сборах в Давосе (Швейцария). После окончания тестирования наших посылок система рухнула. Видимо, поднимают.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      Система не падала:)
      Просто результаты пока не опубликовали в связи с занятостью жюри...
      Скоро все будет!
      → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Это уже не впервые , иногда приходилось ждать по несколько дней.
    → Ответить