swapnil07's blog

Newton's Coding Challenge June 2021 Invite
By swapnil07, history, 3 years 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 June 2021 at 9 PM IST. The contest will have our dearest characters from FRIENDS!

Registration Link: Newton's Coding Challenge

You will be given 6 problems and 150 minutes to solve them.

The problems are written and prepared by aniket9465 and swapnil07.

We would also like to thank:

  • gkapatia for co-ordinating the contest.
  • jiraya_ and ak532 for the valuable feedback throughout.

    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: Prizes are for Indian Participants only. Participants from other countries can opt to receive an Amazon Gift voucher in INR.

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

    Also, we have opened the problems from previous coding contests for practice.

    Thanks, have a great day ahead.

    • Vote: I like it
    • -20
    • Vote: I do not like it

    Comments Comments (31)
    | Write comment?
    »
    3 years ago, # |
      Vote: I like it +3 Vote: I do not like it

    Auto comment: topic has been updated by swapnil07 (previous revision, new revision, compare).

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

    what is the Stream/ Specialization section of the reg. part??

    → Reply
    »
    3 years ago, # |
    ← Rev. 2   Vote: I like it -6 Vote: I do not like it

    .

    → Reply
    »
    3 years ago, # |
      Vote: I like it +30 Vote: I do not like it

    "Something Wrong" on Questions tab.

    → Reply
    »
    3 years ago, # |
      Vote: I like it +17 Vote: I do not like it

    Soln to E

    → Reply
    »
    3 years ago, # |
      Vote: I like it 0 Vote: I do not like it

    Problem F

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

    In E do we use Dirichlet convolution to find the number of co-prime pairs less than $$$\displaystyle \frac{L}{X}$$$ or is there an easier way to go about it?
    My idea was to calculate $$$\mu(i)$$$ using dirichlet convolution and then find the number of coprime pairs by $$$\displaystyle\sum_{i=1}^N \mu(i)(\frac{N}{i})^2$$$ where $$$\displaystyle N=\frac{L}{X}$$$. This would be an $$$\displaystyle\mathcal{O}((\frac{L}{X})^{\frac{2}{3}})$$$ solution.

    → Reply
    »
    3 years ago, # |
    ← Rev. 2   Vote: I like it +63 Vote: I do not like it

    1e9/1e18 boring math problem spam with occasionally sub-par samples, and copied problems. (Also, sum of Euler totient till 1e9? Really? Is this Project Euler? Also easily googleable BTW)

    → Reply
    »
    3 years ago, # |
      Vote: I like it +6 Vote: I do not like it

    In D what's the approach or there was a short trick ????

    → Reply
    »
    3 years ago, # |
      Vote: I like it 0 Vote: I do not like it

    In problem C, this solution was getting WA on 3 cases, could anyone help out?

    main function
    → Reply
    • »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      wait what? My solution was pretty much the same yet it got AC. if(a>=b) then Chandler wins else Joey wins. How come your solution doesn't work

      → Reply
      • »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, that's what confuses me. The entire duration I tried to figure this out, even wrote a brute-force checker but didn't find the error. swapnil07 Can you please look into this, any bug ? My username is adityatrivedi25. Thanks

        → Reply
    »
    3 years ago, # |
      Vote: I like it +11 Vote: I do not like it

    What was the simpler solution for problem D.

    My solution used Dp[0,a+b]=0 and Dp[1,a+b-1]=x, and made equations for other states in terms of x. Had to use matrix exponentiation for solving.

    → Reply
    • »
      »
      3 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      $$$dp[i][j]=i*j$$$ lol

      → Reply
      • »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you prove why such a solution?

        → Reply
        • »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 2   Vote: I like it +3 Vote: I do not like it

          You can prove using induction on following :

          dp[i][j]=1+0.5*(dp[i-1][j+1] + dp[i+1][j-1])

          → Reply
          • »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            And how can this be counted through dp? Do we have cyclic transitions

            → Reply
      • »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Lol, now I can see that using induction.

        wasn't very straightforward on just seeing the Dp[i][j] in terms of Dp[i-1][j+1] and Dp[i+1][j-1].

        → Reply
    • »
      »
      3 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Problem $$$D$$$ already exists by the name Gamblers Ruin. The same problem has already been discussed here. Answer to the porblem is just $$$a \cdot o$$$.

      The proof is really hard it seems.

      → Reply
      • »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Do you mean to say that you observed it just by looking at the recurrence? or did you do the hard proof?

        → Reply
        • »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          No, I knew about Gamblers Ruin prior to the contest. Otherwise, I don't think I could have solved this challenge on my own.

          → Reply
      • »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Also, problems $$$A$$$ and $$$B$$$ are just bad. Problem $$$E$$$ already exists in multiple sites. For example here. And, now I know that problem $$$F$$$ is the exact copy of this. Although I liked solving it during the contest as I didn't have any prior knowledge of the existing problem. I solved it using digit dp along with plug dp.

        I don't know how this contest has prizes with these problems.

        → Reply
    • »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +42 Vote: I do not like it

      Let $$$N = A+O$$$. $$$dp[i]$$$ represents the expected number of moves given that there are $$$i$$$ apples currently (and as a result $$$N-i$$$ oranges).

      $$$ dp[i] = 1 + (dp[i-1] + dp[i+1])/2\\ \implies dp[i+1] - dp[i] = dp[i] - dp[i-1] - 2 $$$

      Hence, the difference between consecutive items in the DP form an AP with common difference $$$-2$$$. Let's say the first term of this AP is $$$d$$$. Also, as a base case $$$dp[0] = dp[N] = 0$$$. This means that the sum of all adjacent differences in the DP, and so this AP, is 0.

      Using the expression for the sum of an AP, we get $$$N(d-N+1) = 0$$$, and hence $$$d = N-1$$$.

      Our required answer is $$$dp[A]$$$, which the the sum of first $$$A$$$ terms of the above AP. You can see that it reduces to $$$A*(N-A)$$$.

      → Reply
    »
    3 years ago, # |
      Vote: I like it 0 Vote: I do not like it

    For D, should we not have the following recurrence $$$dp(x,y) = 1 + \left(\frac{x}{x+y}\right)dp(x-1,y+1) + \left(\frac{y}{x+y}\right)dp(x + 1,y - 1)$$$

    → Reply
    • »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's mentioned that both apple and orange are chosen with the same probability.

      → Reply
      • »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Looks like I didn't read the problem carefully!

        → Reply