slim-shady's blog

By slim-shady, 3 months ago, In English

Discussion Thread of CodeNation Innovation Labs Hiring Challenge held on 26 January 2021.

PROBLEM 1 :-

Statement
Sample Test Cases
Extra Test Case

PROBLEM 2 :-

Statement
Sample Test Cases

PROBLEM 3 :-

Statement
Sample Test Cases

PROBLEM 4 :-

Statement
Sample Test Cases

PROBLEM 5 :-

Statement
Sample Test Cases

PROBLEM 6 :-

Statement
Sample Test Cases

PS :- THE CONTEST HAS ENDED. THOSE WHO HAVE PARTICIPATED CAN SHARE THEIR SOLUTIONS. INTERESTED NON — PARTICIPANTS CAN ALSO SHARE THEIR APPROACHES.

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

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

Video Editorial with Scoring Distribution: https://youtu.be/8tEXXSc351c

Problem 1:

Observation 1: Notice that the left arrows will form a prefix of any row. L U L can be made L U U without affecting anything. Observation 2: The number of left arrows will decrease as we go from the bottom row to the top row.

These 2 solutions lead to a $$$O(N\cdot M)$$$ DP where N, M are the dimensions of the rectangle.

Problem 2:

Observation 1: If any bit is set in >= 2 numbers in the range, answer is 0. So we can compute prefix frequencies for each bit. Observation 2: Answer will atmost be 2 because we can make the last bit 1 (having two odd integers in the range is sufficient).

So, with the prefix computation, if answer is not 0, it is 2 — (number of odd integers in the range). Solution complexity: $$$O(N + Q)$$$

Problem 3: Simple implementation problem — just store the frequency of every number. Answer = Sum of initial array. Then, ans = min(ans, sum — freq(val) * val) for all values. Solution complexity: $$$O(N)$$$

Problem 4:

We can have a $$$O(N \cdot M)$$$ DP, where DP(i, j) stores the number of ways of spending i days, where at the last day, we did an activity of type j, adhering to all the constraints. Using prefix summations, we can get the transitions in O(1) time.

Problem 5:

Observation 1: The order of the elements does not matter — we can swap any two elements doing the mentioned operations, and also get the xor of any subset of elements.

Observation 2: The above leads to Gaussian elimination based solution — we only care about the basis (linearly independent set) of elements in the array, since we can get all other XORs from it. Thus, the problem is reduced to finding the basis with the smallest sum. We can do this by finding any basis, and reduce the larger basis elements using the smaller ones.

Solution code: http://p.ip.fi/-1b1

Problem 6:

Observation 1: The required node is basically the LCA of all the leaf nodes in the range [L, R]. Observation 2: If we do a DFS order traversal of the tree and store the discovery time of every node, then we only care about finding LCA(first discovered leaf node, last discovered leaf node) in the query range, because all the other nodes lie in between.

Using this, we can solve the problem in $$$O(N \log N)$$$ using various techniques.

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

    Did the questions have uneven points distribution or the same points for every question?

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

      The harder problems had a higher score weightage. $$$P_3 < P_2 < P_1 = P_4 < P_6 < P_5$$$.

      • »
        »
        »
        »
        3 months ago, # ^ |
        Rev. 2   Vote: I like it +2 Vote: I do not like it
        JUST CURIOUS
        Spoiler
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          Various questions were given the InterviewBit team and I was responsible for reviewing the questions. So we are not the setters, more like coordinators/reviewers.

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

        Why not show this to participants?

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

        Can you elaborate D a little more ?

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

        Can you provide a rough estimate of the scores.

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

        Due to this the people who did if else, if else for 3 hours will get more point than someone who solved genuinely.

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

    Problem 6: Segment Tree + LCA

    Video editorial will be very cool. Ashishgup

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

    Can you elaborate on problem 4?

    Like what will the recurrence relation look like?

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

      yes, dp[day][lastact][streak] is very intuitive but how to reduce it to n^2

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

        remove streak from dimension, and move it transitions instead. then it can be optimized by prefix sums.

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

          Can you please elaborate on how to do that ? Coz I was able to solve it with dp[day][lastact][streak] But couldn't optimize it and it obviously gave TLE and I want to learn how to solve this very badly :( Please please help!!!

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

      $$$dp[i][j] = \sum\limits_{l=1}^{A_j}\sum\limits_{k=1}^{m} dp[i-l][k] - \sum\limits_{l=1}^{A_j}dp[i-l][j]$$$. You can simplify this by defining $$$pre[i][j] = \sum\limits_{l=1}^{i} \sum\limits_{j=1}^{m} dp[i-l][j]$$$

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

    In problem 4, we need to define $$$dp[0][j] = \frac{1}{m-1}$$$. So we define $$$dp[0][j] = 1$$$ and divide the final obtained value by $$$(m-1)$$$. Or was there some easy way to define base cases?

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

      Suppose we want answer for dp[i][j] and i-A[j]<=0, this is the only case we will be using dp[0][j]. Whenever we encounter this case, we can explicitly add 1 to dp[i][j] instead of defining dp[0][j]=1 and dividing it later. This will solve the issue.

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

    Will the ranklist be revealed?

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

    For problem 6, we can notice that LCA can be thought of as a monoid operation, so we can make a normal segtree on the range [1...N] and store the LCA in the segtree nodes. (we can store -1 corresponding to non-leafs, which will work as an identity element: LCA(x,-1) = x = LCA(-1,x))

    To make it better we can notice that LCA(X,X) = X, so it is also idempotent, so we can use a sparse table as well. Which gives us a fast solution. $$$O((NlogN+Q) * f(N))$$$. Where $$$f(N)$$$ is the time in which you calculate LCA ($$$O(logN)$$$ or $$$O(1)$$$ depending on how you do it)

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

    P2: answer can be 1 as well. if in the range, we already have an odd number, then we can add 1 to any even number and their AND will be > 0

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

    Please answer this if you have any suggestions.

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

    Can you elaborate D problem a bit more . It will be helpful if you can make a video tutorial on it.Thanks.

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

    can the answer for the fifth problem be the bitwise OR of all the elements? if no ,than why plz explain.

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

