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

Editorial: Codeforces Beta Round #83
Автор Atef, 13 лет назад, перевод, По-русски

Время-палиндром

Автор: Atef

В этой задаче необходимо найти следующий палиндром на цифровых часах. В задача точнось времени ограничивается минутами, и в сутках всего 24 * 60 минут. Соответственно, достаточно проверить все минуты, начиная с введённого времени, до тех пор, пока не будет обнаружен палиндром. Если палиндром не был обнаружен до конца дня, 23: 59, ответом будет 00: 00.

Типы данных

Автор: Atef

Будем считать пару типов данных (a, b), где a < b, "плохой" тогда и только тогда, когда существует числоx такое что x помещается в a бит, но x * x не помещается в b бит. Для решения задачи поможет следующее наблюдение. Лучшим кандидатом на число x будет максимальное число, которое помещается в a bits --- то есть x = 2a - 1. Таким образом, для каждого ai достаточно проверить что минимальное из aj > ai содержит достаточно бит, чтобы хранить x * x = (2a - 1) * (2a - 1), для которого требуется максимум 2 * a бит. Для того, чтобы находить следующее минимальное aj > ai числа на входе имеет смысл предварительно отсортировать.

Водоснабжение

Автор: Atef

В задача задаётся граф корпусов общежития и направленных труб между ними. По условию задачи этот граф будет содержать одну или блее цепочек труб. Необходимо найти начало и конец каждой цепочки, принимая во внимания, что цепочка может состоять из более чем одной трубы.

Также для каждой цепочки необходимо найти наиболее слабое звено. Чтобы сделать это, следует пройти по каждой цепочке, например, запуская поиск в глубину из каждого корпуса не имеющего входящих труб. Эти корпуса будут началами цепочек, и, по ходу поиска в глубину, нужно также помнить минимальный диаметр среди встреченных труб. После того, как все цепочки найдены, перед выводом их следует отсортировать по номеру корпуса, откуда выходит данная цепочка.


Автор: Atef

Рассмотрим два множества возможных команд: команды, где Мистер Вафа является единственным студентом со своего факультета и команты, где хотя бы один студент с факультета Мистера Вафы, кроме самого Мистера Вафы, является членом команды. Эти множества не пересекаются. Если вычислить количество команд в первом множестве --- A, и количество команд во втором множестве --- B, то ответм будет B / (A + B).

Количество команд в первом множестве A = . Нужно вычесть единицу так как Мистер Вафа точно является членом команды, а оставшиеся (n - 1) игроков будут выбраны из оставшихся студентов.

Теперь найдем количество команд, где кроме Мистера Вафы в команде есть ещё k студентов с его факультета. Это будет . По аналогии с количеством команд в первом множестве, нужно выбрать (n - (k + 1)) студентов с других факультетов и ни один из них не должен быть с факультета Мистера Вафы. Таким образом, общее количество команд, где у Мистера Вафы будет хотя бы один партнёр по команде с его факультета, равно .

Выше приведено математическое решение. Оно допускает множество алгоритмических реализаций.

Автор: Atef

С первого взгляда ограничение на n в 1018 кажется огромным. Однако, в сочетании с тем, что ответ следует вывести по модулю 12345 оно должно не пугать вас, а наоборот, помогать думать в правильном направлении: как решить задачу методом динамического программирования.

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

Предположим, что n равно 11, и у нас есть решение для первых 10 преступлений. Понятно. что просто знать ответ --- количество способов, которыми можно совершить первые 10 преступлений и остаться безнаказанным --- недостаточно для того, чтобы решить задачу для n = 11. Дополнительной информацией, которую необходимо передать из подзадачи в подзадачу является следующее множество чисел: количества способов, которыми можно совершить первые n преступлений, имея после этого кратности преступлений по всем типам d1, d2, ...d26 соответственно. Так как произведение кратностей во входном файле не превосходит 123 размер множества всех возможных комбинаций кратностей тоже ограничен сверху ста двадцатью тремя.

