COCI 2012/2013 — контест №1

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

Система проверки по блокам без токенов?

→ Ответить

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

Ну, я надеюсь, что система не поменялась — без групп (за исключением там где реально надо) и без feedback'a.

→ Ответить

Zlobober

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

← Rev. 4 →

Запоздал на полтора часа на тур :-\

Успел что-то сдать по всем задачам, совершенно не тестя, чувствую, потеряю баллов на тупых багах. Последняя — интересная. Единственное, что придумалось и быстро написалось — решение за O(2^4K) — динамиика D[v][a][b] — мы находимся в вершине v полного бинарного дерева, причём его листы упорядочены так, что самый левый — a, а самый правый — b. Значение — минимальная длина цепочки в этом поддереве, удовлетворяющей таким условиям на крайние элементы. Пересчитываем, понятно, перебирая барьерное ребро между двумя центральными листами.

До K = 7 работает, а вот дальше начинает тормозить.

Умею разбирать два верхних слоя динамики за побыстрее, а дальше пускать мою эту за O(2^4K), но хочется чего-нибудь покрасивее.

UPD:

Да, как и предполагалось, какие-то баги, баги :-( 50-80-10-120-98-96.

→ Ответить

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

Аналогичное написал, есть подозрение что нужно оптимизить константу такими разбиениями.

→ Ответить

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

У меня сначала было O(2^2K * 2^2K), но это можно превратить в O(2^2K * (2^K + 2^K)). Попробую написать щас.

→ Ответить

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

50-80-100-45-140-160, потому что замутил правый край бинарного поиска на 10^6. :|

→ Ответить

agul

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

Расскажите KONCERT и SNAGA, пожалуйста.

Вроде в SNAGA я нашёл циклическую закономерность значений strength(n) : 2 3 2 4 2 3 2 3 2 3 2 3, но на числах 420 и 360360 она сваливается (возможно, есть ещё такие числа, но перебор их не нашёл).

→ Ответить

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

Число в которое переходит большие числа — маленькое. Будем его перебирать, а потом считать для скольких чисел оно будет переходом.

→ Ответить

agul

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

Можно подробнее?

→ Ответить

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

Смотри, если у тебя есть переход в число х, то нету в х-1, тоесть число должно быть больше НОК(1,2,3,...,х-1). Получаем, что х не велико.
Теперь нам нужно для каждого числа х посчитать — сколько есть чисел, которые кратны 1, 2, ..., х-1 и не кратны х. Это значение равно N/lcm(1,2,...,x-1) — N/lcm(1,2,...,x). Дальше для мелких считаем перебором и лепим все в кучу.

→ Ответить

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

← Rev. 2 →

Концерт — задача на понимание условия.
Отдадим все мальчику №1, затем будем действовать так:
- первый дает билет 2му
- они оба заходят
- второй отдапет билет первому
- первый выходит
И так со всеми.
Потом просто запускаем 1го в зал. Так как билетов не меньше 2х, то все нормально.

→ Ответить

gen

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

У меня девочка одна всех мальчиков провожала...

→ Ответить

mexmans

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

В зависимости от значения strength(n) = 2,3,4,5.. числа удовлетворяющие этим значениям растут очень быстро. Находим для каждого strength(n) = 2,3,4,5.. минимальное число которое удовлетворяет этому strength. Достаточно до 42. И считаем кол-во чисел из этого диапазона умноженное на необходимое число + 1

→ Ответить

andreyv

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

← Rev. 6 →

koncert: Найдём какого-то парня с билетом и какую-то девушку с билетом. Парень отдаёт билет девушке. Теперь для каждого парня: эта девушка даёт ему один билет, они проходят внутрь, парень отдаёт ей билет, девушка выходит.

snaga: Разобьём все числа на такие множества:

x не делится на 2 (здесь strength(x) = strength(2) + 1)
x делится на 2, но не делится на 3 (здесь strength(x) = strength(3) + 1)
x делится на 2, 3, но не делится на 4 (здесь strength(x) = strength(4) + 1)
x делится на 2, 3, 4, но не делится на 5 (здесь strength(x) = strength(5) + 1)
...

Для каждого из множеств можно посчитать, сколько есть таких чисел до нужного нам предела. Будем перебирать эти множества и суммировать их общий strength до тех пор, пока lcm(2, 3, …, k) не станет больше n (тогда уж точно не найдём более чисел).

Считаем эту функцию для b и a - 1, отнимаем второе от первого.

→ Ответить

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

← Rev. 3 →

+13

MARS:

Во-первых, будем действовать снизу вверх, то есть объединять [1..1] и [2..2], [3..3] и [4..4], .... Потом, второй слой — [1..2] и [3..4], [5..6] и [7..8] и.т.д. Так пока не объединим всё.

Во-вторых, можно заметить, что если у нас есть цепочка с началом l и концом r (обозначение: {l-r}), то мы однозначно можем определить её длину. И какие числа в ней. Это упрощает реализацию и даёт, что у нас 2^2K положений.

Будем делать ДП — a[l,r] = минимальная длина {l-r}. Будем считать их в порядке объединения отрезков (см. начало). То есть, если мы сейчас объединяем [17..24] и [25..32], то мы на данном этапе считаем a[l,r] где l любое число в [17..24], а r — любое число в [25..32].

Тогда a[l,r] = min(a[l,x] + dist[x,y] + a[y,r]), где x — неравный l число из половины же l, а y — неравное r число из половины r (если объединяем отрезки длины 1 — оно не может быть неравное — особый случай). Итого получаем O(2^2K * 2^K * 2^K), так как надо выбирать x и y.

Не забываем потом, что a[r,l] = a[l,r].

Однако давайте разобъём подсчёт. Идея такая — мы перебираем только x, а минимальное расстояние по второй половине мы уже преподсчитали. Итого: a[l,r] = min(a[l,x] + precomputed[x,r]). Осталось, подсчитать precomputed. Понятно, что precomputed[x,r] = min(dist[x,y] + a[y,r]). Осталось заметить, что для того чтобы подсчитать precomputed для данного слоя, всё что нам надо это константные длины и значения a из предыдущего слоя. То есть вычисления precomputed выполняем между слоями, и это занимает O(2^2K * 2^K), зато теперь и главное вычисление имеет такую же ассимптотику. Ответ на задачу: минимальное значение a из последнего слоя. Итого: O(2^3K), и то это довольно грубая оценка сверху (0.09 с в худшем).

→ Ответить

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

← Rev. 2 →

Поскольку, был интерес, мой код к MARS (в первом edit).

→ Ответить

MinakoKojima

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

How to solve problem F ... >_<

→ Ответить

MinakoKojima

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

How to solve problem F >_< ..

→ Ответить

accidentallygivenfuck

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

Does anybody know why don't they display results immediately ? Can't wait for results ! :(

→ Ответить

Pancake

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

Your personal results are up right after the contest ends. Full results are posted in a week or so ( accoring to the organizers , this is an 'appeal period' , some contestants may complain about testcases {not meeting problem's constraints} , the grading process .. etc )

→ Ответить

Anton_Lunyov

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

50-80-50-120-140-160

Так и не понимаю условие C. Они что должны парами ходить? Как они это проверяют? Почему этого в условии нет.

→ Ответить

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

Да, по одному билету можно двоих провести, если один заберет билет другого в зале.

→ Ответить

Calvinxiao

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

1 — easy, 2 — sort then easy, 3 — all tickets to girl one then easy, 4 — binary search, 5 — math, how to solve? 6 — thinking...

→ Ответить

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

5 — one can observe that for any number smaller than k! the number in the second iteration will be smaller or equal to k. so all you have to do is finding out, which of the numbers have 2 as smallest "not divisor" which one has 3 and so an, up to 21 i think .

→ Ответить

bjin

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

I believe it's LCM of first k integers, instead of k!

→ Ответить

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

but when you have a number n smaller than k!, than there is one number between 1,2,3,4,5,..,k that does not divide n, so one of the smallest should be between 1 to k.

→ Ответить

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

oh ok, if it is divisible by n, it is also divisible by 2*n and so on, so lcm should be right.

→ Ответить

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

how do you want to solve 4 with binary search?

→ Ответить

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

never mind, i remembered the problem differently...

→ Ответить

bjin

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

6 — trivial divide and conquer works, when merging two 2^k groups into a 2^k + 1 group, you need to multiply three 2^k × 2^k matrix, use ordinary O(n³) algorithm, then whole algorithm works in O(n³) either

→ Ответить

mmaxio

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

Can anyone add this contest to the gym, please?

→ Ответить