12040 - Again Lucky Numbers

All about problems in Volume 120. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
brainless_the_swiss
New poster
Posts: 5
Joined: Sat Feb 16, 2013 2:19 am

12040 - Again Lucky Numbers

Post by brainless_the_swiss » Tue Feb 26, 2013 1:37 am

Dear all,

It would be great if someone helps me with this challenge :
http://uva.onlinejudge.org/index.php?op ... oblem=3191

When the number M cannot "overlap" itself, it is not a big deal to compute it recursively.
By "overlapping itself", here is an example :

If M=1212, then the number "121212" contains M both at its beginning and at its end. If M=12312, then "12312312" is another string containing twice M overlapping itself. The overlap is the substring "12" in the middle. M=123 is a case where M cannot overlap itself.

The tricky cases are when M can overlap itself.

I have looked for similar situations on other topics, like 10722 - Super lucky numbers and 10712 - Count the numbers:
http://online-judge.uva.es/board/viewto ... ky+numbers

Any little hint will allow me to move forward.

Thanks in advance for your help !

evaaaaaaaan
New poster
Posts: 1
Joined: Tue Aug 12, 2014 4:51 pm

Re: 12040 - Again lucky numbers

Post by evaaaaaaaan » Tue Aug 12, 2014 4:55 pm

brainless_the_swiss wrote:Dear all,

It would be great if someone helps me with this challenge :
http://uva.onlinejudge.org/index.php?op ... oblem=3191

When the number M cannot "overlap" itself, it is not a big deal to compute it recursively.
By "overlapping itself", here is an example :

If M=1212, then the number "121212" contains M both at its beginning and at its end. If M=12312, then "12312312" is another string containing twice M overlapping itself. The overlap is the substring "12" in the middle. M=123 is a case where M cannot overlap itself.

The tricky cases are when M can overlap itself.

I have looked for similar situations on other topics, like 10722 - Super lucky numbers and 10712 - Count the numbers:
http://online-judge.uva.es/board/viewto ... ky+numbers

Any little hint will allow me to move forward.

Thanks in advance for your help !
this problem can be solved using dp + some prefix matching technique

Post Reply

Return to “Volume 120 (12000-12099)”