Чтобы лучше понять эту идею, рассмотрим первый тест из условия. В нём есть два ограничения, A с кратностью 1 и B с кратностью 2. Остаток по преступлениям типа A всегда ноль. Остаток по преступлениям типа B может быть либо нулём либо единицей. Таким образом, решая подзадачу для первых n2 <  = n преступлений, достаточно помнить два числа: "количество способов, которыми можно совершить n2 преступлений и быть невиновным по всем статьям", и "количество способов, которыми можно совершить n2 преступлений из которых есть одно ' нескомпенсированное' преступление типа B".

Ключевым шагом к решению теперь является наблюдение, что каждый переход от моножества решений для первых k преступлений ко множеству решений для первых (k + 1) преступлений можно задать матрицей перехода. Эта матрица будет одинаковой на каждом шагу. После построения этой матрицы задача можеть быть решена за логарифм от n = 1018 используя идею matrix exponentiation: на некоторых шагах вместо того, чтобы вычислять Ai + 1 = Ai· A0 можо вычислить A2i = Ai· Ai.
до
Последним подводным камнем в этой задача являются множественные кратности. Если бы у каждого преступления была максимум одна кратность, достаточно было бы хранить в множестве состояний текущую кратность по данному преступлению. Более того, после возведения матрицы в степень единственным допустимым состояниям было бы состояние, где все кратности равны нулю.

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


Размещение

Автор: Atef


В задаче требуется найти лексикографически n-ю сортировку, удовлетворяющую данным ограничениям.

Подвох, который смутим многих участников, а заодно и некоторых тестеров и авторов опорных решений, заключается в том, что вместо интуитивного ограничения в формате position[a[i]] < position[b[i]] ограничения в этой задача имеют вид  element at position[a[i]] < element at position[b[i]].

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

Перед тем как научиться считать количество возможных решений, давайте поймём как это поможет нас решить задачу. Для начала сделаем следующее наюлюдение: если общее количество решений меньше, чем y - 2000, то ответом будет "The times have changed". А когда эта проверка на существование решения произведена, найти само решение можно, например, подбирая его слева направо.

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

А если зафиксировать первый элемент в единицу не дало нам достаточно перестановок, тогда следует уменьшить y на количество перестановок, где первым элементом является единица, и продолжить поиск в предположении, что первым элементов является двойка. Вычесть количество перестаноков, где первым эдементов является единица, необходим, потому что, согласно условию задачи. мы пропускаем те порядки размещения, которые использовались в 2001, 2002 и т.д. годах.

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

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

Для данного префикса P необходимо подсчитать количество способов, которыми можно разместить оставшиеся (n-m) элементов не нарушив ни одного ограничения.

Предположим, что мы будем генерировать все возможные перестановки. Однако, вместо стандартного подхода "попробуем поставить на позицию i любой свободный элемент и решим задачу для оставшихся позиций начиная с (i+1)-й", используем несколько иной подход: "для данного способа разместить первые i элементов, не считая элементов, которые образуют префикс, возьмём (i+1)-й элемент и проверим все позиции, куда его можно было бы поместить". При этом будем идти по элементам в возрастающем порядке, пропуская, конечно, элементы, которые являются частью уже известного префикса.

Несложно видеть, что такой алгоритм генерации всех перестановок работает, но за время O((n - m)!), что конечно, недопустимо. Соответственно, нужно каким-то образом уменьшить пространство состояний, чтобы свернуть этот алгоритм генерации перестановок в динамику.

Необходимое нам наблюдение такое: состояние частично решённой задачи однозначно задаётся битовой маской использованых позиций. С первого взгляда может показаться, что этой информации недостаточно, так как на будущие ограничения влияет не только маска занятых позиций, но и то, в каком порядке расположены элементы на этих позициях. Однако, это оказывается несущественным, если заполнение перестановки элементами производится в порядке возрастания свободных элементов. Действительно, пусть для некоторой маски занятых позиций мы хотим поставить элемент e в свободную позицию i. Чтобы проверить допустимо ли такое положение для элемента e, будем проверять те пары входных ограничений, которые касаются позиции i. Если ограничение касается позиции i и другой позиции, которая ещё свободна, то оно не нарушается элементом e. Если же ограничение накладывается на позицию e и другую позицию, в которой уже есть элемент, то верно одно из двух: либо другая позиция принадлежит префиксу, и тогда мы точно знаем, какой на ней стоит элемент, либо же нам заведомо известно, что элемент на этой позиции меньше, чем e, потому как наша динамика расставляет элементы начиная с меньших.


