### swapnil07's blog

By swapnil07, history, 2 months ago,

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.

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

 » 2 months ago, # |   +10 First of all update us about the prizes for march grand contest. We did not receive any info regarding that.
•  » » 2 months ago, # ^ |   0 We are waiting for Amazon vouchers, they'll be distributed by next Friday. Apologies for the delay caused.
•  » » » 2 months ago, # ^ |   +9 Its been 12 days now. I request you to not put false propoganda of prizes if you can't manage things that way.
 » 2 months ago, # |   0 My College Name is Not Found I requested but not still found because of that i can't register the contest
 » 2 months ago, # |   0 Submissions of D will be rejudged, right?
•  » » 2 months ago, # ^ |   0 Yes, they'll be re-judged!
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 But why to rejudge so late?? You should have done it long before, when test files were fixed.
•  » » » » 2 months ago, # ^ |   0 They have been re-judged.
 » 2 months ago, # |   +3 When will the editorials be posted?
•  » » 2 months ago, # ^ |   0 Will post by tomorrow.
•  » » » 2 months ago, # ^ |   +3 is it posted somewhere ..?
•  » » » 2 months ago, # ^ |   0 When will it be posted ?
 » 2 months ago, # | ← 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?
•  » » 2 months ago, # ^ |   +9 2 2 1 0 0 1 0 The answer is zero for the old version and non zero for the new version.
•  » » » 2 months ago, # ^ |   0 Oh! My bad ... I somehow proved that both the statements were equal :XD, got my mistake. Thanks!
•  » » 2 months ago, # ^ |   0 What were the changes in the statement? I think I missed them
•  » » » 2 months ago, # ^ | ← Rev. 3 →   +8 I was solving for — (x,y) to ((x+A) mod N, (y+B) mod M) as the only possible move until clarifications came.
•  » » » » 2 months ago, # ^ |   +18 And I thought I had wasted an hour because I misread the statement :/
•  » » » » » 2 months ago, # ^ |   +10 Same here :(
 » 2 months ago, # |   +18 Problem E is on stackexchange.
 » 2 months ago, # | ← 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.htmlObservation :- 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#define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i)) #define Forl(i,a,b) for(ll (i)=(a);(i) < (b); ++(i)) #define Forn(i,a,b) for(int (i)=(a);(i) >= (b); --(i)) #define Fornl(i,a,b) for(ll (i)=(a);(i) >= (b); --(i)) ll n,m; cin>>n>>m; vector cnt(maxn),dnt(maxn); Forl(i,1,m) { cnt[__gcd(m, i)] += 1; } //Forl(i,1,m)cout<>T; while(T--) { ll x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; ll x = 0, y = 0; ll p = abs(y1 - y2), q = abs(x1 - x2); if (p != 0) { for(ll i = 1; i * i <= p; i++) { if (p % i == 0) { x += cnt[i]; // cout<
 » 6 weeks ago, # |   0 Auto comment: topic has been updated by swapnil07 (previous revision, new revision, compare).