swapnil07's blog

By swapnil07, history, 23 months ago, In English

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

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

| Write comment?
»
23 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

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

»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Submissions of D will be rejudged, right?

»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

When will the editorials be posted?

»
23 months ago, # |
Rev. 3   Vote: I like it -7 Vote: I do not like it

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

  • »
    »
    23 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it
    2 2
    1
    0 0 1 0
    

    The answer is zero for the old version and non zero for the new version.

    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh! My bad ... I somehow proved that both the statements were equal :XD, got my mistake. Thanks!

  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What were the changes in the statement? I think I missed them

    • »
      »
      »
      23 months ago, # ^ |
      Rev. 3   Vote: I like it +8 Vote: I do not like it

      I was solving for — (x,y) to ((x+A) mod N, (y+B) mod M) as the only possible move until clarifications came.

      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        And I thought I had wasted an hour because I misread the statement :/

»
23 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Problem E is on stackexchange.

»
23 months ago, # |
Rev. 6   Vote: I like it +6 Vote: I do not like it

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

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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