[Community Puzzle] Length of Syracuse Conjecture Sequence

Puzzles
#1

https://www.codingame.com/training/medium/length-of-syracuse-conjecture-sequence

Send your feedback or ask for help here!

Created by @Silmaen,validated by @bbb000bbbyyy,@JBM and @Jamproject.
If you have any issues, feel free to ping them.

#2

Hi @Silmaen, @JBM, @Jamproject, @bbb000bbbyyy
Would you know why I pass all test cases but not the validators? Really weird, I have nothing hard coded…
Is it a Long/Int loss of precision thing?
Thanks

#3

Hi,
hard to tell without your code. But you might be on the right track because the “You can assume that no operation overflows a 32-bit integer” is misleading, it’s actually 32-bit unsigned integer. And so if you are for example coding in java, the Integer is not enough as it is a signed integer.

#4

If I share you my code in private, would you be able to tell :stuck_out_tongue:? I’m using Scala, types are the same as in Java but I already tried moving to Long and it doesn’t work?

#5

Actually 32-bit signed integers should be enough to prevent from overflows in all tests & validators (the maximum sequence value to compute overall is ~1.5e9).

#6

which validator you don’t pass? the last one?
a 32bit integer is enough to pass all the tests.

it could be because of a timeout (the last validator is a ‘big’ one if you don’t use memoisation)

#7

I already use memoisation, and I pass all test cases. However, I don’t pass validators 1, 3 and 4…

Basically what I do is either I take the first tournament and I have r-1 consecutive days left but I have the reward or I don’t and I still have r consecutive days left. If r <= 0 then I just move to the next. Hope this is not too much details.

Am I missing something?

#8

Sure, since I am above level 20, I can retrieve the validators files and run your code to see what’s wrong.

#9

What? Are you talking about The Grand Festival puzzle?

#10

Thanks I sent it to you via private message. Let me know :wink: Thanks

#11

Oooohhhh yes sorry :stuck_out_tongue:

For this one I simply did it straight forward (1 + solveProblem(n-1)) with a little bit of memoïzation. Then a loop to iterate over all n to fetch its Syracuse sequence length.

#12

Hey @bbb000bbbyyy any news on that? Thanks :wink: !

#13

Well damn, I replied 4 days ago but I guess there was a problem.
Anyway, yes I know where the issue is in your code. You need to make sure that it returns the “lowest integer that leads to the longest cycle-length”.

#14

Thanks that solved my issue :wink:

#15

Hello, my code passes all the tests in the IDE of CodinGame but not when I submit the answer. Tests 1,2 and 4 fail. Have you ever encountered this type of problem ? :thinking:

#16

I finally found it. Pay attention to the condition in your if when searching for the maximum

#17

My Java solution runs without any memoization at all. Shouldn’t the inputs be big enough to force you to use it? Isn’t that kind of the whole point of the puzzle?

#18

Same for me, no memoization in java, but everything just works.

#19

My groovy code is only working on tests 1 and 2, the big ones cannot succeed due to timeout.

I do use static class, recursivity, and also memoisation. But all of this are too slow.

Is there another way to solve it, using a little bit of logarithms or another shortcut ?

#20

I had the same problem. Here are two ways to solve the puzzle:

With recursivity and memoisation

(in C++ at least:)

  • Problem if you use a map for memoisation: It takes time to store values into a map and look them up, hence the timeout issue.

  • Problem if you use an array for memoisation: the biggest value we come across while computing is 1570824736, so you would need an array of size 1570824737 for memoisation…

Working solution: use an array for numbers up to 100000, and a map for numbers bigger than that.

With not (recursivity or memoisation)

This might be too big of a spoiler.

Spoil me anyway

The real time eater is recursivity, so just loop and count. It is so fast you can get rid of memoisation.

Cheers.