### 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 24th June 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, Xzirium, and _Enigma__.

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 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! :)  Comments (24)
 » 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?
 » 2 months ago, # | ← Rev. 3 →   There is some issue with 1st test case of problem 1 (Possibly x and n are on different lines). Please check.
 » I think there is some problem with question 1
 » D = ARC036-C
•  » » english version plz!
•  » » » 2 months ago, # ^ | ← Rev. 2 →   Sorry, this contest is before AGC001, so only Japanese statement exists.This is exactly same as today's D, except |n(A)-n(B)|
•  » » » » 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
 » 2 months ago, # | ← Rev. 4 →   Problem A and B were simple brute forceProblem C was a bit interesting. Problem CMake 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. Problem DPut $+1$ in place of $B$ and $-1$ in place of $A$. The sum of any subarray $-m •  » » 2 months ago, # ^ | ← Rev. 2 → 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.. •  » » 7 weeks ago, # ^ | ← Rev. 2 → Problem C: yes it was a nice, I implemented with Disjoint set union  » why the name is newton? ..it seems to be mechanics challenge*  » Nice problem C!  » When can we see the problem statements again?  » 7 weeks ago, # | ← Rev. 3 → 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. // a[i] = {number of people in the room where i goes, number of such rooms when i enters} vector ans(n); vector dp(m+10); for(int i = n-1; i >= 0; i--){ ans[i] = 1 + dp[a[i].first+1]; Mint prob = Mint(1) / a[i].second; (dp[a[i].first] *= (1-prob)) += prob*ans[i]; } for(int i = 0; i < n; i++){ cout << ans[i] + a[i].first << '\n'; } 
 » Please open questions and allow submitting code...