Warm greetings,
Newton School cordially invites you to be a part of our monthly coding contest. The challenge will go live on 30th June 2021 at 9 PM IST. The contest will have our dearest characters from FRIENDS!
Registration Link: Newton's Coding Challenge
You will be given 6 problems and 150 minutes to solve them.
The problems are written and prepared by aniket9465 and swapnil07.
We would also like to thank:
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: Prizes are for Indian Participants only. Participants from other countries can opt to receive an Amazon Gift voucher in INR.
We hope you like the contest! Hope to see you all at the leaderboard! :)
Also, we have opened the problems from previous coding contests for practice.
Thanks, have a great day ahead.
Auto comment: topic has been updated by swapnil07 (previous revision, new revision, compare).
what is the Stream/ Specialization section of the reg. part??
Your college branch!
.
"Something Wrong" on Questions tab.
Soln to E
Problem F
In E do we use Dirichlet convolution to find the number of co-prime pairs less than $$$\displaystyle \frac{L}{X}$$$ or is there an easier way to go about it?
My idea was to calculate $$$\mu(i)$$$ using dirichlet convolution and then find the number of coprime pairs by $$$\displaystyle\sum_{i=1}^N \mu(i)(\frac{N}{i})^2$$$ where $$$\displaystyle N=\frac{L}{X}$$$. This would be an $$$\displaystyle\mathcal{O}((\frac{L}{X})^{\frac{2}{3}})$$$ solution.
1e9/1e18 boring math problem spam with occasionally sub-par samples, and copied problems. (Also, sum of Euler totient till 1e9? Really? Is this Project Euler? Also easily googleable BTW)
In D what's the approach or there was a short trick ????
cin>>a>>b; cout<<(a*b)%1000000007;Thanks sir , Orz :)
In problem C, this solution was getting WA on 3 cases, could anyone help out?
wait what? My solution was pretty much the same yet it got AC. if(a>=b) then Chandler wins else Joey wins. How come your solution doesn't work
Yes, that's what confuses me. The entire duration I tried to figure this out, even wrote a brute-force checker but didn't find the error. swapnil07 Can you please look into this, any bug ? My username is adityatrivedi25. Thanks
What was the simpler solution for problem D.
My solution used Dp[0,a+b]=0 and Dp[1,a+b-1]=x, and made equations for other states in terms of x. Had to use matrix exponentiation for solving.
$$$dp[i][j]=i*j$$$ lol
Can you prove why such a solution?
You can prove using induction on following :
dp[i][j]=1+0.5*(dp[i-1][j+1] + dp[i+1][j-1])
And how can this be counted through dp? Do we have cyclic transitions
Lol, now I can see that using induction.
wasn't very straightforward on just seeing the Dp[i][j] in terms of Dp[i-1][j+1] and Dp[i+1][j-1].
Problem $$$D$$$ already exists by the name Gamblers Ruin. The same problem has already been discussed here. Answer to the porblem is just $$$a \cdot o$$$.
The proof is really hard it seems.
Do you mean to say that you observed it just by looking at the recurrence? or did you do the hard proof?
No, I knew about Gamblers Ruin prior to the contest. Otherwise, I don't think I could have solved this challenge on my own.
Also, problems $$$A$$$ and $$$B$$$ are just bad. Problem $$$E$$$ already exists in multiple sites. For example here. And, now I know that problem $$$F$$$ is the exact copy of this. Although I liked solving it during the contest as I didn't have any prior knowledge of the existing problem. I solved it using digit dp along with plug dp.
I don't know how this contest has prizes with these problems.
Can you elaborate your solution for F?
Let $$$N = A+O$$$. $$$dp[i]$$$ represents the expected number of moves given that there are $$$i$$$ apples currently (and as a result $$$N-i$$$ oranges).
Hence, the difference between consecutive items in the DP form an AP with common difference $$$-2$$$. Let's say the first term of this AP is $$$d$$$. Also, as a base case $$$dp[0] = dp[N] = 0$$$. This means that the sum of all adjacent differences in the DP, and so this AP, is 0.
Using the expression for the sum of an AP, we get $$$N(d-N+1) = 0$$$, and hence $$$d = N-1$$$.
Our required answer is $$$dp[A]$$$, which the the sum of first $$$A$$$ terms of the above AP. You can see that it reduces to $$$A*(N-A)$$$.
Lovely explanation, thanks!!
For D, should we not have the following recurrence $$$dp(x,y) = 1 + \left(\frac{x}{x+y}\right)dp(x-1,y+1) + \left(\frac{y}{x+y}\right)dp(x + 1,y - 1)$$$
It's mentioned that both apple and orange are chosen with the same probability.
Looks like I didn't read the problem carefully!