Дартс

Автор: Dima

Перед тем, как перейти к алгоритму, отметим, что ответом на задачу будет отношение суммарной площади всех прямоугольников к площади объединения всех прямоугольников.

Чтобы понять это, сделаем следующее наблюдение. В первую очередь понятно, что если все прямоугольники совпадают, то ответом будет их количество. Теперь временно забудем про то, что фигуры должны быть прямоугольниками, предположим, что форма фигур на входе может быть любой, и покажем как построить пример, где площать объединения была бы s и ожидаемое среднее количество проткнутых фигур было бы e. Понятно, что такой пример можно построить начав с произвольного контура объединения, ограничевающего площать s, путём добавления дополнительных фигур, лежащих внутри этого контура. Суммарно необходимо будет добавить фигур на общую площать t = s· (e - 1), но конкретное число не важно. Важно то, что взаимное расположение этих добавленных фигур не имеет значения, и, соответственно, ответ на исходную задачу зависит только от площади контура объединения всех фигур и суммарной площади всех фигур.

Вернёмся теперь к прямоугольникам. Найти суммарную площадь всех прямоугольников легко. Сложно найти площадь объединения всех прямоугольников быстрее, чем за O(n3). Обратите внимание, что объединение может состоять из множества несвязных компонент, компоненты не обязаны быть выпуклыми, они могут содержать дырки, и вообще, в общем случае описать объединение всех входных прямоугольников не очень просто. К счастью, в этой задаче нас интересует только площать этого объединения.

Одно из решений, которое относительно несложно закодировать, заключается в следующем. Будем считать площадь объединения методом трапеций. Отметим сразу, что для вычисления площади методом трапеций достаточно знать все ориентированные сегменты контура, а их порядок совершенно не важен. Таким образом достаточно "просто" найти все ориентированные сегменты, которые образуют контур объединения, причём вертикальные сегменты могут быть сразу исключены из рассмотрения.

Например, если для какого-то теста объединение представляет собой фигуру с дыркой, то внешний контур должен превратиться во множество сегментов с положительной общей площадью, а внутренний контур --- во множество сегментов с отрицательной общей площадью. Иными словами, внешний контур следует обойти по часовой стрелке, а внутренний --- против часовой стрелки.

Для того, чтобы найти все такие сегменты, рассмотрим все различные невертикальные прямые, на которых лежат стороны входных квадратов. Их не больше, чем 4n. Понятно, что каждый сегмент объединения лежит на одной из этих прямых, соответственно, достаточно проверить отдельно каждую из прямых, но только по одному разу.

Правила, по которым можно выделить "положительные" и "отрицательные" сегменты на каждой прямой достаточно просты:

1) Если сегмент этой прямой (x1, y1) - (x2, y2) является частью границы одного из входных прямоугольников, тогда помечаем этот сегмент как "положительный" или "отрицательный" в зависимости от того, лежит ли данный прямоугольник выше или ниже прямой.

2) Если на сегменте этой прямой (x1, y1) - (x2, y2) накладываются границы двух входных прямоугольников, лежащих по разные стороны от прямой, то этот сегмент не може являться частью контура.

3) Если сегмент (x1, y1) - (x2, y2) лежит полностью внутри какого-то из входных прямоугольников, то он не может являться частью контура.

Соответственно, построить все сегмента контура объединения можно с помощью примерно следующего кода:

для каждой уникальной не-вертикальной прямой
  создаём массив маркеров. маркер хранит x-координату и одно из четырёх событий: { начало/конец положительного сегмента, начало/конец отрицательного сегмента }
   проходим во всем входным прямоугольникам
    если одна из сторон этого прямоугольника принадлежит рассматриваемой прямой
       добавляем два маркера: начало и конец сегмента. знак сегмента определяется положением прямоугольника относительно  рассматриваемой прямой.
    иначе если это прямоугольник пересекается с прямой
      находим левую и правую точки пересечения, и помечаем сегмент между ними четырьмя маркерами, покрывая его и положительным и отрицательным сегментом.
  сортируем массив маркеров по их x-координате
  идём по маркерам слева направо. если про какой-то сегмент известно, что он должен быть положительным, и не должен быть отрицательным, выводим его как положительный сегмент финального контура. если известно, что он должен быть отрицательным и не должен быть положительным, выводим его как отрицательный сегмент финального контура.

