ologn_13's blog

By ologn_13, 12 years ago, In English

Hi all!! The problem is related to searching the k-nearest neighbor of a point in 2-D co-ordinate system. Inputs are given in form of (x,y) coordinates and we have to find out k-nearest neighbor of a point. I search thoroughly on internet, but I got only pure theoretic algorithms in term of searching points in a hypothetical sphere. I also read that it can be solved using k-d trees, which I learn, but I am not getting how to implement the algorithm. Please help, if anyone have implemented it before or had a look at its implementation earlier. Thanks!

Full text and comments »

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

By ologn_13, 12 years ago, In English

Hi all! I was solving this problem:- We are given a weighted directed graph. We have to find the route with minimum length and it should visit all the nodes with a node not visited more than once. Please help in tackling it!! Thanks for reading it.

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it

By ologn_13, 12 years ago, In English

hi all!The problem is An interesting subsequence(May challenge). My solution is giving runtime error on submitting but when i tested on codeforces(custom test),ideone and on my pc, it give correct answer for all of these!! why this is so??? help please..my code is here.

Full text and comments »

  • Vote: I like it
  • -5
  • Vote: I do not like it

By ologn_13, 12 years ago, In English

Hi guys!! I was solving the problem of finding LIS of a given sequence. I had built the code for getting the length of LIS but now i am a bit confused in finding a LIS(any one)...please tell the modifications which should be done in following code (or the algorithmic modification). Thanks!!

#include<iostream>
using namespace std;

int Binarysearch(int*a,int c,int d,int key)
{   if(d<=c)
    return c;
    if(a[(c+d)/2]<key)
    { c = (c+d)/2 + 1;
      return Binarysearch(a,c,d,key);
    }
    else{ d = d-(c+d)/2;
          return Binarysearch(a,c,d,key);
    }
}

int main()
{   cout<<"Size: ";
    int n;
    cin>>n;
    
    int a[n];
    for(int i=0;i<n;i++)
    cin>>a[i];
    
    int end[n];// Storing the end elements of the sequences formed till now.
    
    end[0] = a[0];
    int len = 1;
    
    for(int i=1;i<n;i++)
    {
      if(a[i]<end[0])
      { end[0] = a[i];
        continue;
      }
      else if(a[i]>=end[len-1])
           { end[len++] = a[i];
              continue;
           }
           else{
                 // Binary searh in end[] for smallest element greater than a[i]
                 int c = 0;
                 int d = len-1;
                 int j =  Binarysearch(end,c,d,a[i]);
                 end[j] = a[i];
                
                }
      
      }
      
      cout<<"Size of Longest Sequence:- "<<len<<endl;
      
      return 0;
}
      
              
    

Full text and comments »

Tags lis
  • Vote: I like it
  • -4
  • Vote: I do not like it

By ologn_13, 12 years ago, In English

Hi all.. I have read about probabilistic primality testing algo's but i want to know about an algo which is deterministic in its approach and which can be coded faster in competition arena(also it should be less confusing in implementation!!) and with best time complexity for larger numbers like 10^20...**please help here** because I got wrong answers most of the time due to long implementation of code and it makes internal steps little bit confusing.. Thanks for reading it..

Full text and comments »

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

By ologn_13, 12 years ago, In English

Hi all! I have been caught in this problem from past few hours....my thoughts are in following way:- first we'll do DFS and store number of nodes in the subtree rooted at every node..after this we would take all these numbers in sorted order and iterate from both sides(start and end) and print each pair till we reach middle..but this won't work if more than 2 subtree has same number of nodes.....please help here... or please discuss if there is any other simpler way than this..thanks in advance!! [CUT] EDIT: The problem is solved. From here it was nothing but to just take an "OR" of all combinations possible from each node with overall array of possible combinations.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By ologn_13, 12 years ago, In English

Hi! this is an SRM problem on topcoder..i tried solving it using the property of periodicity of wins 'W' and loses 'L' along with the property that result for a particular position(number of coins left) depends on atmost k position back..k is the maximum number of coins a player can pick..my question is how to decide the periodic length "q" for a given set moves[]..so that I will not iterate all over to MAXN and just use periodicity of this string with length "q"..

Full text and comments »

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

By ologn_13, 12 years ago, In English

Hi all! This is a problem asked on facebook interview....

There are many intervals each defined by pair containing a starting point and a ending point (si, ei). Two intervals i1 and i2 are called nested if i2 lies completely inside of i1. Example:- (2,6) and (3,4) are nested, since (3,4) is a part of (2,6). Similarly k intervals i1, i2, i3....ik are called nested if, i2 lies inside i1, i3 lies inside i2, ...and so on. Determine size of largest set of intervals from the given intervals, such that all the intervals in that set could produce a nesting.

I thought it in following way:- Let us take an e.g.- (0,7) (0,5) (1,21) (1,9) (2,8) (2,4) (3,20) (4,16) (5,15) (6,21) Sort it in the way such that a[i-1]<=a[i] && b[i-1]>=b[i] Than starting from first interval we start a linked list.. if the next interval comes inside a interval we move down the node and traverse the graph created down the node(other than main list)..we store the pointer of the maximum level node in this graph at which the new interval can fit.. and traverse further in linked list to see under whom the current interval comes.. at last we have a pointer to a node with whom we have to attach the current interval.. and compare the level of this node with the maximum level we already have..... The final value of maximum level is size of maximal nested intervals set..

complexity of above solution is likely to be:- O(n(k+l) + nlogn)

I guess it is difficult to get it this way, but I have no other option... if anyone got other algorithm.. please explain it...thanks!!

Full text and comments »

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