swapnil07's blog

Newton's Coding Challenge June 2022 Invite
By swapnil07, history, 2 years ago, In English

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:

  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! :)

  • Vote: I like it
  • +25
  • Vote: I do not like it

Comments Comments (21)
| Write comment?
»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

When will the editorial of previous contest (May Challenge) be released?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    it "May" not be released.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    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.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can't create account

→ Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Sorry for stupid question but why do I have to give my phone number to register?

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

There is some issue with 1st test case of problem 1 (Possibly x and n are on different lines). Please check.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

D = ARC036-C

→ Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

what's the equivalent cf rating for D ?!!...did A,B,C in 15 minutes and then got nothing for D till last (◕‸◕ )(◕‸◕ )

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are there system test in the contest.. My solution to A passed before but now it shows incorrect submission

→ Reply
»
2 years ago, # |
← Rev. 5   Vote: I like it +7 Vote: I do not like it

Problem A and B were simple brute force

Problem C was a bit interesting.

Problem C

I didn't like problem D much, it was very standard.

Problem D
→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it -11 Vote: I do not like it

    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

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Can you explain D in detail, I am not getting it . Thanks in advance..

    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Problem C: yes it was a nice, I implemented with Disjoint set union

    → Reply
»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

why the name is newton? ..it seems to be mechanics challenge*

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

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<Mint> ans(n);
vector<Mint> 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';
}
→ Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Please open questions and allow submitting code...

→ Reply