The_Orion's blog

By The_Orion, history, 3 weeks 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

»
3 weeks 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.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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 ?

        • »
          »
          »
          »
          »
          3 weeks 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
    • »
      »
      »
      3 weeks 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.