swapnil07's blog

By swapnil07, history, 2 months 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 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! :)

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

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

Great work guys

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

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

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

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      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!

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

        The blog has been updated. Thanks for informing. :)

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

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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    My code
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No not necessary.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

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

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 ?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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

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

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

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

Why Memory limit in the 4th problem was tight?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

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

Editorial? :-)