Single Round Match 530

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

А когда будет правильно отображаться оставшееся до соревнования время?

Или оно только у меня неправильно показывается?

→ Ответить

aropan

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

А какой у вас таймзон и какой вы выбираете?

→ Ответить

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

Таймзон московский, выбираю его.

Сейчас 1:50.

SRM в 6:00 - это показывает правильно. Но говорит что до него осталось 3 часа, а не 4.

→ Ответить

aropan

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

← Rev. 2 →

а в настройках оси таймзон +4 указан?

UPD. У мну под семеркой для Москвы +3 выбирается.

→ Ответить

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

Юзайте update_tz

→ Ответить

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

+10

Ой, как внезапно. Спасибо.

→ Ответить

de_troit

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

-9

У меня в арену не заходит, у всех так ?

→ Ответить

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

-15

Любопытно, а зачем так упорно минусуют пост?

→ Ответить

ilona

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

-11

А теперь и Вас заминусовали)

→ Ответить

gen

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

+18

Негодуют, что теперь не выспятся (:

→ Ответить

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

+11

Если вы крепко спите, не ставьте будильник (звонящий 30 секунд с интервалом в 10 минут) на 5:44 - может быть очень обидно потом.

→ Ответить

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

Мне кажется, что условие 250-ки настолько ужасное, что даже нецензурно выразиться можно с трудом, чтобы передать все эмоции.

→ Ответить

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

500 - тоже не конфетка

→ Ответить

SkyHawk

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

← Rev. 2 →

Не хочу больше вылетать во второй дивизион. Тут контест длится 30 минут =( И всё равно наверняка на какой-нибудь задаче слажал.

UPD. Зато challenge тут весёлый :) Пары секунд до первого места не хватило.

→ Ответить

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

Судя по тому, что там много народу уже сдали все, сегодня задачи простые.

Иногда бывают значительно сложнее.

→ Ответить

SkyHawk

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

Знаю, но всё же... Судя по некоторому беспорядку в таблице, в первом дивизионе интересные задачи.

→ Ответить

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

Первая простая, а потом слишком резкий скачок до 500-ки.

→ Ответить

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

ну так почти всегда

→ Ответить

kit1980

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

← Rev. 2 →

С div2 1000 что-то не так - сейчас ни одного прошедшего решения.

→ Ответить

mongolrgata

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

← Rev. 2 →

ОЛОЛО. Я вот не могу понять почему в тесте

{
"NYYYY",
"NNYYY",
"NNNYY",
"NNNNY",
"NNNNN"}

ответ 7, а не 8

0-4
0-1-4
0-2-4
0-3-4
0-1-2-4
0-1-3-4
0-2-3-4
0-1-2-3-4

UDP: если я правильно понял условие, то надо найти число путей из вершины 0 в вершину N-1

→ Ответить

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

Если речь про div1-500, то все ребра последнего пути содержатся в предыдущих.

→ Ответить

mongolrgata

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

← Rev. 2 →

Нет, задачи в этот раз разные

UPD: ссылка на условие

→ Ответить

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

Ну на прочтение по диагонали вроде та же задача.

→ Ответить

VArtem

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

If i >= j then choices[i][j] will be 'N'.

А в остальном - та же задача.

→ Ответить

mongolrgata

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

← Rev. 2 →

Да, согласен. Почти похожи. Но Рейму мне больше нравится))

→ Ответить

SkyHawk

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

Ну например если он будет идти в этом порядке, то все переходы в последнем пути он уже когда-то выбирал, поэтому он не будет корректным

→ Ответить

kleninz

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

← Rev. 2 →

"For each pair of different stages i, j the game contains at most one such choice."

Это значит, что ребро в каждой игре используется не более одного раза, но в первом сэмпле 2 раза встречается 0 -> 1. Поправьте меня.

UPD.

Почему нет челленжа?

→ Ответить

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

Как быстро вбивать тест, являющийся ветором?

→ Ответить

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

+10

Вбиваешь кучу строк через запятую, потом жмешь ++

→ Ответить

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

Спасибо, пригодится! А то который раунд очевидный хак не успеваю сделать)

→ Ответить

yarrr

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

Традиционный вопрос относительно DIV1-500.

→ Ответить

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

+17

На Codeforces давно пора сделать кнопку "Как решать 500-ку?"

→ Ответить

VArtem

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

← Rev. 4 →

nevermind, о чем-то не том подумал.

UPD: Решение в 1 правке кривое, а то, что я написал на раунде, к моему удивлению прошло.

Я делал так: поддерживаем множество in, означающее, что из этих вершин достижима n-1 и они достижимы из 0. Далее на каждом шаге бфсом находим кратчайший путь из множества in+{0} в множество in+{n-1}, удаляем ребра на этом пути и обновляем множество in.

