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

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

Warm greetings,

Newton School cordially invites you to be a part of our monthly coding contest. The challenge will go live on 30th November 2021 at 9 PM IST. Registration Link: Newton's Coding Challenge

You will be given 7 problems and 150 minutes to solve them. The contest will be rated for all!

The problems were written and tested by _Enigma__, ShlokG, and iLLusio.

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 an Amazon Gift voucher in their respective currencies. All other gift vouchers will be sent in INR.

We hope you like the contest! Hope to see you all at the leaderboard! :)

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

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

Great work guys

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

In the September challenge also, it was mentioned that editorials would be published soon. But till now there are no editorials. Was it ever published and if yes where are they published. And if not, would this contest have editorials? P.S. Pls don't take it otherwise, I appreciate your dish(contest) but a bit of garnishing(editorials) would make it wholesome. :)

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

    Hey, we have published the editorials for the September contest.

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

      Ohh thank you very much for taking out time to reply...Relly sorry that I wasn't able to find it... I would request you to please attach it to this blog so that everyone could easily find it as many would check site and this blog only. Again thanks for clarifying!

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

What was the idea for 4th problem? The answer should be -1 or N+M-2 right? I removed the cells that cannot be reached (due to parity) and had a dfs to check reachability. Did not work.

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

    It was BFS . I think code is self explanatory , let me know if u cant understand.

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

      If an answer is possible it would always be N + M — 2 right?

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

        No not necessary.

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

          1) So each cell has a fixed parity, if we'll arrive there at odd steps or even. 2) If that cell is blocked at that parity then we can never visit the cell. 3) It's never optimal to visit one cell more than once

          If all 3 are true we can have only N + M — 2 as answer right if at all possible?

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

            I think your 3 points are true, but they dont imply your last statement, imagine a board where the optimal path has zig zags, we dont visit same cell twice but we go back and forth along the rows.

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

              I'm still not sure if there could be a case where we would need to decrease the row pointer or column pointer. I could be mistaken.

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

            All 3 are true but N+M-2 isn't. It is possible that the player is forced to move in a zig zag way , forcing him to make more than N+M-2 moves.

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

    There can be 2 possible sets of laser orientations.
    Perform BFS starting from (1,1).
    For any cell, for the next step, check if the cell is unvisited and is not under a laser.
    code for reference.

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

How to solve the probability one ?
We have a bag , and 2 types of balls, B and W. Alice and bob are playing , Alice starts first . In each turn a player removes a ball . Whenever white ball is removed it is put back in the bag , and when black is chosen it is taken out . The one removing the second black ball wins . Whats the probability of Alice winning ?

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

    Lets assume p is probability of alice winning then

    1) alice choose white ball :- ( W/(W+B) )*( 1-p )

    2) alice choose black ball:- all pattern of type BWB, BWWWB, BWWWWWB....this will become infinite Geometric progression.

    Add these two, you will get the answer.

    Code

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

I liked problem Q6, i think it was a nice problem.

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

Why Memory limit in the 4th problem was tight?

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

    I ended up using short data type for the first time in any contest xD.
    Although a good reminder to always take care of ML

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

    The default memory limit on the platform is 128MB. And it was an oversight on my part combined with the fact that the setter solution takes only 40MB.

    It was not intended to make contestants optimise memory. Apologies for that.