Обсуждение задач 2 и 3 раундов SnarkNews winter series-2011

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

Да, правильно. А в чем проблема?

→ Ответить

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

WA 7.

Я не понимаю, в чем может быть проблема.

→ Ответить

yarrr

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

А покажи код, пожалуйста.

→ Ответить

http://pastebin.com/nuZ7DdSY

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

как-то глупо блин:(

→ Ответить

aropan

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

между 3 и 4 у тебя будет расстояние 1, а надо если не ошибаюсь $\text{[math]}$ ...

→ Ответить

dalex

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

Может, ошибка возникает, если инпут из одного символа? Потому что негде там набажить, неправильно посчитанные расстояния между кнопками проверяются претестами

→ Ответить

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

Я, чтобы не рисковать, написал d[k][j] - ответ, если нажали К клавиш, один наш палец на клавише с К-той цифрой, а второй на клавише j. Но должно было пройти и по 3 параметрам, вроде бы, ни с МЛом, ни с ТЛом проблем нету.

→ Ответить

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

Ну да, я так написал тоже.

→ Ответить

PavelKunyavskiy

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

У тебя как-то странно считается расстояние. По моему например для (3,4) будет не правильно. Получится $\text{[math]}$

→ Ответить

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

Спасибо.

Извините за беспокойство.

→ Ответить

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

Как решать D третьего раунда?

→ Ответить

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

В задаче D проходит жадность: сначала мы на каждый корабль должны посадить одного хорошего человека, потом нужно попытаться распределить всех плохих людей так, чтобы ни на один корабль никого досаживать не пришлось. Потом, если есть такая позиция, куда можно посадить плохого, что придется посадить только еще одного хорошего, то тогда помещаем его туда. А после этого постоянно будем сажать плохих на крайний левый корабль. Как-то так :-)
Ну и естественно нужно учесть случай, когда есть только один корабль

→ Ответить

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

Ну или можно забить константы с помощью какой-то многомерной динамики - к примеру F(номер корабля, количество уже посаженых хороших, количество хороших в последнем корабле, количество плохих в предпоследнем корабле, количество плохих в последнем корабле) -> максимальное общее число плохих. Есть и более оптимальные ДП, которые не требуют много памяти и забивать константы не надо, но эта проста как пень.

→ Ответить

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

← Rev. 2 →

Что значит "забить константы"?

upd: А, прекальк чтоль.

→ Ответить

Zhukov_Dmitry

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

← Rev. 2 →

Можно было простой рекурсивный перебор написать.

Перебираем, сколько сажаем "плохих" на текущий корабль, вычисляем минимум, сколько надо посадить "хороших" на предыдущий. И ещё минимум для последнего.

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

Он вроде даже по времени проходил.

→ Ответить

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

Эх, и без забивания констант эта динамика прошла.

→ Ответить

vilcheuski

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

← Rev. 2 →

Как решалась Е третьего раунда?

→ Ответить

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

Лично я был очень сильно расстроен, что по задаче E проходит n*m... я даже не пытался такого писать :(

→ Ответить

vsb

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

Time Limit 7 sec

n * m = 500 000 000

за 1 секунду бывает пара сотен миллионов срабатывает. А тут их аж 7. Попробовать нужно было, вдруг повезет? :)

→ Ответить

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

Ну может быть и надо было. Просто я обычно не люблю писать что-то совсем уж близкое к миллиарду :) и я всё оставшееся время контеста пытался придумать что-то, что работает быстрее :)

→ Ответить

vsb

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

Ну никто не любит. Наверно из-за того что в большинстве случаев TL не больше 2 сек. И все забывают на него посмотреть...

Или ты знал, что ТЛ 7 секунд и все равно думал что в лоб не пройдет?

→ Ответить

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

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

→ Ответить

goo.gl_SsAhv

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

А как решать за n *m ? я в дорешке сдал m * log(n)^2

→ Ответить

Zhukov_Dmitry

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

← Rev. 2 →

+15

Для каждого запроса ищем максимум за O(n) (перебираем все окна, проверяем координаты и смотрим время его отрисовки поверх остальных).

А как решать за O(m * log² n)?

→ Ответить

goo.gl_SsAhv

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

← Rev. 4 →

в моей терминологии n - число запросов и m - число окон.

Разобъём по координате X все поле на 2^14 полосок, построим по этому делу дерево отрезков. Каждому интервалу соответствует другое дерево отрезков (теперь по Y), включающее все точки-запросы лежащие на полосках соотвутствующих этому интервалу (максимум n штук <= 10^4). каждая точка-запрос попадёт максимум в 14 деревьев, поэтому памяти у нас n * log(n). ах да, в вершине второго дерева отрезков лежат пары (time, window_id). Чтобы узнать цвет ячейки мы вибираем максимум из всех интервалов, которые её содержат O(TreeSize), таким образом чтобы покрасить какую-либо ячеку в нужный цвет нам достаточно присвоить этот цвет любому интервалу содержащему её.

UPD: последнее утверждение верно для деревьев по Y, и для дерева по X, ну и понятно почему оценка O(Log(n)^2) - сначала для дерева по X получаем Log(n) интервалов, и там на каждом дереве запрос будет стоить Log(n)

UPD2: код

→ Ответить

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

А как решается F с третьего раунда? Вроде что-то простое должно быть, но никак придумать не могу

→ Ответить

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

+10

Там запас топлива не нужен больше 200. Итого 1000 * 200 состояний, 1000 * 1000 * 200 ребер - зашло Дейкстра.

Альтернативно можно сделать 100 * 100 * 200 вершин (для каждой вообще клетки) и только же * 4 ребер - просто ход в сторону или +1 топлива, и тоже пустить Дейкстру.

→ Ответить

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

Спасибо... и правда просто. Меня почему сбило с толку, что топлива до 1000 и я подумал, что будет многовато состояний :)

→ Ответить

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

+10

Даже до 100000. Меня тоже сбило, на контесте я не сдал:)

→ Ответить

slavik

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

Странно что Дейкстра зашла. Вроде бы и ребер 2 * 10 ^ 8, и вершин 2 * 10 ^ 5. Если писать сетом, то получаем O(m * log(n)), если как обычно то O(n ^ 2). Видимо, стоило писать сетом, ведь константа невелика(обновляем значения не так часто). Или ты использовал еще какие-то соображения?

→ Ответить

hydrastuff

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

Вершин там 200*100*100 = 2*10⁶, из каждой вершины 5 ребер, итого 10⁷ ребер, я использовал priority_queue, прошло с запасом.

→ Ответить