Project Euler #158: Exploring strings

Sort by

recency

|

5 Discussions

|

  • + 0 comments

    We can solve this problem by finding the recurrence relation. Let A(n,m) be the number of ways in the string with length n for which exactly m characters come after theit neighbour to the left. We can call them ascents. We can construct such string either by placing a new character to string with length n - 1 and m - 1 ascents or placing a new character to the string n-1 with m ascents. In the first case we have string with m segments were characters are decreasing from left to right and we can put a new character in all n positions except for position 0 and and m-1 positions between ascending characters that is n-m positions. In the seconds case we have string with m+1 decreasing segment and we can put character at the begining of each segment that is we have m+1 choices. So A(n,m) = (n-m)*A(n-1,m-1) + (m+1)*A(n-1,m). A(n,0) = 1 for all n and A(n,n) = 0 for all n. The rest is trivial as we can use memoization to solve all test cases.

  • + 0 comments

    For N = 700 and m = 0, 1, .. 699 I get following sum:

    First digits: 24852827549363778103818000360884855688859274799663035....

    last digits: 08433505760735219696180850962689869949710826332645746831356075750752869976605336293599548108511464727114964064660520016562607136532939010163985742438455249882955899640271685505419053449214593163977703007368323931572476417580582804451662627264391735394040958486127161392677991

  • + 2 comments

    Wow, those are some big numbers! My very wimpy C++ BigNumber class times out for test cases with alphabets of size around 500.

    For example, answer for

    370 1

    113

    is the number (more than 750 digits)

    1129486192863670815372730620783152644645169 1442473318546501048909340350384155216314327 4388928275082280890440415255439241910001546 2010749396855372214202134439383005223993275 8536596323384816629416049833306137266457487 4322049800510021109373025249471015248831329 7130400883899674846529159641866613001987231 7911193788754442584927477720429127563216884 6008787920431360644080198580955955254473662 7756954418383722891987501053820677434636345 5978890805684775481410610470681630942556410 6409125700551210297628302316146986808029677 2380837979049654271185843505158957683435991 5743631040336861132082488759019517356369043 6639985261394938004139680810790315701841724 9032123262350144516972365274229892284882967 6141813989374499877422091577973968474227765

    01855821264609860903760

  • + 1 comment

    what does lexographic mean

  • + 1 comment

    Doesn't the output value reach way beyond 2^64 ? It doesn't say I need to output modulo 1000000007 so I'm confused.

No more comments