gkapatia's blog

By gkapatia, history, 2 months ago, In English

Greetings,

Newton School cordially invites you to be a part of our monthly coding challenge. This month, the challenge is going to take place on eve of 27th February, 2021 at 9PM IST. The duration of the contest is 150 minutes.

Please follow below link to register. Contest page: https://www.newtonschool.co/contest-home

Highlights of contest:
- The Prize Money is ₹20k and candidates can win exciting prizes and goodies
- ₹100 gift vouchers to top 50 participants
- ₹100 gift vouchers to 50 randomly selected participants between ranks 51-500
- We receive more than 10K registrations in our contest from all engineering colleges pan India

Registrations for contest is open till start of contest.
*Note: Prizes are for Indian Participants only.

I hope you all will participate and enjoy the contest.

Regards,
Newton School Team.

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

»
2 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Clashes with Lunchtime :(

»
7 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Can someone please share their solution idea for the 5th and 6th problem?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    For the 5th problem.

    Fix the position of the unique person and the distance between the nearest power ranger to the left. Then, we can get possible ways to arrange the others in O(1) (with precalculation). It reduces to equation of form:

    (a1 + a2 + a3 + .... + aP = something, ai >= 0 for all i).

    Number of solutions for this is a well-known combinatorial result.

    We can simply iterate over all possible values of distance and finally multiply the result by N. Also handle the cases when there are not enough seats available.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I solved it with combinatorics, but it became very complex for me. Can it be solved with dp?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      There is also a closed-form formula: $$$\frac{N}{P}\binom{N-P\cdot C-1}{P-1}(N-P)$$$

      Adapt the solution given here and multiply by $$$N-P$$$.