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:
- 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 other gift vouchers will be sent in INR.
We hope you like the contest! Hope to see you all at the leaderboard! :)
Great work guys
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. :)
Hey, we have published the editorials for the September contest.
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!
The blog has been updated. Thanks for informing. :)
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.
It was BFS . I think code is self explanatory , let me know if u cant understand.
If an answer is possible it would always be N + M — 2 right?
No not necessary.
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 once
If all 3 are true we can have only N + M — 2 as answer right if at all possible?
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.
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.
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.
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.
Thanks for this! I implemented this code But not sure why it gives WA for some cases.
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 ?
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
Edit :Thanks for the help.
I liked problem Q6, i think it was a nice problem.
Problem 5 was stars and bars ? We should start by fixing elements of each type and iterate on gaps right ?
https://math.stackexchange.com/questions/600/circular-permutations-with-indistinguishable-objects
How to solve problem 6?
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 .
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.
You are welcome. https://pastebin.com/iDm3UcSM
Why Memory limit in the 4th problem was tight?
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
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.