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

SSU Online Judge Problem : 284 (Grammer)

Автор hagu, 10 лет назад, По-английски

I was trying to solve this problem but i am getting WA on test 19. I'm not able to figure out the bug in my code.

Problem Link :- http://acm.sgu.ru/problem.php?contest=0&problem=284

I have used the approach explained here :- http://e-maxx.ru/algo/prefix_function translated version here :- http://translate.yandex.net/tr-url/ru-en.en/e-maxx.ru/algo/prefix_function

I have first computed the pie function(KMP) of the pattern to search. Then i have used the approach explained in the given link. (The Build Machine prefix function part).

This is my code :- http://ideone.com/NcBqKX

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

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

I haven't inspected your code but I have a guess. The result doesn't have to fit inside int (and long long, either). I think a big integer implementation is required here.

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

    can you explain to me your computation analysis of why it won't fit inside long long range. If you can, provide me the link to your big integer implementation.

    P.S -> I tried using unsigned long long too , still the same result.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится 
      30
a
16 a a a a a a a a a a a a a a a a
16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
16 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
16 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
...
16 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29

      Then 1 consists of 16 characters, 2 is made of 162 characters and so on; finally, 30 is made of 1630 = 2120 characters and the same number of occursnces, which is larger than 264. Of course, I think the result can still be slightly bigger.

      I don't have any big-int implementation on my hard drive, I'm sorry :P

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

      see this link for BigInt tools

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

      thanks mnbvmar and Elk-Cloner. :)

      → Ответить