For problem 3 , we will make a hashmap which stores the frequency of each element . Iterate through hashmap and find maximum value of x = ( key * value) . Answer is simply sum of elements in the array — x;

»
3 months ago, # |
  Vote: I like it +13 Vote: I do not like it

In problem 6, was Farach Colton LCA the intended solution to find LCA without MLE? or was segment tree solution for LCA sufficient?

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

    Yes,Lca with segment tree was sufficient.

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

      Could you plz explain how to find the lca using segment tree here , I was able to get the observation required but wasn't able to find a way for lca.

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

        just use standard min/max segtree, and change min()/max() to lca().

        also, have lca(leaf, non-leaf) = leaf to get lca of leafs only.

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

          for computing lca(a, b) use any standard way.

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

            oh, nice method, I have never done a problem like this before. Also did you solve all the problems XD

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

            in the first sample case my ans[-1,3] AC->is [-1,5] but lca(3,5) is 3 then why 5 is considered?

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

              Because only the lca of leaf nodes having the label within the given range is asked,you are finding the lca of a internal and a leaf node.

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

    I think it is possible to solve it without LCA using in time and exit time.Then the problem reduces to binary search on a segment tree which is more memory efficient than normal LCA.

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

can anyone please explain problem statement of problem 1 , i could'nt even understand problem clearly , i tried hard to understand but couldnt ..plz explain anyone..

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

This is problem 4 — Problem

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

How do you guys come to know about these contests? Can anyone participate?

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

    LinkendIn and Codenation social pages.

»
3 months ago, # |
  Vote: I like it -20 Vote: I do not like it

I solved P2, P3 and P6 is there any probability I may get a call?

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

    Depends on how many people gave the test and how many peeps CN are going to interview, which might be revealed in some days.

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

      Hey, did you got any response or anything? If yes, please let me know.

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

        No i couldn't solve that many problems to expect a response :(, also i am not sure if they will even hire from this test because of all the cheating and since they are hiring through codechef as well.But for a more sure answer you can ask ashishgup.

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

        So I was wrong, people who solved at least 4 did got interview calls.

»
3 months ago, # |
  Vote: I like it -46 Vote: I do not like it

Will I get the internship interview opportunity ? I solved first 3 Questions. Ashishgup

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

can anyone post the solutions of problem 4?

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it -26 Vote: I do not like it

    The comment is hidden because of too negative feedback, click here to view it

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

Are the problems available for practice on any platform?

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

Can someone explain 5th question solution in a more detailed way? It will be better if you can mention the required mathematical concepts properly.

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Ashishgup, could you please tell whether the testcases on which the solutions were tested at the time of the contest were only pretests or full testcases.

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

    So will the answer for fifth problem just be the bitwise OR of all the numbers according to the second solution you explained

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

      No it won't be just bitwise OR of all numbers (I actually implemented this during contest and got WA xD) Let's say for some bit B you can have a situation of not having an element whose highest set bit is B , and provided that B is set in some elements.

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

      Consider the case 3,6. The answer is 8 but the bitwise OR is 7.

      (In particular, the answer will be equal to bitwise OR if all non-zero bits are linearly independent)

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

Can someone please elaborate if there is anything wrong with the following code for 1st problem(rectangular field) as the following code gives 45 answer for the first testcase (although the answer is 65 as shown above)but still this solution is accepted on online platforms?

include

include

using namespace std;

int n,m,P1[500][500],P2[500][500],FR[501][501],FC[501][501],dp[501][501];

int main(){ while(1){ scanf("%d %d",&n,&m); if(n==0) break;

for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%d",&P1[i][j]);

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%d",&P2[i][j]);

    for(int i=0;i<=m;i++) FR[i][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            FR[i][j]=FR[i][j-1]+P1[i-1][j-1];

    for(int i=0;i<=n;i++) FC[0][i]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            FC[i][j]=FC[i-1][j]+P2[i-1][j-1];

    for(int i=0;i<=m;i++) FC[0][i]=0;
    for(int i=0;i<=n;i++) FR[i][0]=0;

    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            dp[i][j]=max(dp[i-1][j]+FR[i][j],dp[i][j-1]+FC[i][j]);

    printf("%d\n",dp[n][m]);
}

return 0;

}

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

i solved 2 problem can i get shortlist

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

can anyone provide the contest link so I can practice the problems?