The_Orion's blog

Help needed in a SPOJ problem .
By The_Orion, history, 4 years ago, In English

Sorry for disturbing you .

I was trying to solve this SPOJ problem , but failed .

Any suggestion ? Hint ? Tutorial ? Or solution ?

Waiting for positive reply .

My main code

Thanks in advance .

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

The maximum possible answer is around $$$10^5$$$ (or less), just bruteforce over all numbers and check if they occurs should work.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried this in the range of 1 to 100000. For all the numbers i converted it to a string using to_strint(val) function. Than i checked all sub string of the length of current value. But TLE.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it -8 Vote: I do not like it

      You can't check the occurrences naively. The complexity will be $$$O(10^5 \cdot n)$$$. You can either precalculate all numbers under $$$10^5$$$ that occurs or build a suffix-automaton on the string.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't know about suffix-automaton. Can you help with a sample code or tutorial link ?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          No need to use that. The easiest way to get AC is:

          code
          → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You shouldn't try every possible number. Think what to do with the maximum possible length of the answer.

      → Reply