После этого можно было бы выписать множество финальных контуров используя, например, поиск в глубину, но для метода трапеций это не требуется. Достаточно просуммировать (x2 - x1)· (y1 + y2) / 2  для каждого сегмента.

Вышеописанное решение работает за O(n2· logn) : для каждой из O(n) прямых мы рассматриваем O(n) пересечений, и их сортировка занимает O(n· logn) на каждую прямую.
Разбор задач Codeforces Beta Round 83 (Div. 2 Only)
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Is not there O(1) solution for "Palindromic Times"?

We can just check (MN - minutes in input, HR - hours in input):

 if (reverse(MINUTES) >= HR) {
ans = (string)((HR + 1) % 24) + ":" + reverse((string)((HR + 1) % 24));
} else {
ans = (string)(HR) + ":" + reverse((string)(HR));
}
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    What about input 06:50 for example? First condition is not passed, because 5 < 6, so you will print 06:60, which isn't correct.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
" If there exists an integer x, such that x fits in some type i (in ai bits) and x· x does not fit in some other type j (in aj bits) where ai < aj, then Tuftuf will stop using Gava."
This is a statement of your problem B. Here you use a word some which change the meaning of the statement what you want to mean. This statement mean if there are any aj  which fullfil the condition ai < aj, tutuf will continue using Gava. The word some totally change the statement here and I got wrong over and over only for that reason. Is not it a mistake?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I don't understand why not anyone reply on my post. What's the problem with administrator? I wanna some reply here about my question. How can I get answer of my question can anyone tell me that?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      I can't understand your question. What is the problem with the word "some"? I can't see any.
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        If you use some here, it does not mean that every aj which are ai<aj, but at least one. That change the whole meaning. Do you understand what I want to say? Thanks for your reply.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Problem statement used word "some". And it meant "some". It didn't mean "every". So I don't understand your problem.
          → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
for Problem 2 after sorting  if it is sufficient to chech aj=2*ai for smallest j>i

then plz help me the 4th test case at which my code failed
52

474 24 24 954 9 234 474 114 24 114 234 24 114 114 234 9 9 24 9 54 234 54 9 954 474 9 54 54 54 234 9 114 24 54 114 954 954 474 24 54 54 234 234 474 474 24 114 9 954 954 954 474




in the above case 9 is there but no 18......24 is there but no 48...hence the output should be "YES"
but the correct answer for the case is "NO"

plz explain why is so ??
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    When asking about your code, you can link to it, it's a bad idea to post example cases.
    Also, you can try checking other people's solutions.

    In that example there are only 7 data types, they are:
    9, 24, 54, 114, 234, 474, 954

    It doesn't matter you don't have an 18bit datatype, you have to check that for any two of those types the condition holds, since 9bits*9bits fits in 24bits and 24bits*24bits fit in 54bits and so on, then Tuftuf is not going to stop using Gava 


    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Problem: Basketball Team
I used the following idea: let x = all possible teams= and y = all teams without any member from Wafa's major=. So answer is 1.0-y / x. What's wrong in this? I got wa on test 21. submission[635824].
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Problem Basketball Team:
I used the following idea: let x=all possible teams= and let y=all possible teams without any member from Wafa's major=. So answer is 1.0-y / x.

Is anything wrong in the reasoning? I got stuck on test 21. submission[635824]. Code is here.
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    The idea is correct, but implementation is wrong. The value of x can go upto C(99999,99) which is about 500 digits long and double does not have such high precision.

    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