→ Ответить

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

1) Удалим нафиг все вершины, из которых нельзя добраться до стока или в которые нельзя добраться до из истока.

2) Утверждается что после этого ответ E - V + 2.

3) Почему это так. В наборе есть поднабор покрывающий все вершины. Пусть он состоит из cnt путей. Тогда общее количество путей не не более E - (V - cnt - 2) + cnt = E - V + 2. Значит от параметра cnt ничего не зависит и ответ не более E-V+2. Ну очевидно, что какой-то набор покрывающий все вершины существует.

→ Ответить

AlexanderBolshakov

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

У меня решение такое: Флойдом проверил достижимость стока из каждой вершины, после этого запустил ДФС из истока (вершины, из которых сток недостижим, не ДФСил). Если пришел в сток или в уже посещенную вершину - answer++. Вот код.

→ Ответить

Furko

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

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

→ Ответить

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

с любым натуральным? я искал с наименьшим натуральным.

интересно услышать доказательство, что можно любой такой путь брать)

→ Ответить

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

Любой - не правда. см. первый семпл.

→ Ответить

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

ок, значит Furko имел ввиду "наименьшим натуральным"

→ Ответить

Furko

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

Да, с наименьшим натуральным.

→ Ответить

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

← Rev. 3 →

мда, я редкостный идиот

я думал, что в 500ке в каждом пути не должны повторяться ребра (семпл в обратном меня не убедил :) )

придумал решение, написал, сдал... и понял, что этого не учитываю.

огорчился, как пофиксить, не придумал, пошел делать тест. и... 2 неудачных челленджа! тогда я решил перечитать условие...

надеюсь, медиум пройдет :D

UPD мда, 250 упала, 500 прошла.ну ладно, чо, первый медиум есть)

→ Ответить

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

После того, как ты понял, что слажал 500-ку, ты надеешься, что она пройдет? Оо

→ Ответить

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

да!

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

→ Ответить

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

Ага, прошла.

→ Ответить

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

← Rev. 2 →

а на чем могла 250 упасть? О_о

UPD мда, у меня баг на баге был

→ Ответить

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

Вот мне тоже интересно. Два челенджа которые я сделал - на совсем лаже у людей.

→ Ответить

kleninz

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

Вероятно, из-за того, что cutter не влезает в cake.

→ Ответить

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

А на что это влияет? На тесте где у меня упало все вполне прилично.

→ Ответить

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

Не, там по условию, что cutter всегда влезает в cake.

→ Ответить

KADR

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

Там не обязательно есть дырка в левом верхнем углу вырезалки. У меня на этом упала.

→ Ответить

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

У меня это учитывается, или пытается по крайней мере - упало.

→ Ответить

Kenny_HORROR

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

Я троих почелленджил на том, что они не учитывали, что в cutter '.' может быть не в [0][0], а значит, ему надо некоторое смещение.

→ Ответить

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

А с учетом этого есть идеи?

→ Ответить

Kenny_HORROR

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

← Rev. 2 →

Ну кроме этого больше ошибок, которые могут быть общими, я не придумал.

→ Ответить

Jokser

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

А зачем вообще нужно было обращать внимание есть ли в [0][0] у cutterа '.' или нет?

→ Ответить

Kenny_HORROR

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

Многие как и я искали верхнее левое вхождение '.', т.к. по ней можно однозначно определить где должен находиться cutter, если расстановка валидна и т.д.. Но много кто не учитывал, что сам cutter должен иметь смещение.

→ Ответить

bytybai

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

Подскажите, пожалуйста, вот если тест

cake="XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"

а cutter = "." почему ответ YES?

→ Ответить

AlexanderBolshakov

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

Потому что мы ничего не вырезали.

→ Ответить

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

дак ни одного наложения cutter-а делать не надо

→ Ответить

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

Гарантируется, что в cake есть ',' же

→ Ответить

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

← Rev. 3 →

ну как я делал:

Берем в первой строке самый левый, его совмещаем в первой строке с самым левым из куттера, продолжаем

UPD: нашел багу, вместо y<0 - x<0

и на этом -120 :(

→ Ответить

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

Отличная бага в 250. Оказывается -2 иногда больше 3. А кто знает как заставить арену компилировать с -Wall?

→ Ответить

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

Насколько я помню в арене варнингов много каких-то пишется. Там точно -Wall нет?

→ Ответить

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

Ну comparation between signed and unsigned integer не кидает.

→ Ответить

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

А зачем именно в арене? Ты совсем не компилируешь локально?

→ Ответить