swapnil07's blog

By swapnil07, history, 4 weeks 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 31st August 2022 at 9 PM IST.

Registration Link: Newton's Coding Challenge

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

The problems were written and tested by dnshgyl21, _deactivated_, Sawarnik, Xzirium, and _Enigma__.

We would also like to thank pradumangoyal and 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.
  4. Dragon eggs to random participants (undisclosed).

Note: Top 5 participants from other countries can opt to receive the prize money through Paypal. All the other gift vouchers will be sent in INR.

We hope you like the contest! See you all at the leaderboard! Winter is coming :)

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

»
4 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Couldn't register. Every time, I enter my valid phone number and click "Send OTP", it pops up the message -_-
Some unexpected error happened at third party library

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Will it be possible to submit in practice mode?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    contest will open for practice mode soon

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Hey, the contest is open for practice!

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      When i open problem it still has locked sign on the top-left corner. Locked sign has only problems which I had submitted during contest.

»
4 weeks ago, # |
Rev. 3   Vote: I like it +20 Vote: I do not like it

In E(Golden Coins), why is the weight of $$$(x,y) \rightarrow (x+1,y)$$$ denoted by $$$B$$$, not $$$A$$$?

You could say that this can be a matter of taste. However, I and gennadykorotkevitch made the same mistake of swapping these two parameters, so it should be unnatural to some extent.

»
4 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

What was the intended solution of Lady Alicent and Dragons?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    I submitted $$$O(n^2 logn)$$$ solution.

    I found answer for queries offline.

    Here's what I did.

    Suppose our current root is $$$u$$$. Now look at all nodes which are adjacent to $$$u$$$.

    Suppose $$$x$$$ and $$$y$$$ are two children of $$$u$$$ such that $$$EdgeValue(u,x)<EdgeValue(u,y)$$$. Now $$$path(u,v)<path(u,y)$$$ for all nodes $$$v$$$ which lie in the subtree of $$$x$$$.

    So if we intend to visit the nodes in order $$$a_1,a_2,\dots a_n$$$ such that $$$path(u,a_{i-1}) \leq path(u,a_{i})$$$, we should visit whole subtree of $$$x$$$ before visiting node $$$y$$$. So you can try recursive solution somewhat similar to dfs.

    Code
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      satyam_343 could you please comment your code or elaborate a little more, would be really helpful for understanding.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        Suppose you have rooted the tree at some node $$$u$$$ and you plan to find $$$f(u,i)$$$ $$$(1 \leq i \leq n)$$$.

        Here $$$f(u,i)$$$ gives the number of nodes $$$v$$$ such that $$$path(u,i)>path(u,v)$$$.

        Also note that by definition answer to query $$$u$$$ $$$v$$$ is just $$$f(u,v)$$$.

        Now let's see how to find $$$f(u,i)$$$ for all $$$(1 \leq i \leq n)$$$.

        First of all $$$f(u,u)=0$$$.

        Here is one way in which you visit nodes $$$a_1,a_2,\dots ,a_n$$$ such that $$$path(u,a_{i-1}) \leq path(u,a_i)$$$.

        Traverse over all nodes $$$v$$$ which are adjacent to $$$u$$$ — $$$ v_1,v_2,\dots ,v_k$$$.

        As our motive is to visit nodes such that path of current node $$$\geq$$$ path of previously visited node, it is intuitive to visit nodes in non-decreasing order of edge weight(here we are talking about order of $$$v_1,v_2,\dots,v_k$$$ only).

        Also if $$$weight(u,v_i)<weight(u,v_j) (1 \leq i,j \leq k)$$$, all nodes in the subtree of $$$v_i$$$ should be visited before visiting $$$v_j$$$. So if we sort the nodes in all adjacency lists($$$adj[i] (1 \leq i \leq n)$$$ on the basis of edge weight and do standard dfs, we will visit all nodes in subtree of $$$v_i$$$ before visiting $$$v_j$$$.

        But which node to visit first if $$$weight(u,v_i)=weight(u,v_j)$$$?

        As both nodes have same path we should visit both nodes at same time. But how to do that?

        In standard dfs we visit one node at a time — $$$ dfs(int CurrentNode)$$$

        For our problem, we can visit a list of nodes at a time — $$$ dfs(vector<int> CurrentNodes)$$$

        Is there something special about vector $$$CurrentNodes$$$?

        Yes, all nodes in this vector will have same path.

        Also it is not possible that $$$path(u,i)=path(u,j)$$$ such that $$$i \in CurrentNodes$$$ and $$$ j \notin CurrentNodes $$$ (Why? — Left as an exercise)

        Code with comments
        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for explaining thoroughly. Got your point, really nice approach.

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

    I simply used a trie. Fix a root $$$u$$$, now, I will store answers of all query in form $$$(u,v)$$$ in $$$dp[u][v]$$$.

    Imagine a trie with all strings inserted starting from root. Formally, all strings which are formed via simple path $$$(u,i)$$$ are present in my trie. Then, to compute answer for query $$$(u,v)$$$ would be easy. (Figure it out yourself!)

    Inserting strings into trie can be done in $$$O(1)$$$ instead of $$$O(L)$$$ ($$$L$$$ is the length of string) by doing a dfs on the tree and inserting string into trie on the way, (by maintaining the ending string node of the parent of the current node).

    Time Complexity: $$$O(n^2)$$$

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

What was your approach for Problem 3(Stepstones)?

What I did was, I calculated the factors for the smallest number in the array and iterated over all factors in descending order and checked if it can be the GCD of entire array with doing the given operation at most one time. Time Complexity: O(Sqrt(Min(A)) + |Factors_Set|*N)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Ok my code should not work but it apparently passed all the test cases, as we can also replace the smallest element.

    Counter TC:
    2 10
    2 8

    My Output: 2
    Actual Answer: 8

    So yeah, you guys might wanna include this tc in the system also.

    My Code
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why is this getting downvotes? Isn't that case is missing from the system test cases?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How are you going to select 50 random participants.

Is there any way to see the names of those 50 participants.

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Where are the editorials posted?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is the editorial?