swapnil07's blog

By swapnil07, history, 19 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 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

| Write comment?
»
19 months 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

»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Will it be possible to submit in practice mode?

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

    contest will open for practice mode soon

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

    Hey, the contest is open for practice!

    • »
      »
      »
      19 months 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.

»
19 months 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.

»
19 months ago, # |
  Vote: I like it +21 Vote: I do not like it

What was the intended solution of Lady Alicent and Dragons?

  • »
    »
    19 months 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
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      • »
        »
        »
        »
        19 months 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
        • »
          »
          »
          »
          »
          19 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    19 months 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)$$$

»
19 months 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)

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

Where are the editorials posted?

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

Where is the editorial?