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:
- 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
- ₹100 Amazon gift vouchers to the top 50 participants.
- ₹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! :)
First of all update us about the prizes for march grand contest. We did not receive any info regarding that.
We are waiting for Amazon vouchers, they'll be distributed by next Friday. Apologies for the delay caused.
Its been 12 days now. I request you to not put false propoganda of prizes if you can't manage things that way.
Submissions of D will be rejudged, right?
Yes, they'll be re-judged!
But why to rejudge so late?? You should have done it long before, when test files were fixed.
They have been re-judged.
When will the editorials be posted?
Will post by tomorrow.
is it posted somewhere ..?
When will it be posted ?
Why have you changed the problem statement of C? I think even the previous statement was fine, the answer should be the same?
The answer is zero for the old version and non zero for the new version.
Oh! My bad ... I somehow proved that both the statements were equal :XD, got my mistake. Thanks!
What were the changes in the statement? I think I missed them
I was solving for — (x,y) to ((x+A) mod N, (y+B) mod M) as the only possible move until clarifications came.
And I thought I had wasted an hour because I misread the statement :/
Same here :(
Problem E is on stackexchange.
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$$$.
Code for Reference
Auto comment: topic has been updated by swapnil07 (previous revision, new revision, compare).