Hello Codeforces community!
I am glad to announce that HackerRank 101 Hack 45th edition will be held on 17th Jan 2017 at 16:30 UTC. You can sign up for the contest here. Though what's priceless is solving interesting problems and the thrill of competition, prizes make the competition fierce. Top 10 performers will get a HackerRank T-shirt.
Problems have been set by me, and tested by wanbo and niyaznigmatul.
The contest will consist of 5 problems with variable scoring distribution. We have tried our best to prepare a nice problem set. Hopefully everyone will enjoy. Also, you'll be able to enjoy the detailed editorials written by the setter.
Good luck and have fun!
Nice problemset! How to solve E?
binary search on answer , to check for answer (say 'X') , eliminate all those points where dist(a[i] , b[i]) < X , Now for each point you get 2 ranges from where points can be picked , so use persistent segtree.
Here is my brute force solution:
It passed all tests except the 20th,and it turned out to be very strong,i submitted ~10,2017-01-18 times and always WA 20.
I challenge everybody to hack this solution without random tests :).
Problem D , can someone explain what is meant by field Zp . And what is the polynomial R(x) . I tried reading the editorial but I couldn't get how the observation works .
It means that the coefficients of our polynomials are always modulo 1e9+7.
R(x) is a polynomial such that R(x)*Q(x)=P(x) (coefficients modulo 1e9+7)
Wasn't the time limit too tight in problem E?
Can someone enlighten me why checking if ba - 1 is a root of P(x) modulo p is a necessary and sufficient condition in D?
If P(x)=R(x)*(ax+b) then (ax+b) is a factor of P(x). Since Zp[x] is a unique factorization domain, ax+b is always a factor of P(x) and hence -b/a is a root of P(x). The observation mentioned in the editorial is based on the fact that Zp[x] is a UFD.
What is a unique factorization domain?
Edit: The explanation on wikipedia suggests that this is something similar to the fundamental theorem of arithmetic? Is so then how do you prove the uniqueness of factorizing polynomials modulo p?
In essence, it is a domain in which every element can be written as a unique product of (prime/irreducible) factors. For example, Z (integers) is a UFD because every number can be written as a unique product of prime powers. In this case, Zp[x] (Polynomials in which coefficients are taken modulo p) is a UFD. For a more rigorous definition, you can refer wikipedia.
Is this common knowledge that the ring of polynomials is a UFD? Since the number of accepted solutions was reasonably high, I believe there might be a simpler way to prove the sufficient condition.
I took this:
https://en.wikipedia.org/wiki/Polynomial_remainder_theorem
And somehow modify the values, to get the form (x — a). Of course I still was not sure if it was right, so I implemented a brute force solution to check that.
Unfortunately I lacked a few minutes to finish sqrt decomposition to get a full score.
Yes, it's called Gauss's Theorem: If a ring R is a UFD, then the ring R[x] of polynomials with coefficients in R is also a UFD.