codenationtest's blog

By codenationtest, history, 5 years ago, In English

Please use this thread to discuss the problems of CodeAgon 2019.

Q1 : Represent N as sum of minimum numbers ending with 9. eg 28 = 19 + 9, 27 = 9 + 9 + 9.

Q2: Make frequency of each digit even and minimize the last — first deleted numbers index difference.

Q3: Maximum diameter of tree where parent of x = (x — x&(x-1) ). ie last bit unset.

Q4: array of site n, multiply or divide(if possible) by k any number of times. return minimum (MAX — Min) element of modified array.

Q5: online queries of type 1) change value of index x to v. 2) sum of all values with index <= x Q <= 1e5 x <= 1e18

Q6: return max product of size of 2 non intersecting palindromic substring. required in O(n).

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it

The third problem said 1<=N, however there were definitely cases in which N was equal to 0. Many wasted quite some time because of this.

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

    floor(log2(n+1))+floor(log2(2(n+1)/3)) Is this the answer for third problem?

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

      You can try comparing the output you get with the output this code gives you and find out https://ideone.com/jQ3whW (not my solution), my approach was different so I can't comment on the correctness of the equation you gave.

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Where can we see the standings?

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

    I don't think it is possible to view standings as of now. How many did you solve?

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

      first four

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

      Then when are they going to display the standings?

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

        Most probably never as they have intentionally changed the interface(more like hiring contest) this time where you can't see standings.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone solve the last one?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +20 Vote: I do not like it

    It looks like straightforward manacher's algorithm to me.

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

      I solved it with Palindromic tree :)

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

        How did you handle the only odd length palindrome condition? Did you remove the type — 2 root?

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

          toxic_hack If the length of maximum palindromic suffix ending at index i is even, and the length of palindromic suffix ending at index i with odd length is x, there always exist a index j before i where length of maximum palindromic suffix ending at j is odd and >=x

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

            How can you prove this? Seems like complete magic to me.XD

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

    For every index $$$i$$$, calculated maximum palindrome length if this is the center element of that palindrome using binary search and hashing.

    Updated in two lazy segment trees, maximum possible length of palindromes ending at a position and starting from a position. After that, it is straightforward to calculate best possible answers for each position. Could not debug in time, just passed 17 of 29 test cases.

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

      You don't need lazy segment tree for the later part.

      Suppose you have the array $$$d1[i] = \text{maximum length palindrome centred at i}$$$, then to find $$$mx[i] = \text{length of maximum length palindrome starting at } i $$$, we need to know the furthest center of a palindrome possible from i, that can be done by two pointers.

      Spoiler
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    You can do binary search and using string hashing find max length considering this index as a center.

    Build a prefix max and suffix max array where prefix(i) denotes length of longest string which is palindrome and has a ending point <= i. Suffix(i) denotes length of longest string which is palindrome and has a starting point >= i.

    Iterate over all index and update answer. Ans = max( Ans, pref(i)*suff(i+1) )

    If you want, I can elaborate on how to build the prefix and suff array.

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

      It would be really helpful if you could elaborate on building the prefix and suffix array, I have an intuition it requires building the longest prefix suffix array, but can't really use it to find what the question wants. Thanks in advance.

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 3   Vote: I like it +3 Vote: I do not like it
        ` Let Arr[i] denote the maximum length palindromic string considering ith element as center. `
        
        ` Let pref[i] denote maximum length palindromic with last index <= i `
        ` We can build pref[i] array in following way. `
        for( int i = 1; i<=n; i++ )
              pref[i+Arr[i]-1] = max(pref[i+Arr[i]-1], pref[Arr[i]] ) 
        
        ` For ith index we can make pref[i+1]-2 length pan ending here ( removing first and last element from pref[i+1] ) `
        for(int i= n-1; i>=1; i--)
              pref[i] = max(pref[i], pref[i+1] - 2) 
        
        ` Taking prefix max `
        for(int i=2;i<=n;i++)
             pref[i] = max(pref[i], pref[i-1])
        

        You can build suffix array in similar way.

»
5 years ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

In 5th question I used simple BIT (point update and range sum query) with map but was getting TLE for large x.
How to optimize it?

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

    You can use dynamic segment tree to solve this problem, which is nothing but a trie like implementation of segment tree. Refer the last point of this blog for implementation.

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

      Was there some more optimization in it ? Because dynamic segtree was giving tle for range 1e18 .

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

        Just creating exactly the nodes with data in them, and not using long long for every variable converted my TLE to AC.

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

