hagu's blog

SSU Online Judge Problem : 284 (Grammer)

By hagu, 10 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it 
      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

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      see this link for BigInt tools

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      thanks mnbvmar and Elk-Cloner. :)

      → Reply