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

Автор codenationtest, история, 7 лет назад, По-английски

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

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

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +23 Проголосовать: не нравится

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.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

Where can we see the standings?

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

Did anyone solve the last one?

»
7 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +9 Проголосовать: не нравится

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?

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

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

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

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

    • »
      »
      »
      7 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, скрыть # ^ |
        ← Rev. 3  
        Проголосовать: нравится +3 Проголосовать: не нравится

        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.

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

Ashishgup please explain the solution to 5th problem.

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +37 Проголосовать: не нравится

    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

    • »
      »
      »
      7 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

      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

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

      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.

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

How to solve 4th ??

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

Can we solve the second question using two pointers?

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Yes, using the sliding window technique.

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +12 Проголосовать: не нравится

    Yes, we can solve it using two pointers.

    Approach
    • »
      »
      »
      7 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      Can you please tell how to code this?

      • »
        »
        »
        »
        7 лет назад, скрыть # ^ |
         
        Проголосовать: нравится +26 Проголосовать: не нравится
        Code
»
7 лет назад, скрыть # |
 
Проголосовать: нравится +24 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +13 Проголосовать: не нравится

    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?

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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.

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

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)

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

How to approach 4th question ?

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

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

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +40 Проголосовать: не нравится

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.

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

Did someone get a call from codenation?