When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

gkapatia's blog

By gkapatia, history, 3 years 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

»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Clashes with Lunchtime :(

»
3 years 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?

  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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?

    • »
      »
      »
      3 years 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$$$.