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

TCO 2013 Algorithm Round 1C
Автор HolyInq, 11 лет назад, По-русски

Последний шанс для тех, кто ещё не прошёл в Round 2, но планирует это сделать.
Регистрация открывается в 18:00 Москвы, начало в 21:10.
Дальше проходит 600 человек.

Всем удачи!

  • Проголосовать: нравится
  • +42
  • Проголосовать: не нравится

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

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

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится -15 Проголосовать: не нравится

    Попробуем доказать от противного.

    Пусть текущая сумма больше 2000000000 (переполнение). Тогда сумма на предыдущем шаге бинпоиска должна быть максимум в два раза меньше (поскольку делится, в худшем случае, на число 2x+1), то есть, больше миллиарда, а это бинпоиск отсечёт.

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

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

      Вполне себе рейтинговый.

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

      а если предыдущая сумма больше миллиарда больше и 2 миллиардов?

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Ну, в самом начале бинпоиска переполнения у нас нет (максимальная сумма равна 2 * 47), а выше показано, что оно не может за один ход возникнуть из суммы, меньшей миллиарда. Возможно, ошибся где-то в доказательстве, но у меня только что с интом зашло.

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

        это смотря какие границы у Вашего бинпоиска, если идти с середины (5e8) и спускаться до нуля, то это как уже сказано ранее невозможно, ибо сумма возрастает каждый раз не более чем вдвое. значит когда-то переполнится(станет больше k)

        → Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я завалил свой бинпоиск и еще парочку решений в комнате, но все бинпоиск пишут по разному. Некоторые решения даже прошли сис. тесты с переполнением.

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

у меня в комнате у чувака упало решение потому что он границы бинпоиска сделал [-1,1000000000], а не [0,1000000000] и считал в интах. считал бы в лонгах или сделал нормальные границы, тогда бы прошло

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

How to solve the 1000 point problem ...

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

    I'd like to know too...

    It's easy to calculate the expectancy of attacked cells if you only place only one knight. If I'm not mistaken, it's (8*N^2 — sigma(1,8) f(i)) / N^2, where f(i) is the amount of cells from which the knight cannot make move i (the knight can move in 8 different ways). For each of the 8 types of movement, you define the rectangular region from which the knight cannot make that move (it's always rectangular, covers either the whole horizontal range or the whole vertical range, and starts from one corner of the board, depending on the type of move), then f(i) is the area of that rectangle.

    But when the second knight comes into the game, it changes completely and I don't know how to solve it...

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

    First, let's solve problem "what is probability of cell (i; j) to be under attack? (call it p_i_j)". Calculate number of different cells (x, y), that if there is a knight on cell (x, y), cell (i, j) is under attack. Let it be A. Than p_i_j = (total — (n^2 — A) * (n^2 — A — 1) / 2) / total, where total = n^2 * (n^2 — 1) / 2 — number of different arrangements of knights.

    Now, we just need to calculate sum of p_i_j over all n^2 cells. We know that p_i_j depends only on A (number of different...). So let's divide all cells in groups with same value of A. Let's call value i interesting if exist such j that A[i][j] != A[i-1][j]. We can find that only {0, a, b, n — a, n — b, n} (may be +-1 in some of them) can be interesting. So if we divide our board into count_interesting^2 parts, for every part we could calculate p_i_j in some cell and multiply it by number of cells in part.

    → Ответить