TopCoder Single Round Match 521

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

Некоторые там динамику по подотрезкам писали :)

→ Ответить

Hohol

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

Я писал. Первая мысль была: черт, если это 250, значит она решается втупую... Пофигу, пусть умные люди пишут простые решения, я же буду писать че умею)

→ Ответить

72VanVector_SevNTU

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

Горе от ума)

→ Ответить

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

← Rev. 2 →

Странно, что мало посдавали 1000.

У меня она тоже, вообще-то упадет, но фиксится вроде одной строчкой.

UPD: гы, прибежела толпа народа, все смотрят, что ж я там такое написал)))

→ Ответить

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

А там есть какое-то очень простое решение? Кстати может кто-то объяснить откуда берутся матрицы размера меньше 256?

→ Ответить

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

Считаем, что следующий ход - открывает новый ряд.

Тогда видов состояний всего 4 - 2 последних слоя полный, предпоследний полный, в последнем 2 рядом или 3, или в предпоследнем 3, на них - 2

→ Ответить

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

Мы же можем иметь три незаконченных ряда одновременно. Я не понимаю как это обработается.

→ Ответить

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

давай отмечать не все моменты времени, а как бы когда мы остановились и собрались открывать новый слой. если у нас три ряда не полных, то новый слой мы открыть не можем=> это не рассматривается. точно также, если сверху 2 не рядом.

→ Ответить

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

Похоже на правду... Я чуть по другому делал - отсекал по моментам когда полностью заполняется слой. В результате получается перемножение матриц 256*256, но в них очень много нулей - поэтому говорим что много что не достижимо и даже не надо это считать. На макстесте в тл укладывается. на 2⁵⁹ - 1 тоже.

→ Ответить

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

Действительно, правда. В практис зашло. Видимо опять придется возвращаться к #define int long long

→ Ответить

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

За такое хочется сильно побить человека, после челенджа по переполнению.

→ Ответить

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

Я знаю. Одна из причин по которой и не пишу.

→ Ответить

udalov

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

Пишется тупое решение, узнаются первые 5 ответов, угадывается последовательность => матрица 2х2 :)

→ Ответить

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

Неужели числа Фибоначчи? :)

→ Ответить

Egor

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

Совсем простое решение - у нас не больше 3 нетривиальных слоев в любой момент (тех, где не все включены или не все выключены). Можно посчитать, что всего 35 валидных "шапок" (битовых масок поставленных кирпичей в этих 3 слоях). Тогда достаточно составить матрицу перехода и возвести ее в степень 4n - вот мое решение

→ Ответить

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

Откуда берется 4*n??? У меня из такого же соображения получилось n. Правда для матрицы непонятно какого размера.

→ Ответить

Egor	13 лет назад, # ^ \| 0 Ну, 4 кирпича на каждом уровне. А матрица перехода - добавление одного кирпича → Ответить

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

Логично. Видимо я это 4 засунул в динамику перед решением...

→ Ответить

subscriber

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

Действительно 1000 оказалась не особо сложной, примерно в 2 раза больше прошедших решений на 1000 чем на 500..
Правильный ход был сразу начинать с 1000, жаль что мне такое не свойственно)

→ Ответить

yahooo

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

мне кажется, это конечно мое личное мнение, но на мой взгляд, это наикоченейш_й раунд

→ Ответить

sdryapko

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

Мне вообще повезло, я зачелленджил чела по 500-ке, который возвращал рандом. :)

→ Ответить

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

← Rev. 2 →

И откуда такие берутся? У меня в комнате по харду человек возвращал n mod 100...7

→ Ответить

BECEJIb4AK_U

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

Товарищи, дайте идею 500 div1.

В 1000 напрашивается динамика, но довольно хитрая, точно не уверен.

→ Ответить

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

+20

Идея такая: для начала поймём, что для каждого хорошего множества существует квадрат какого-нибудь хорошего вида. Например, n для него равно либо nlow/nhigh, либо какой-нибудь разнице координат.
После чего перебираем сторону квадрата. Поймём, что если квадрат для множества есть, то его можно сдвинуть вправо/вниз до тех пор, пока либо у него на верней и левой стороне не окажется по точке, либо он упрётся правой/нижней стороной в какую-нибудь точку, не включая её.
Теперь у нас мало возможных квадратов, проверяем все и складываем ответы (в виде битмасок) в set.

→ Ответить

ifsmirnov

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

Правда ведь, что если добавить для каждой точки восемь соседних, то перебирать нужно только квадраты, которые построены одним из четырех способов по любым двум точкам, включая фиктивные? Ну и длины - это все возможные попарные расстояния + nlow + nhigh.

→ Ответить

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

Хватит даже трёх соседних - слева-сверху.
И, да, в любом случае надо помнить, что надо пытаться вписать каждый из углов квадрата, а не только один.

→ Ответить

ifsmirnov

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

Я вписывал четырьмя способами для девяти точек, но все равно получил WA на последнем претесте. Значит, все же в реализации хрень.

→ Ответить

ifsmirnov

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

Блин. Нецелые точки.

→ Ответить