Sort 10 Discussions, By:
Please Login in order to post a comment
One of test cases contains this term:
In my solution, bolded parentheses evaluate to zero (-1/-1+1*1*-1 = 1 - 1 = 0), and then further evaluation fails because of division by zero error (-1*1/0*2).
Can someone explain the logic behind this, because it is written that there will be no divisions by zero in any test cases?
EDIT: When I redefined the modular inverse of zero to be zero, which is mathematically incorrect, it passed all the test cases. I think that four of the test cases are bad.
Yes, you're totally right, thanks for your observation. I guess the author was so hell-bent on using Euler's formula that he probably computed every modular inverse by raising to p - 2 power mindlessly and totally forgot that it only holds when gcd(a, p) = 1. I used EEA instead. After seeing your post I added assertion against non-invertible numbers as on Wiki page and it became obvious what was going on.
p - 2
gcd(a, p) = 1
Sorry for my perhaps naive question.
When I compute 10^(p-2) using fast modular exponentiation as suggested by the challenge author I do not get the expected result of 700000005. My code for fast modular exponentiation is below (no spoiler here since it is a word for word rendering of the challenge author's own suggestion as he himself posted):
let rec modexp x y =
if y=0. then 1.
let z=modexp x (floor (y/.2.)) in
if (mod_float y 2. =0.) then mod_p (z ** 2.)
else mod_p (x *. (z** 2.))
let mod_p a =
mod_float ((mod_float a p) +. p) p
let p = 10. ** 9. +. 7.
Indeed, the reported result for modexp 10. (p-.2.) is 485926138.
Can someone point me in the right direction? Thank you!
I've thought about it for an hour, and still don't understand this step. I've read the wikipedia page on Fermat's little theorem, and am still very confused as to what/why/how to get this step:
Can you please explain further? Is "p" (10^9 + 7)? in that case, does 10^(p-2) turn into 10^(1000000007-2)? if so... that number is SO large!
This should help you : x^(a+b) = (x^a)*(x^b)
I think this problem might not be tagged as Expert
AC using SLR(1) and LL(1) Parsing
I can not understand example 3. Can anyone clarify why (-2) / 10 is converted to -2 * 10^(p-2)?
(-2) / 10
-2 * 10^(p-2)
Fermat's little theorem says:
a^(p-1) == 1 (mod p)
Multiplying both sides by a^(-1)
a^(p-2) == a^(-1) (mod p)
Oh, thank you. I am ashamed by forgetting this theorem. So, am I supposed to convert division to multiplication when evaluating expressions? Currently my code evaluates (-2)/10 to be equal to 0 by rounding integers.
But if I use exponentiation almost all of the test cases fail because of the time limit (I use Scala). So, is it really necessary to use exponentiation instead of division to solve this problem?
Seems you are not using fast exponentiation. Check following properties
1 , b == 0
a^b = (a^(b/2))^2 , even b
(a^((b-1)/2))^2 * a , odd b
Here complexity will be O(log b) instead of O(b).
Edit: Check this wiki page.
Yes, I use standard library function - BigInt.pow. I've looked it up in Scala's sources and found that it uses lots of optimizations including those you mentioned.
You don't need big integer libraries for any of the challenges in FP subdomain. Simple optimization in 32/64 bit integers should work.
I'm finding myself a little confused by the grammar. According to it, "-+-3" is a valid expression; what should that mean?
For now, I'm going to assume the grammar allows at most one unary operator for each factor:
Term ::= Factor0 [*/] Term
Factor0 ::= [+-] Factor | Factor
Factor ::= Number | '(' Expression ')'
(Naming is not my strong point)
Correct! Each factor is accompanied by at most one unary operator.
Thanks for pointing. Now added to constraints.
There is a very strange step in input/output 3. The transformation 4/((-2)/10) -> 40/(-2) does not make sense. It is arithmetically correct, but A) the reduction of double division into multiplication is not specified anywhere B) this does not match the behavior of most sane integer arithmetic evaluators (they evaluate strictly in parenthetical order) C) this requires either really weird AST manipulation or the use of non-standard number types to implement.
I suggest either A) clarifying the description to state that we're doing what essentially amounts to either doing arithmetic with rational number types or B) changing evaluation behavior to something reasonable (like what's used in basically every single programming language). In the standard case, it would be 4/((-2)/10) -> 4/(-1) -> -4.
Also, the description says to print the output mod 1,000,000,007 (p), not constrain all intermediate steps to p, so it is not at all clear that we are supposed to substitute division with multiplicative inversion mod p.
Hi @ wyager, yes you are right. Explanation was wrong there. I had corrected it. Please check.
Thanks for pointing that out.
This question's explanation still does not indicate that we should constrain each intermediate step to p...
I hate to boast, but this should not be classified as 'Expert' : solved in 2 hours flat :D
I have a question and a remark after completing this challenge :p
The question is Why no one uses a Lex/Yacc equivalent? This seems by far the most straightforward way to do this. And I see no interest in creating a custom lexer/parser :O
As for the remark, I think this challenge is not worth 100 points. It took 15 minutes to produce the 70 lines of code that solve it. I'd rather say 10 points (Yeah I know, I expose myself to some backfiring that way, let's see where the debate goes :-) ) The only difficulty IMHO was calculating the inverse of a number, but the problem statement gives explicitly the solution.
Let's see... Instead of writing code yourself you used code who was written by somebody else. That probably means you didn't solved the problem.
No more comments