Hello everybody,
As most of you know recently the June long challenge in CodeChef finished and I want to bring attention to one specific problem — Chef and cities. Roughly the part of the solution that is difficult to come up with can be summarised as:
"You have an array of N integers and you have two types of queries — update some integer or ask about the first digit of the product of all numbers." (The original problem has more details but they are solved trivially)
I was eager to see some real solution (unlike cheats with double values) so I checked the author solution and to my surprise it did something very simple — it calculated the log of the product and used it to find the first digit.
Now this is okay in theory, it is okay in mathematics — but my first thought was 'what about precision?'. Surely if you have some tricky number then you might get some precision error and since you're looking simply for the first digit — there's not relative error allowed. So I quickly came up with the following test:
9
3 3 11 41 101 271 3541 9091 27961
1
2 1
You can confirm yourself that :
3*3*11*41*101*271*3541*9091*27961 = 99999999999999999999
And unless I've missed something crucial it seems that it's a valid test. However all three solutions provided by the author in his analysis ('Setter', 'Tester', 'Editorialist') would print 1 as a first digit, just as my cheaty solution with double values does.
This test is incredibly small given the constraints. You have integers with values up to 109 and up to 105 of them. This allows the product to contain thousands and thousands of digits, making me seriously doubt any solution based on floating point numbers.
I was wondering if a proper solution even exists at all? Am I overlooking some constraint or just missing something or is the author solution plain wrong?
