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

problem DAGCNT2 from SPOJ
Автор wtiger9999, 13 лет назад, По-английски
https://www.spoj.pl/problems/DAGCNT2


Please anyone give me some hint about the proper algorithm to solve it. My solution run in O(n^2) (and got TLE) @@.
  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
http://en.wikipedia.org/wiki/Topological_sorting
→ Ответить
  • »
    »
    13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    ok, but how to get answer without counting the same vertex twice?

    BTW: your comment in russian interface, so and my too

    → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да, я как всегда условие криво почитал.

      А запихивал кто-то? Ничего умнее n*n+n*m/32 не придумывается. Локально за секунду работает, но это же spoj :/
      → Ответить
      • »
        »
        »
        »
        13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Там вроде быстрее n*n+n*m/64 и нет ничего. Но непонятно как пихать.

        → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится -16 Проголосовать: не нравится
      написано же, граф ацикличный - а значит 2 раза 1 вершину не посчитаем
      → Ответить
      • »
        »
        »
        »
        13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится -16 Проголосовать: не нравится

        мда.. уже через 10 мин. -1
        ладно, просто делаем массив булей v. когда встречаем вершину проверяем значение v[i] и если оказалось, что false - меняем на true и прибавляем вес вершины к сумме.


        +: а тут то за что?

        → Ответить
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        А как вы предполагаете тест вида?
        3 вершины, 3 ребра
        Рёбра:
        1 -> 2
        2 -> 3
        1 -> 3
        → Ответить
»
13 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Запихнул: http://pastie.org/3244846

Но это жесть, конечно.
Решение, по идее, очевидное: запускаем DFS'ы из вершин со степенью 0, для каждой вершины получаем маски достижимости других вершин из детей.
Ответ считаем тупо за квадрат.

Хаки:
1) Читаем fread'ом, пишем fwrite'ом.
2) Если мы находимся в вершине u и вершина v уже помечена как достижимая, забиваем на обновление масок.
3) Подсчитываем суммы для полных масок (32 единички). Тогда при подсчёте ответа, рассматривая некую маску, мы можем её обработать за O(1), если она пустая или полная.
→ Ответить
  • »
    »
    13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    У меня более крутое решение в плане асимптотики, у тебя присутствует явный квадрат n, у меня n * m / 32 + n / 32 (3 * 2 ^11 + n * 3) ~ n * m / 32 + n^2/10. Вот решение. 9-ое место в списке лучших решений. Но что бы я делал без идеи битового сжатия.

    Второе что помогло, так это подсмотренное у тебя разделение подсчета битовых масок, а уже после этого подсчет собственно сумм. Посчитаем битовые маски. Подсчет сумм можно огранизовать за n / K * (2^K + n), разбив все маски на группы по K бит (у меня было 11, и каждые 32 бита обрабатывались как 11 + 11 + 10). Бежим в цикле по группам. Для каждой из 2^11 масок посчитаем соответствующую сумму, запишем в массив sum[1 << K]. Затем пройдемся по всем вершинам, вычленим нужные K бит, и добавим к ответу для этой вершины sum[bit_mask].

    PS: читаю scanf, вывожу printf, время работы 18.19 секунды.

    UPD: твой инпут/аутпут ускоряет до 14.00 секунд.

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

      ЗЫЗЫ:

      а чем так не правильно читать инпут? WA получает

      1. char buf[1 << 26];
      2. char *tbuf = 0;
      3.  
      4. int readInt()
      5. {
      6.     while (tbuf == 0)
      7.     {
      8.         gets(buf);
      9.         tbuf = strtok(buf, " ");
      10.     }
      11.     int res = atoi(tbuf);
      12.     tbuf = strtok(0, " ");
      13.     return res;
      14. }
      → Ответить
»
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Предлагаю свою версию: делаем сжатие компонент сильной связности. После этого - топсорт и динамика, начиная от "тупиков".

UPD: уже понял ошибку. Думаю, как исправить.

→ Ответить