[Community Puzzle] Fair Numbering

Puzzles
#1

https://www.codingame.com/training/medium/fair-numbering

Send your feedback or ask for help here!

Created by @java_coffee_cup,validated by @Deltaspace,@Maurice_Moss and @dbdr.
If you have any issues, feel free to ping them.

#2

Hi @java_coffee_cup, thank you for your puzzle. My code passes all the tests in the IDE but fails at validator 2 after submission.

I’ve checked my code thoroughly but cannot find what’s wrong in it. How would you recommend me to process to find out the problem in my code as I can’t see what is in validator 2 ?

#3

Validator 2 is very much alike test case2. Constantly having people pass it so I rule out data is incorrect.
If you wish you can private msg your code to me (specify what language and </> tag the code). I may tell what’s wrong.

#4

The usual approach for this problem has two parts :

  • writing a function that counts digits between given page a and page b
  • the search for the good page (an exhaustive iteration is too long so you have to optimize the search somehow)

I doubt the problem is in the first part cause the testcases feature enough edge cases to test the validity of your formula.
So it’s probably the search.
If you solve all testcases it means your search is fast enough, so the problem might be your halting condition.

2 Likes
#5

I would appreciate, how can I private msg you? My code is in Python, not sure what you mean by </> tag the code.

#6

I have just sent you a private message

1 Like
#7

I have just sent you a private message

How I did it:

image
image769Ă—270 23.6 KB

1 Like
#8

Could i get some help on how to find the number once you get the total? My process always timesout in the bigger ones cuase is not enough optimized and im stucked

#9

My main tip : you may want to look at the log 10 function to count digits in ranges, and find the middle efficiently.

4 Likes
#10

I found a way to get the count of digits in range 1 to N (logn) , and got the total by doing digits(1 to ed) - digits( 1 to (st - 1)). Im not sure if im doing the best way and how to use this way to find the middle

I just completed it nvm, thanks a lot for the help!

#11

Surprisingly the problem was in the function that counts digits between two given pages.

I am coding in Python and math.log(1000,10) appears to be less than 3… But math.log10(1000)=3.

Thanks again @java_coffee_cup for sharing the numbers where my code was failing!

1 Like
#12

Interesting finding. Checked online there are comments like that:

" log10(a) : This function is used to compute the logarithm base 10 of a. Displays more accurate result than log(a,10)."

1 Like
#13

Hi
i’m new in here and i need some help to “adjust” my code to insert in functiunally.
it works in eclispe but i’m not familiar to the way to modify and let it works in the Solution.
may someone can take a look on my code and explain
it would be great
thanks

#14

are you writing in java?

#15

I also had this problem. It turns out I missed the bit of the problem where it says Alice should never write more digits than Bob

#16

some tests of mine are running out of time…
I think that there is not other way than precompute the results…

#17

No puzzle on this site requires precomputing. Alls can be passed in the allotted time, if your code is optimized enough and use the good method.

#18

Hi ,
Can you explain more please?
I’ve only 62 %

#19

Anyone doing it this way is doomed to fail by timeout:

sum = 0
for int i = 1 to n {
String s = string_value(i)
len = string_len(s)
sum = sum + len
}

Using the example for explanation,

Here is the steps

For the example of range 1…200,
We could divide it into ranges 1…9, 10…99, 100…200
Digit count of each number in each range: 1, 2, 3
Total digit count (1…200) = 1x9 + 2x90 + 3x101 = 492

Half of it is 246

The first two ranges account for 9 + 180 = 189 digits.
Alice will do the first two ranges, and will have to write 57 extra digits in range 3.
57/3 = 19
Alice will write 19 pages in range3 (100…118) to finish her part.

Answer is 118.

Computers can finish the above calculation a thousand times in a flash.

1 Like
#20

I think there is a mistake in the checker “Typical cases” in
Found: 501759
Expected: 509259
input data differ by 1 where is such a difference in the answer?
4-1000000
5-1000000
6-1000000
9-1000000
10-1000000
11-1000000