public static void main(String args[])
{
int i,j,hh,mm,h1,m1,h2,m2;
String str;
try{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
str=br.readLine();
hh=new Integer(str.substring(0,str.indexOf(":"))).intValue();
mm=new Integer(str.substring(str.indexOf(":")+1,str.length())).intValue();
for(i=hh;i<24;i++)
{
for(j=mm+1;j<60;j++)
{
h1=i/10;h2=i%10;m1=j/10;m2=j%10;
if(h1==m2&&h2==m1)
{
if(i<=9)
System.out.println("0"+i+":"+j);
else
System.out.println(i+":"+j);
return;
}
}
mm=0;
}
System.out.println("00:00");
}
catch(Exception e){e.printStackTrace();}
}
This is my solution to palindromic time problem.
Can anyone tell me the bug cause this problem was failing in pretest 3 which I don't know why?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    You force the number of minutes to always be greater than the number of minutes that you start out with. Let's say the time is "22:45". The next palindromic time should be "23:32", but your loop never lets the number of minutes be 32 because you force the number of minutes to be greater than 45.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
About the problem Basketball Team, the solution was probably not very accurate. When i used __float128 or long double to calculate my results, i got WA on some pretests, but when i converted it to double, my solution was accepted. May be you should have considered decreasing the required accuracy if double could not give the required precision.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Is the formula for problem D is right ?
A = C ( sum(s[i] i!=h) - 1, n - 1), I think it should be A = C ( sum[i] i!= h), n - 1). Why we must subtract 1 ?
And F(k) = ... sum(s[i]  i!=h) - (k + 1), why we must subtract (k + 1) ?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо за разбор) Разберите задачу E у Div 2 :) интересно как ее решать  
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
In the problem C in Div 1: the editorial says: " Now to complete the solution we need to be able to compute the number of permutations which satisfy two restrictions: the input constraints and the added permutationhasprefixP constraint. This problem is solved using DP with n· 2n states, which fits the time and memory limit.". But it seems not to be easy for me to implement the DP. Can anyone explain me more clearly? Thanks.
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I haven't implemented yet, but what I undertood is dp[x][y] is the number of years having x as first element, and using elements of mask y. 
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Actually I implemented it using 2n states instead of n * 2n. A state dp[mask] represents the number of permutations you can get with some free positions (free positions are bits in mask equal to 0). The transitions work as follow:

    If there are k bits equal to 1 in mask, it means that you have fixed elements 1..k. Now you are going to fix element k + 1. Then, try all possible free positions, and check for each one the constraints: if you are checking constraints for position j, all position j' such as there exists an edge j' -> j, should have been fixed before (if exists an position j' such as there exists an edge j' -> j and j' hasn't been fixed before, then it will be fixed with an element k' > k + 1, so element at position j' will be less senior than element at position j, and dp[mask] will be 0). If you can put element k + 1 at position j then go for the next state: mask | (1 << j). Finally dp[mask] will be the sum of all possible transitions.

    F(mask) = {
      if not free position, then
        return 1
      if dp[mask] has been calculated before, then
        return dp[mask]
      dp[mask] = 0
      i = number of occupied positions + 1
      for j in 1..n then
        if j is a free position and no constraint is violated after putting element i at position j, then
          dp[mask] += F(mask | (1 << j)).
      return dp[mask]
    }

    Now the tricky part is printing the answer.
    For each position j in 1..n, try to fix an element i in 1..n at position j, if it hasn't been used in a previous position and the number of permutations with some elements fixed, is greater or equal than y. If such number of permutations (temp) is less than y, then y <- y - temp, and continue with element i + 1. The procedure looks as follow:

    print(y) {
      // Not enough permutations.
      y = y - 2001 + 1
      if (F(0) < y) then
        print "The times have changed"
      
      for j in 1..n then
        for i in 1..n then
          if i hasn't been used in a previous position then
            v[i] = j // put i at position j
            F(0, v) is greater or equal than y, then:
              go for position j + 1, the answer include i at position j
            else:
              y = y - F(0, v) // Discard all permutations with i at position j
              continue with element i + 1
      use v to find the answer and print it.
    }

    Of course you have to modify the initial DP algorithm to incorporate elements fixed at certain positions. If element i hasn't been fixed at some position then iterate all over positions 1..n, otherwise use the position where i has been fixed.

    Hope it helps.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Indeed. Hope it's correct now.

FTR, my solution is not using this formula, but a simple DP approach with memoization.

long double solve(int i, int n, int min_k = 0) {
  if (i >= M) {
    return (n == 0);
  } else {
    long double& save = cache[i][n][min_k];
    bool& save_valid = cache_valid[i][n][min_k];
    if (!save_valid) {
      save_valid = true;
      for (size_t k = min_k; k <= n && k <= S[i]; ++k) {
        save += solve(i + 1, n - k) * C[S[i]][k];
      }
    }
    return save;
  }
}

...

  swap(S[H-1], S[0]);
  --S[0];
  const long double total = solve(0, N - 1);
  if (total == 0) {
    cout << -1 << endl;
  } else {
    const long double valid = solve(0, N - 1, 1);
    cout << valid / total << endl;
  }
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
"The very first observation is: if the total number of possible solutions is greater than y - 2000, then the answer is "The times have changed"."

I think you meant ".. number of possible solutions is NOT greater .."
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А можно поподробнее об вычислении количества перестановок за n· 2n, мне только понятно как это делается за n2· 2n
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Чтобы сделать на n· 2n, нужно уметь делать проверку "можно ли поставить элемент e на позицию i" за O(1).

    Заметим, что элементов всего n, и позиций всего n. То есть пар "элемент-позиция" всего n2, для маленького n.

    Соответственно, можно сделать "битовую маску" размера n2, которая задаёт все "ещё допустимые" пары "элемент-позиция". А ещё можно, заранее, до запуска всех динамик, пройтись по всем n2 парам "элемент-позиция", и для каждой из них в этой "битовой маске" размера n2 отметить, какие пары становятся недопустимыми после добавления данной пары.

    Дальше в самой функции динамики (если она, конечно, "ленивая динамика" через рекурсию) можно передать в следующий вызов рекурсивной функции "битовую маску" размера n2, которая получается путём AND-а предыдущей "битовой маски" и "битовой маски" заготовленной заранее для данной пары "элемент-позиция".

    Таким образом проверка допустимости данной пары "элемент-позиция" свелась к одной операции, а собственно добавление этой пары и обновления списка ограничений --- к одному AND-у на числе размером n2 бит.

    Конечно, битовой маски размера n2 = 256 пока не бывает, но она помещается в четыре uint64. :)

    А если хочется лучше, то можно построить такие маски не для всех пар "элемент-позиция", а только для последних четырёх позиций (то есть не n2 = 256 бит а n· 4 = 64). Это ускорит только самые глубокие вызовы ленивой динамики, но их будет больше всего! И тогда хотя бы части задачи у нас будет "честная" O(n· 2(n - m)) динамика.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      зачем так сложно....
      вот у нас есть динамика dp[1<<n]  - где i бит означает 1 если позиция не занята и 0 если занята... запомним для каждой позиции маску на какие позиции нельзя ставить элемент больше чем на этой... ну и тогда проверка будет просто сделать and масок текущей позиции и маски нашего состояния... и всё в инты нормально влезает...
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Thanks for editorial :)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А что означает буква C в этой формуле:  ?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кто-то может все-таки объяснить как вычислить количество перестановок в задаче "Размещение" (словами, а не кодом)? Я никак не могу понять, как это делать, а с кодов решивших мне тоже ничего не понятно.
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 11   Проголосовать: нравится 0 Проголосовать: не нравится

    вот здесь и здесь объясняется для гамильтонова пути, а подсчет перестановок, это тоже самое. А в случае ограничений, нужно только понять какие ограничения это будут на графе. 
    Вот вижу много контестантов решали, не за n22n по времени, а за n2n
    С єтим и самому интересно. Но пока никто не ответил.

    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Действительно, странный разбор этой задачи; описана только стандартная часть, а нетривиальная опущена.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Действительно некрасиво получилось. Исправляемся.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Any one could teach me how to solve Problem 4 by Matrix Power ...
(I always can't get acorss the editorial >_< ) ...
→ Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain how to calculate the transition matrix for Div1 D(Crime Management),and also what should the dp state be?

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Thanks. good editorial

→ Ответить