ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1769. Old Ural Legend

Posted by Anton 27 Jan 2012 12:28
I'm laughing now ....
I've spent about 3 hours for this problem.
First off, I used Z-function and I tried to treat problem as a string problem. I generated new string and tried to find it. If there is no, that's the answer.
It became not so slow as can seems to be. But TLE#6 got me!
Then I tried to store positions for each digit(0-9) and than tried to search target number using binary search for every digit. It works, but not good enough to pass test#6.
Then I decided to use the straight approach using bool exists[1000000] that indicates whether n is substring. It approach can be done since total length is 10^5, so 10^6 is free for sure.

Since we know several approaches sometimes we use more complex first :)
Re: finally
Posted by inatial_D 2 Apr 2013 19:42
Re: finally
Posted by Амир Меннибаев 21 Mar 2017 23:04
good idea!