Блог пользователя gkapatia

Автор gkapatia, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Clashes with Lunchtime :(

»
3 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      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$$$.