Блог пользователя swapnil07

Автор swapnil07, история, 3 года назад, По-английски

Edit: The prizes have been distributed and the editorials have been published.

Warm greetings,

Newton School cordially invites you to be a part of our monthly coding contest. The challenge will go live on 29th April 2022 at 9 PM IST.

Registration Link: Newton's Coding Challenge

You will be given 6 problems and 150 minutes to solve them. The contest will be rated for all!

The problems were written and tested by dnshgyl21, _deactivated_, Sawarnik, and Xzirium.

We would also like to thank gkapatia for co-ordinating the contest.

Highlights of contest:

  1. The Prize Money for the top 5 performers are as follows:
    • First Prize: ₹10,000
    • Second Prize: ₹5,000
    • Third Prize: ₹2,500
    • Fourth Prize: ₹1,500
    • Fifth Prize: ₹1,000
  2. ₹100 Amazon gift vouchers to the top 50 participants.
  3. ₹100 Amazon gift vouchers to 50 randomly selected participants ranked between 51-500.

Note: Top 5 participants from other countries can opt to receive an Amazon Gift voucher in their respective currencies. All the other gift vouchers will be sent in INR.

We hope you like the contest! See you all at the leaderboard! :)

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

First of all update us about the prizes for march grand contest. We did not receive any info regarding that.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    We are waiting for Amazon vouchers, they'll be distributed by next Friday. Apologies for the delay caused.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      Its been 12 days now. I request you to not put false propoganda of prizes if you can't manage things that way.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Submissions of D will be rejudged, right?

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

When will the editorials be posted?

»
3 года назад, # |
Rev. 3   Проголосовать: нравится -7 Проголосовать: не нравится

Why have you changed the problem statement of C? I think even the previous statement was fine, the answer should be the same?

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Problem E is on stackexchange.

»
3 года назад, # |
Rev. 6   Проголосовать: нравится +6 Проголосовать: не нравится

problem C can be done in $$$q * [sqrt(N) + sqrt(M)]$$$

My approach was basically at first I formed the equation

$$$(y1 + q * B) \ mod \hspace{2mm} M = y2$$$

Which can be rewritten like this

$$$M * q' + (-B) * q = y1 - y2$$$

This is a linear diophantine equation and one can obtain the general form of pair solutions which is mentioned on the linear diophantine equations page of CP-Algorithms.

https://cp-algorithms.com/algebra/linear-diophantine-equation.html

Observation :- If we plug the values corresponding to the general solution $$$x, y$$$ one can notice that only checking the usual gcd condition for linear diophantine equations does it and we won't have to deal with any range checks or anything.

So now our problem is basically checking if $$$x1 - x2$$$ is divisible by $$$gcd(n, i)$$$ where $$$i$$$ lies from $$$1$$$ to $$$n - 1$$$.

To solve it fast we can precompute gcds and then in sqrt time compute answers independently for $$$X$$$ and $$$Y$$$. Finally we multiply them and get our answer.

There is an edge case if the difference between $$$x1 - x2$$$ comes out to be $$$0$$$.

Spoiler

Code for Reference

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by swapnil07 (previous revision, new revision, compare).