The River II


#25

Anyone else having an issue with optimization in python3?
Passes all test cases quickly with no errors and no hard-coding, yet only showing 91% completion... :frowning:
I'm failing the "yes please" test.


#26

Keep in mind: you don't need to find the earliest starting point of the meeting rivers, you just need to check if a river exists. So consider starting with r1 and then try to find one single smaller number that leads to r1 and you are done...


#27

I am literally way to ashamed to admit how much time i had to spend on this one..
If you are stuck like i was just PLEASE read the description from the beginning to the END and realize how simple the solution might be. My final code takes like four lines and runs in seconds. Cheers :slight_smile:


#28

Trying brute force seems, effective for small cases, but kind of stupid…
Before coming here I had figure out that you juste need to go one step backwards to be able to give an answer ( you just have to say YES or NO , no how many river meet this number)
But for the life of me I’m not smart enough in Math to figure out how the hell you do that, if that’s even possible…


#29

Of course you are.
Given K, there’s another river meeting K, if for [1…K-1] you can find X such as (X + sum digits of X) == K.
Now, you can find a lower bound for the numbers you need to check.


#30

Hello guys,

I am stuck on this one for too long…I need some help.
The ‘BIG’ and the ‘Random Large’ tests fail…

“Given K, there’s another river meeting K, if for [1…K-1] you can find X such as (X + sum digits of X) == K.
Now, you can find a lower bound for the numbers you need to check.”

This is what I do. Also, I found a lower bound, but it is not enough to pass the 2 tests: [1…K - (Kn+1)].

I had another idea : during the loop, store all the numbers of every river in a tab, and remove the duplicates. if K is in the tab, I do not need to get the river and I can go to the next iteration.
But this takes more time than my first solution :rofl:

So I am stuck, any (other) clue would be nice. Thank you in advance guys :grinning:


#31

Naive method i used:
the maximum number of steps any river advances is (length_of_number)*9. obviously. e.g. 99 will advance 18 steps, whereas 100 will advance only to 101.
so the biggest step any number below your checking number is:
amount_of_checks: ((first_digit-1)+(length_of_number-1))*9

now you only have to check this amount of numbers.

iterate over each of them, and see whether the very next step leads them to your number. if so, you’re done. if not, next.

HTH


#32

Thank you guys, these clues helped me a lot :smiley:


#33

Hi, thanks to the comment about log10 I was able to validate the exercice with 100%, before I was using the same logic but didn’t really know where to stop to still have a high probability of a valid answer
Does anybody have a source/explaination about why the step between 2 numbers in the river has to be lower than 9 * log10(input) ?


#34

What’s the step length for 15?
What’s the step length for 999?
What’s the step length for 12361?

What is the step length for abcdefgh, where [ah] are single digits?
How many digits are this?
What is the log(10) of abcdefgh?

HTH :slight_smile: