Enchom's blog

Doubt about CodeChef solution
By Enchom, history, 8 years ago, In English

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?

  • Vote: I like it
  • +230
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +140 Vote: I do not like it

Just another shitty problem with doubles and discrete answer.

→ Reply
»
8 years ago, # |
  Vote: I like it +137 Vote: I do not like it

Yeah, 100% agree that problem is bullshit. xorfire recently told me about that problem and I got exactly same comment as yours. Very probably no other correct solution different than BigIntegers exists at all.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    Considering the constraints I'm positive that no solution with BigIntegers can fit in the time limit. I suppose the problem is just wrong then.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      Yeah, sure, I didn't mean it to be solution which can get AC, I meant "only solution that prints correct answer" :).

      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +100 Vote: I do not like it

I waited about 2 weeks to see the brilliant solution and was very upset to see such a stupid one...They could've let the intial task for sqrt trick(even though it wasn't hard), but at least it was solvable, but nooo why would they do that?:))

→ Reply