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

IFMO Training 05 - September 28, 2011
Автор aropan, 13 лет назад, По-русски

Предлагаю делать отдельные ветки обсуждений для каждой тренировки...


Problems of September 28, 2011 Contest.
Team standings of today's contest.
Personal standings of today's contest.
  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Будет ли дорешивание или кто знает где можно дорешать "C. Calendar"?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    вроде никогда дорешивания не бывает, можно найти тесты на этом же сайте...
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      в тех годах было дорешивание....странно, что сейчас не запускают=(
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А где тесты? Я их не смог найти
      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Эти задачи можно сдать на acm.msu.ru, но для этого придется запустить виртуальный контест.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      как вариант, но хотелось тогда уже в архиве задач где нить...
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
кто как Б решал? и как вообще ее правильно надо было решать?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    ну мое решение использует 500500*1000/32*4+1000*4 байта - что около 64 мегабайта памяти и имеет сложность O(N), т.е. просто добавляем новую коробку, причем упорядочиваем размеры d1<=d2<=d3, потом считаем кол-во бит во всей таблице.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Почему в G не проходит решение - найти все точки сочленения и вывести те, которые встречается на кратчайшем пути из S в E ?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Потому что путь должен быть кратчайшим по количеству точек сочленения на нем, а не по количеству ребер в исходном графе.
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Хотя, на самом деле, все простые пути из S в E проходят через одни и те же точки сочленения... странно. Может, лишние посчитал (те, у которых с обеих сторон путь в одной компоненте)?

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да нет все правильно. Я тоже так думал. Но сейчас придумал тест:
      1 2
      2 3
      3 4
      4 5
      2 6
      6 5
      6 7

      Находим путь из 1 в 5. В итоге пройдем лишнюю точку - 6. Для графа она точка сочленения, а для нашего пути никакой роли не играет.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А реально в J пропихнуть БФС ?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Там легче жадно идти в сторону финиша (корректность легко доказывается).
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Я под конец пытался сдать такое решение:
      Сначала идем по диагоналям, пока не сравняемся по улицам или авеню. А дальше увеличиваем/уменьшаем оставшуюся координату. Там 2 случая, либо 600 футов проходим, либо 200 в зависимости от четности суммы координат. Но WA. В чем ошибка?

      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А ещё можно сделать дп навроде черепашки, где если есть ребро, то переход стоит 200; иначе - 600.
        → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        не совсем верно в конце.
        там или 2 * k * 200 футов или (2 * k +/- 1) * 200 футов в зависимости от четности, где k - сколько кварталов нужно пройти по прямой до финиша.

        → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Скорее всего нет из-за ограничения по памяти. Так как хочется похранить в очереди похранить координаты и ответ. А это 5000^3 > размерности uint. 5000^2 интов - это 100 метров...а нам нужно еще больше=)
    Можно использовать половину очереди....т.е. зациклить по модулю 5000^2 / 2. Тогда возможно хватит памяти и вроде такого количества вершин должно хватать....но тогда нужно пользоваться или 10 или 12 байтным типом для хранения вершин в очереди.

    Там можно вывести простую формулу для ответа - а идея, как уже упоминалась выше, это сначала по диагонали подойти к финишу, чтоб первая или вторая координаты сравнялись, а потом дойти по прямой подобием зиг-зага.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я сдал BFSом. Для проверки посещена ли вершина или нет храним массив битсетов + ясно, что в очереди в среднем будет порядка O(500*4) эл-ов.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Наверно все же 5000*4 тогда вершин? странно, нам 30000 не хватило для размера очереди.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Да.
          Ну может 30К и не хватает. В любом случае ясно, что будет < 1млн :)
          Я юзал std::queue<State>, где State хранит i,j и d - расстояние до клетки i,j.
          → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    скорей всего да, но я думаю надо будет извращаться, чтобы в память влезть... у меня решение такое:
    - в любом случаем можно двигаться по диагонали за 2 хода в любом направлении, т.е. мы можем стать с конечной точкой на одной линии (по горизонтали или вертикали).
    - затем проверяем можем ли мы сделать ход в направлении выхода.
    - потом формулой считаем сколько осталось.

    → Ответить