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

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

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

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

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

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

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

Will it be possible to submit in practice mode?

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

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.

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

What was the intended solution of Lady Alicent and Dragons?

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

    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
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

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

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

    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)$$$

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

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)

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

Where are the editorials posted?

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

Where is the editorial?