zemen's blog

HackerRank 101Hack 45th Edition
By zemen, history, 7 years ago, In English

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!

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

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice problemset! How to solve E?

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

    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.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 6   Vote: I like it 0 Vote: I do not like it

    Here is my brute force solution:

    Spoiler

    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 :).

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

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 .

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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)

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wasn't the time limit too tight in problem E?

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

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

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

            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.

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

            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.

            → Reply