For second binary search on length is the way to go?, And can someone give some idea about 4

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

    Insert all possible values in a min-heap/multiset with indices. Suppose, in the beginning, there is nothing at all indices. Continuously pop-out values from the multiset, at each instance the popped-out value $$$X$$$ with index $$$i$$$ is the maximum and if at least one value has been popped out for all indices, the current answer will be $$$X-$$$min of (max of previously popped-out values for an index) for all indices except $$$i$$$.

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

      lets take an example 1 5000 9999 and k =10000 now can you explain with this example please

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

        Multiset will contain (1,0), (10000,0), (5000,1), (50000000,1), (9999,2), (99990000,2) in sorted order. First popped value (1,0), then (5000,1). Then, (9999,2) is popped, after which at least one value for each index 0, 1 and 2 has been popped out. With minimum of maximum of values at each index popped except 2 is 1. So, current answer is 9999-1.

        Then (10000,0) is popped out, then min of max of values at each index popped out except 0 is 5000. Current answer is min(ans, 10000-5000). Then similarly 50000000-9999, then 99990000-10000.

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Ashishgup please explain the solution to 5th problem.

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

    There were many approaches to solving the problem, but here is mine:

    For the subtask with Q = 1e5, X = 1e9, there was a very short Q log^2N code using a BIT (Map instead of array): http://p.ip.fi/trAf

    Whereas for the full version with Q = 2e5, X = 1e18, there was a Q logN code using approaches like dynamic segment tree or tries. I personally used tries because I find it easier to code: http://p.ip.fi/FG_F

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

      Can you please explain how you are storing the sum and querying it. And if you can share some problems like this.

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

      Allow me to explain the amazing approach of Ashishgup. First of all, now using dynamic segment trees or using sqrt decomposition seems to be overkill.

      Whoever is reading out this must try out problem of finding max XOR in an array using trie first then move ahead. A node structure representing a bit in trie would be like

      node
      {
      	node bit[2];
      	sum = 0;
      }
      

      The head of trie would point to the most significant bit. At each node we will store sum while we are updating. Lets say $$$110010$$$ and $$$110110$$$ has come then in our trie, at $$$3rd$$$ node we are actually storing sum for both of numbers with same pattern of bits before it.

      Insert PseudoCode

      Now, while querying we will traverse through bits/nodes of $$$X$$$(the input) and whenever its $$$ith$$$ bit is $$$1$$$ we will add sum stored in corresponding node for $$$0th$$$ bit. This is because we are assure that if $$$ith$$$ bit of $$$X$$$ is $$$1$$$ then all numbers whose $$$ith$$$ bit is $$$0$$$ will be smaller than $$$X$$$.
      Remember we will not do this when $$$ith$$$ bit is $$$0$$$. This is easy to prove. This is left as a task.

      Query PseudoCode

      I hope this makes sense.

      Thank you

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

      if unordered_map was used,would it still be tle. but very cool trick, using map in bit, saw it first time.what other places could we use map instead of array, like segtree.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve 4th ??

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

    Find all possible numbers at each index and then this

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

      If array is {5,6,2} and k=3, which possible numbers will you store for first index? I mean how many times will you multiply a number by k and store it?

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

        You'll multiply once as it will become divisible by k

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we solve the second question using two pointers?

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

    Yes, using the sliding window technique.

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

    Yes, we can solve it using two pointers.

    Approach
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please tell how to code this?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +26 Vote: I do not like it
        Code
»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Had issues with the compiler of 4th question. Did anyone else have?

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

    There was some issue with the Sample test case. However, if you use custom input or run all test cases, then test cases run as intended. Also, does anyone know when will we be able to see the rank list?

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Its embarrassing to ask but how to approach the first question? I tried a greedy solution but it was failing

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

    First of all you have to look at the last digit of the number, it will directly tell you the answer of the question (if it exists). How ?

    Because the last digit of multiples of 9 follow the repeating pattern :- 9, 8, 7,.. 2, 1

    For eg. if n = 357, you can say the answer is 3 because 9 + 9 + 9 = 27 and guess what you just have to change the one number of these three. Like 357 = 339 + 9 + 9.

    Now you should also check for whether answer exists. For that, first find the expected answer, say x and substract (x — 1) * 9 from n and if it is less than 9, the answer doesn't exist.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what wrong with my 3rd solution only getting 9 testcases AC . my solution is x = log(n) , p = pow(2,x) remain = n-p+1 , second = log(remain) ; ans = max(2*x-1,second+1+x)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to approach 4th question ?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How many questions did you guys solved? Trying to get a little idea about leaderboard here. I solved 4 completely and 5th one partial

»
4 years ago, # |
  Vote: I like it +40 Vote: I do not like it

codenationtest Ashishgup Enigma27 When are the results out? In case, you have already contacted the shortlisted participants, we would really like to see the leaderboard as it was also a prize-based contest and transparency is expected.

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

    Why are you tagging these persons. Did they organise the contest

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

      If anything is related to India, Ashishgupta needs to be tagged. Its mandatory.

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

      I assumed they were the problem setters as they were active in this blog and are associated with CodeNation. I apologize if they aren't involved in this contest.

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

        I was not the problemsetter.I participated in contest same as you. AFAIK top 20 contestant have already been contacted for prizes. They contacted me for the interviews but I think that was from their previous pool-test.

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

          Oh! Btw, how many did you solve? And were you in the top 20 contestants?

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

            I solved 5 problem and took partial in 6th. There are more than 20 people who solved all the 6 problems.

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

    geeky.ass How many did you solve?

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

      I solved the first 4 completely and got partial points in the 6th problem. How about you?

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

Did someone get a call from codenation?