Warm greetings,
Newton School cordially invites you to be a part of our monthly coding contest. The challenge will go live on 24th June 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, Xzirium, and _Enigma__.
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 the prize money through Paypal. All the other gift vouchers will be sent in INR.
We hope you like the contest! See you all at the leaderboard! :)
When will the editorial of previous contest (May Challenge) be released?
it "May" not be released.
Due to this only I feel the day they stop giving monetary rewards no one would participate except very high-rated users. They don't provide editorial and have questions locked for more than 12 hours hindering upsolving.
can't create account
Sorry for stupid question but why do I have to give my phone number to register?
There is some issue with 1st test case of problem 1 (Possibly x and n are on different lines). Please check.
D = ARC036-C
english version plz!
Sorry, this contest is before AGC001, so only Japanese statement exists.
This is exactly same as today's D, except |n(A)-n(B)|<K mod 998244353 or |n(0)-n(1)|<=K mod 1e9+7
Is a 3-D dp solution the intended one?
Yes
what's the equivalent cf rating for D ?!!...did A,B,C in 15 minutes and then got nothing for D till last (◕‸◕ )(◕‸◕ )
1700 seems fair.
Are there system test in the contest.. My solution to A passed before but now it shows incorrect submission
Problem A and B were simple brute force
Problem C was a bit interesting.
Make an undirected graph, connect $$$i$$$ and $$$j$$$ via an edge if we are allowed to swap indices $$$i$$$ and $$$j$$$. I claim that for a connected component of indices $$$(i_{1}, i_{2}, i_{3}....i_{z})$$$, I can freely reorder them to any permutation. To show this, it is sufficient to prove that I can swap any two indices $$$i_k$$$ and $$$i_{k+1}$$$ without changing the rest of the array. If an edge connects them directly then we can swap them, otherwise, there must be a sequence of indices connecting $$$i_k$$$ and $$$i_{k+1}$$$ since they belong to same connected component.
Let it be like this: $$$i_k - i_{j} - i_{j+1} ... - i_{j+r} - i_{k+1}$$$. It is easy to see that to swap $$$A[i_k]$$$ and $$$A[i_{k+1}]$$$, First, swap $$$(i_k , i_{j})$$$, then $$$(i_{j} , i_{j+1})$$$, then $$$(i_{j+1} , i_{j+2})$$$ .. and so on, until we swap $$$(i_{j+r} , i_{k+1})$$$. This brings $$$A[i_k]$$$ at index $$$k+1$$$ and $$$A[i_{k+1}]$$$ at index $$$i_{j+r}$$$.
So again swap $$$(i_{j+r-1},i_{j+r})$$$ then, $$$(i_{j+r-2},i_{j+r-1})$$$ then, $$$(i_{j+r-3},i_{j+r-2})$$$, and so on, until we finally swap $$$(i_{k},i_{j})$$$. This finally brings $$$A[i_{k+1}]$$$ at index $$$k$$$. So, finally we have swapped $$$A[i_k]$$$ and $$$A[i_{k+1}]$$$. Moreover, position of the rest of the numbers doesn't get changed.
Now, problem is almost solved, it can be shown that to minimize the expression, we must pair the lowest $$$C[i]$$$ with highest $$$A[j]$$$ (of course $$$i$$$ and $$$j$$$ has to belong to same connected component).
I didn't like problem D much, it was very standard.
Put $$$+1$$$ in place of $$$B$$$ and $$$-1$$$ in place of $$$A$$$. The sum of any subarray $$$-m<S[i,j]<m$$$. Let $$$dp[i][j][k]$$$ denote the number of ways to get the string $$$[1..i]$$$ such that minimum suffix sum $$$[x..i]$$$ is $$$j$$$ and maximum suffix sum $$$[y..i]$$$ is $$$k$$$. Its very easy to do via forward style DP.
Once you know $$$dp[i][j][k]$$$, update the rest of values as if $$$s[i+1]=A$$$ OR $$$s[i+1]=U$$$ then,
$$$dp[i+1][min(j-1,-1)][max(k-1,-1)]<= (dp[i+1][min(j-1,-1)][max(k-1,-1)]+dp[i][j][k])$$$
otherwise if $$$s[i+1]=B$$$ OR $$$s[i+1]=U$$$ then,
$$$dp[i+1][min(j+1,1)][max(k+1,1)]<= (dp[i+1][min(j+1,1)][max(k+1,1)]+dp[i][j][k])$$$
I dont know how to just start; You just put A ->1 and B =-1 Start dp solution Can you make editorial which just go through the question so that We can learn how to deal with that type of problem
Can you explain D in detail, I am not getting it . Thanks in advance..
Problem C: yes it was a nice, I implemented with Disjoint set union
why the name is newton? ..it seems to be mechanics challenge*
Solution for E —
For every person, we know that when he enters, he will enter in a room of exactly $$$x$$$ people and there will be exactly $$$y$$$ such rooms. These values can be easily calculated for each person using a set. Now iterate from back to front. We will calculate the expected number of people which will enter after this person enters. This can be maintained with dp and some probability calculations.
Please open questions and allow submitting code...