### swapnil07's blog

By swapnil07, history, 2 months ago,

Warm greetings,

Newton School cordially invites you to be a part of our monthly coding contest. The challenge will go live on 30th November 2021 at 9 PM IST. Registration Link: Newton's Coding Challenge

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

The problems were written and tested by _Enigma__, ShlokG, and iLLusio.

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 other gift vouchers will be sent in INR.

We hope you like the contest! Hope to see you all at the leaderboard! :)

• +39

 » 2 months ago, # |   +9 Great work guys
 » 2 months ago, # |   +6 In the September challenge also, it was mentioned that editorials would be published soon. But till now there are no editorials. Was it ever published and if yes where are they published. And if not, would this contest have editorials? P.S. Pls don't take it otherwise, I appreciate your dish(contest) but a bit of garnishing(editorials) would make it wholesome. :)
•  » » 2 months ago, # ^ |   +13 Hey, we have published the editorials for the September contest.
•  » » » 2 months ago, # ^ |   +14 Ohh thank you very much for taking out time to reply...Relly sorry that I wasn't able to find it... I would request you to please attach it to this blog so that everyone could easily find it as many would check site and this blog only. Again thanks for clarifying!
•  » » » » 2 months ago, # ^ |   +2 The blog has been updated. Thanks for informing. :)
 » 2 months ago, # |   0 What was the idea for 4th problem? The answer should be -1 or N+M-2 right? I removed the cells that cannot be reached (due to parity) and had a dfs to check reachability. Did not work.
•  » » 2 months ago, # ^ |   0 It was BFS . I think code is self explanatory , let me know if u cant understand. My code#include using namespace std; typedef int lli; typedef long double ld; #define plli pair #define pb push_back const lli mod=1e9+7; const lli mod1=998244353; #define fir first #define sec second #define pplli pair #define ppplli pair> #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL); const lli N=3010; bool vis[N][N]; bool r[N][2],c[N][2]; lli dx[4]={-1,1,0,0}; lli dy[4]={0,0,-1,1}; bool check(lli x1,lli y1,lli f) { return (r[x1][f] or c[y1][f]); } int main() { fastio lli T,i,j; T=1; // cin>>T; while(T--) { lli n,m,k; cin>>n>>m>>k; memset(vis,false,sizeof(vis)); memset(r,false,sizeof(r)); memset(c,false,sizeof(c)); for(i=0;i>x>>y>>c1; --x,--y; r[x][c1!='R']=1; c[y][c1!='C']=1; } queue > q; q.push({0,0,0}); vis[0][0]=0; lli ans=mod; while(!q.empty()) { auto [x,y,z]=q.front(); q.pop(); if(x==n-1 and y==m-1) ans=min(ans,z); z+=1; for(i=0;i<4;i++) { lli x1=x+dx[i],y1=y+dy[i]; if(x1>=0 and x1=0 and y1=0 and y1>=0 and x1
•  » » » 2 months ago, # ^ |   0 If an answer is possible it would always be N + M — 2 right?
•  » » » » 2 months ago, # ^ |   0 No not necessary.
•  » » » » » 2 months ago, # ^ |   0 1) So each cell has a fixed parity, if we'll arrive there at odd steps or even. 2) If that cell is blocked at that parity then we can never visit the cell. 3) It's never optimal to visit one cell more than onceIf all 3 are true we can have only N + M — 2 as answer right if at all possible?
•  » » » » » » 2 months ago, # ^ |   +1 I think your 3 points are true, but they dont imply your last statement, imagine a board where the optimal path has zig zags, we dont visit same cell twice but we go back and forth along the rows.
•  » » » » » » » 2 months ago, # ^ |   0 I'm still not sure if there could be a case where we would need to decrease the row pointer or column pointer. I could be mistaken.
•  » » » » » » 2 months ago, # ^ |   0 All 3 are true but N+M-2 isn't. It is possible that the player is forced to move in a zig zag way , forcing him to make more than N+M-2 moves.
•  » » 2 months ago, # ^ |   +1 There can be 2 possible sets of laser orientations. Perform BFS starting from (1,1). For any cell, for the next step, check if the cell is unvisited and is not under a laser. code for reference.
•  » » » 2 months ago, # ^ |   0 Thanks for this! I implemented this code But not sure why it gives WA for some cases.
 » 2 months ago, # |   0 How to solve the probability one ? We have a bag , and 2 types of balls, B and W. Alice and bob are playing , Alice starts first . In each turn a player removes a ball . Whenever white ball is removed it is put back in the bag , and when black is chosen it is taken out . The one removing the second black ball wins . Whats the probability of Alice winning ?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +8 Lets assume p is probability of alice winning then 1) alice choose white ball :- ( W/(W+B) )*( 1-p )2) alice choose black ball:- all pattern of type BWB, BWWWB, BWWWWWB....this will become infinite Geometric progression.Add these two, you will get the answer.Code
•  » » » 2 months ago, # ^ | ← Rev. 6 →   +8 Edit :Thanks for the help.
 » 2 months ago, # |   +8 I liked problem Q6, i think it was a nice problem.
•  » » 2 months ago, # ^ |   0 Problem 5 was stars and bars ? We should start by fixing elements of each type and iterate on gaps right ?
•  » » » 2 months ago, # ^ |   0
•  » » 2 months ago, # ^ |   0 How to solve problem 6?
•  » » » 2 months ago, # ^ |   +10 It is clear that it is more advantageous to take the bigger numbers compared to smaller ones. So iterate from biggest to smallest and keep a set of nodes you have taken so far, check to see whether you can add the current node to the set by bitmask dp on the set of nodes + current node, answering the question what s the minimum total path length to start from node 0 , and visit all the nodes in the given set .
•  » » » » 2 months ago, # ^ |   0 Thanks for the help, can you share your code? I had a similar approach during the contest but I wasn't able to figure how to maintain the bitmask dp.
•  » » » » » 2 months ago, # ^ | ← Rev. 3 →   0 You are welcome. https://pastebin.com/iDm3UcSM
 » 2 months ago, # |   +31 Why Memory limit in the 4th problem was tight?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +1 I ended up using short data type for the first time in any contest xD.Although a good reminder to always take care of ML
•  » » 2 months ago, # ^ |   0 The default memory limit on the platform is 128MB. And it was an oversight on my part combined with the fact that the setter solution takes only 40MB.It was not intended to make contestants optimise memory. Apologies for that.
 » 2 months ago, # |   0 Editorial? :-)