Posts by nitin1

i want to do topo sort but i want to output the lexographically smallest topo sort vesion of that. http://www.spoj.com/problems/TOPOSORT/ here goes the link of problem. actually, i have done this using DFS , but i am able to do the question "print any possible topo sort" of the graph. thanks if u can help me.

void dfs(int p)
{
      if(used[p]==1)
      {
                  flag=false;
                  return;  
      }
      else if(used[p]==0)
      {
             used[p]=1;

             for(int i=0;i<g[p].size();i++)
             {
                  dfs(g[p][i]);
             }

             used[p]=2;

             ans.push_back(p);
      }
      else
      return;
}

here ans vector is the answer in which topo sort is there. thanks if u can help me .

If you consider any multiple of 3 and then sum up its digits, the sum is always divisible by 3. For eg. 843 is a multiple of 3 and 8 + 4 + 3 = 15 is also multiple of 3. Similarly, for 9, any multiple of 9 satisfies the property that the sum of its digits is also divisible by 9.

But he suddenly realized that this property for 3 or 9 in base 10 may not hold for another base (let say 11)

Inquisitive, that he is, he wants to know the number of digits for which this property holds for a particular base non trivially.

For 0 and 1, this property holds trivially and thus can be ignored.

A base is the number of unique digits, including zero, that is used to represent numbers .

i am unable to get it... please give some hints.

sorry, if i making it chaotic, but i want to ask one thing, when i write g=s, then s has 3,4,5,NULL and then why dont string g do it like this, 3,4,5,NULL,NULL(last NULL is the NULL which class object itself provides which you said is kept by class which is of no use). thanks. P.S i am thinking that i am irriating u nothing else. :( sorry!

yes, now you are very clear. but one more question, i have read somewhere that string (c++) don't have null at the end. and if you want to have null at the end , then use it as g.c_str(), then you will null at the end like in C array. can you throw somwe light on that ? thanks a lot.

yes, i know it is equal to number of characters. but when i write g=s and when i write g+='\0'; it give me 3 and 4 respectively. why does it happen.

secondly, i am saying it is rejecting null when i write g=s because again i am appeneding some string with it and it still take it. that mean it dont have null at the end as usual, that y string got append with it, otherwise it will not appened. and that y i have asked why it has rejetced null in g=s ? doesn't the size() function stops when i get NULL character ? thanks.

yes, u r correct. but when i print the g.size() after g=s. it gives me 3 and when i do g+='\0'; and then print g.size() it give me 4. but when i write g=s and s already have NULL with it, then why is it giving me 3 rather than 4 ?(because there are 4 charcters in strins g). i hope i am clear in my doubt. thanks.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include <cstdlib>


using namespace std;


int main()
{
     char s[5];
     string g;
     int p=345;

     sprintf(s,"%d",345);

     g=s;

     g+=".mp3";

     cout<<g<<endl;


     getchar();
     return 0;


}

I have a very small doubt about strings. this is code snippet i have shown. when i have called sprintf(), then it has changed 345 to string with NULL character at this end. right ? so when i equalize g with s, then it is also = to 345. but qstn is that why string is rejecting NULL at the end ? and what can i do if i want to have a NULL in the g when i am writing "g=s". please help me if u can. thanks. (i am just learning all these things, not a experieced C++ programmer).

sir, can you tell me that how can i optimize my code so as to reduce the memory consumption ? because in my ocde, i am using 26 pointers on each node which is very costly if string is too large. can you tell me any way to optimize it further ? thanks .

hats off !! out of world code!! 101% readable and understadable in one go. sir, yes! i come to know about my mistake now . thanks. i know i am doing a very stupid mistake, but still i wana ask. when i am on root which has 26 pointers and all NULL. then i have made temp to go to one of that 26 pointers. okay? then after allocating memory to it, why not it is made part of the complete tree (because that child pointer is also part of tree). thanks alot.

#include<iostream>
#include <cstdio>
 #include<string>

 using namespace std;
typedef struct node node;

struct node
{
       int value;
       node * child[26];

}*root;


node * newnode()
{
     node * nn;

     nn=(node*)malloc(sizeof(node));

     nn->value=0;

     for(int i=0;i<26;i++)
     {
            nn->child[i]=NULL; 
     }

     return nn;
}

bool insert(string s)
{
     node * temp=root;
     bool xx=false;

     for(int level=0;level<s.length();level++)
     {
             int index=s[level]-'0';

             temp=temp->child[index];


             if(temp==NULL)
             {
                           cout<<"here"<<endl;
                        temp=newnode();
                        xx=true;                 
             }

             if(temp->value==1)
             {
                         return false;      
             }
     } 

     temp->value=1;

     if(xx==true)
     return true;
     else
     return false;
}

int main()
{
    root=newnode();
    string s;
    int n;
    int t;
    bool p=true;

    cin>>t;

    while(t--)
    {
           root=NULL;

           root=newnode();

           cin>>n;
           p=true;   

          while(n--)
          {    
              cin>>s;

              if(p==true)
              {
                  bool z=insert(s);

                  if(z==false)
                  {
                         p=false;     
                  }
              }

              if(root->child[9]==NULL)
              cout<<"nnnnn"<<endl;

          }

          if(p==false)
          {
                      cout<<"NO"<<endl;
          }
          else
          cout<<"YES"<<endl;    

    }


    return 0;
}

this is my code for tries. i am allocating memory to each node in the insert function. but when i check that it is value of the inserted node is null, then it says yes. problem is in insert function. i am calling this from main(). when i have inserted one string, then it should insert it again. please see whats can be the solution. thanks. i am entering "911" 2-3 times. and it is saying that root->child[9] is till NULL, which should not be there. thanks

the extent of knowledge which people on daniweb has is incredible. they are GOd of thier subjects. it is a boon to me by god when i came across the daniweb. :-) thanks to all of you. :-)

sir, please tell me that can i say both map and set as associative arrays ? i have read this and seen that associative arrays have key,value pairs (like map). but set don't have value , then why are they called associtiave array ?

secondly, map are implemented as Red-black trees. right ? that mean map don't hash the key but unordered_set hashes it. can we have a attached value with unordered_set ?

thridly, i have read that hash tables are used to implement assoctiave arrays. but again , i saw that maps are assoctive arrays, but map dont use hashing. then how hash tables are used to implement assoctive arrays? thanks.

we can say that set (ordered or unordered) are MAINLY used for look-ups ? and i have a big advantage with set(ordered) that they are arranged in sorted order when i will traverse it. am i roght ?

secondly, if can i have a set of structre ? if yes, then how will it check for uniqueness ? thanks.

if i iterate it, then will they be in any specific order ? (as u said "in order"). please throw some light on that. thanks for this help.

unordered_set<string>mm;

what can be the use of it ? just i am inserting the strings and then in future i can check that i have added it already or not ? that's all ?

secondly, how does it save the collisons ? i mean if it hashes the values , then collisions will be there for sure.in short, i am asking that it this always reliable to use it ? thanks

sir, i know that codes are really tuff to understand. but i was willing to know just about basic working. like, when you u have told me about map in STL. (they are implemented as red black trees and they have logn complexity and all..). so , i want to know how unordered_set works and does it hash the values or not and how it retrive the results for queries. thanks

i have already read out this. i want to knoe the working or some knowledge about its implementation. thanks

can anyone please explain me in brief that how exactly this container work ? or can u giveme some link of this. i have tried to look on some links by google, but i am not much clear about my doubt. please help me if u can. thanks.

but when i add all the characters in the string s, and print afterwards, then again even it's sizeof(s) prints 4. now why this happen ? thanks

ohh yes!! but can you tell when i declare string s, isn't it itself a pointer ? because it's size(s) will return 4 which is pointer size i think . can you clearify this thing ? and if it is pointer, then why do you still need to use c_str() ? thanks

"in case you're stuck with a function that wants an array of char instead of a proper string object." can you explain it again ? didn't get this line . Secondly, your link has no text in that, please check it. thanks to you.

i am learning C++ from a good time now.. but I am still very confused sometimes in the use of array(char) and string.. can anyone please tell me that what exactly all differences between string and char array ? what can i do with array which i can't do with string and vice-versa ? searched google alot but on each place something confusing is written. thanks in advance to you.

that mean when i find that i have already visited this node , then i have to use a linear search that where the node is( which is included in cycle) ? right ? linear search will be costly in my case.

how can i print the node number included in the cycle and how will i find the length ?

i have a undirected graph and i want to print a cycle with length >=k (given) , can you suggest me a algo ? i dont want any code, snippet. i am hoping for hint and algo for this. thanks. it is guaratned that cycle of length >=k exists.. thanks.

and my first question ? is_less is a structure, how have you used it as function ? and i know that () is used for function calling and how structure and () are interlinked here ? thanks in advance.

two questions in my mind now,
Firstly, is_less is a structure, how have you used it as function ? and i know that () is used for function calling and how structure and () are interlinked here ? seconldy,

In the statement , key< str.key , "key" is which key here ? i mean in the one object of structure, you are comparing it with which key ?

P.S May be these questions are stupid, but as i have started to learn C++, these things puzzling my mind. thanks in advance to you.

i am the one who has given this idea :-) ehhe... me feeling damn good.. my idea made something changed on daniweb like website .. feeling great.. thanks.

it can be anything.. like any structure or something like that. why does it depend on data type ?

it is really awesome. actually i have given this idea :p and i have some credit in adding this feature to daniweb. (just kidding). in reality, programmers are really great who are behind all these things and whole crdit goes to them. hats off..

P.S who is the programmer who do all these things ? lemme guess, is he deceptikon ? :-D thanks. good luck!!

yeah, all the things which i have written above are read from this link only. somewhere they have overloaded '<' and some where they have overloaded '()'.. why is it so ? thanks in advance.

can anyone please help me in the sort function ? i have read that there are 3 way to use sort().
1. use sort(v.begin(),v.end())
and second is sort(v.begin(),v.begin()+n, cmp)

then in cmp i can have 2 varaitions,

2.a : cmp as the function (it is okay with me)
2.b. here , can you tell me that how "operator()" is overloaded ?

like they have declared a struct and then they have overloaded "operator()" . what is this "operator()" ? can you please xplain me? searched it alot but didnt get anything. thanks.

actually, I am new to C++ , although not new to programming. i have a vector of pairs ,

vector<pair<double, pair<int,int> >>

and i want to sort it in incresing order. for simplicity, i am using sort() inbulit function. does pair has ibuilt '<' operator ? or we have to override it ? if yes, then how will cmp will be declared ?

x,y are coordinates of a point and double is their polar angle. and i am doing this sorting so that after sorting the points are in the order which will make a polygon. thanks if u can help me. any help will be appreciated.

actually in my placaments, apti has first round in which they ask logical reasoning and quantitative and many things like that. so from should i join a coahing for this or do myself ? please help!!

i want to practise blood relations problems, venn diagrams, series, analogies, puzzle test, decsion making and topics resembling to them. can you suggest me a good book for these topics. they are covered under logical reasoning. please suggest the good book which you have come acrossed. thanks.

ohh... multimap is just an map having second argument as vector , can i say this simply for multimap ? and secondly, in C , this is really going to be a difficiult and time taking task so implement our own tree in time constraint ? thirdly, and sir, the space used in map is the sum of spaces used ny keys + values or does it take more than that ?

how does it hash each value to a differnet location ? i hope it will definitely have collision problem. yes! i knoe about red black trees. AVL trees can also be implemented using this ? thanks sir.

map<string,int> M is really an awsome thing. learnt today from book which you told me one month back. yipeee.. :-) don't know how map work ? how it hash the keys ? secondly, can i say that it is good to learn C++ for these types of implementaions ? because in C, they are very tuff to do in limited time. thanks in advance.

i have an array of strings (2D array). i am taking input of strings and that strings can be same with strings which i have inputted before that string. so i want that i don't enter that string which is already being taken into array. so how can i do this thing in my code ? using linear search is costly in my case. thanks in advance.

yeah! i was going to ask that which you have already answered. :p yes! it admit which u said truly. no offense! but sir, tell me that at this level and the experience which i have , what can i do so that i develop skills which is needed in a PROFESSIONAL programmer ?

P.S i was thinking that i will be professional when i will join any big company like amazon, google or somthing like that. was i right in my thinking ? thanks

yeah!! O(n) is the best complexity for this concept. okay! sir, according to you, contests don't improve a person ? i am not arguing, even i am asking you because may be i am wasting my time by attending contests. shouldn't i focus on perfomance ? till which level contests helps one to become a professional coder like you ? (not coder, i would love to say SOFTWARE DEVELOPER ). THANKS.

no sir, thanks for this code. but i have implemented O(nlogn) approach. using bubble sort is nnlogn i suppose. main part is how we sort it so as get the bext complexity possible. for all contests, this approach is much. using bubble sort will give time limit exceeded. i have already implemneted it before you give this post. thanks sir :-)

@gonbe okay thanks for judging my code. i want you to just have a jist of this code and algo of suffix array and i want you to give a "poor" free code and with full description of code and with "C" as the language. thanks. and i wonder if you can do it. :-)

suffix array is ultimate data structure for string problems. yes! this code is working fully and 101% correctly. (i can say this with full certainity). for searching the string suffixes, for sorting the suffixes of atring, for finding the frequeny of a substring in a string and many others. try to search and you will see the magic of suffix array. if you get what it's all about, you will find this code as the easiest one for suffix array. believe me, i have read about 50 links including articles, pages, wiki, topcoder , spoj forumns. and build this code. codes which i found were very tuff to understand. according to my level and as a beginner in this, this is simplest code sone can have for suffix array. thanks.

how can i remove my given code snippet i have submitted ? i dont want any more negative votes to my code. thanks

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 10000000
#include<stdlib.h>
#include<string.h>

char s[MAX];
int p[MAX];
int bucket[MAX],nbucket[MAX];

struct suffix
{
       int idx;

}pos[MAX];

int H=0;


bool cmp(struct suffix i,struct suffix j)
{
    if(H==0)
    {
         return s[i.idx]<s[j.idx];    
    }
    else
    {

          if(bucket[i.idx]==bucket[j.idx])
          {
              return bucket[i.idx+H]<bucket[j.idx+H];                            
          }
          else
          {
               return bucket[i.idx]<bucket[j.idx];
          }
    }

}

bool cmp1(struct suffix *i,struct suffix *j)
{
     if(H==0)
     {
           if(s[i->idx]==s[j->idx])
           return true;
           else
           return false;  
     }else{

     if(bucket[i->idx]==bucket[j->idx] && bucket[i->idx+H]==bucket[j->idx+H])
     return true;
     else
     return false;
     }
}

int update(int l)
{
     int id=0,start=0,c=0;

       for(int i=0;i<l;i++)
       {
             if(i>0 && !cmp1(&pos[i],&pos[i-1]))  
             {
                    id++;
                    start=i;
             }

             if(i!=start)
             c=1;

             nbucket[pos[i].idx]=id;
       }     

       memcpy(bucket,nbucket,4*l);

       return c;
}

void suffixsort(int l)
{
     int i=0;
     int c=0;

     for(i=0;i<l;i++)
     {
        pos[i].idx=i;             
     }

     sort(pos,pos+l,cmp);
     c=update(l);

     for(H=1;c;H*=2)
     {
              sort(pos,pos+l,cmp);      

              c=update(l);
     }

     return;


}

int main()
{
    gets(s);
    int l=strlen(s)+1;

    suffixsort(l);

    for(int i=1;i<l;i++)
    printf("%d\n",pos[i].idx);

    return 0;
}

means ? stackoverflow.com ? can you give me link ? actually, it work so slowly, when i made any changes and run, it take too much time to run the app. i can't resist if it take 5 minutes for running it single time... please help!

are you sure in this the problem ? i have friends working on even 1 GB ram ?

okay! i have download the full pack of android bundle from offical site of android. lemme give the link so as to tell you. http://developer.android.com/sdk/index.html

secondly, i am using windows 7 ultimate with 2 GB ram and 500 GB hard disk.

i have just downloaded that bundle from that link and run eclispse from the folder in the unzip form of that unzip file downloaded. then i just follow the tutorial give on the same site and run the app accoringly. and when i run that app, though it is running but it is giving me the errir again and again. thanks.

thridly, i have used the default settings while making the AVD. 512 MB ram and google nexus and suitable name needed while making that AVD. thanks.

started learning android now.. ^_^ and will start a project in next 3 days.

@tech-ultrasonic What exactly do you mean in SEO ? do you mean it's implementaion or something like that ? can you elaborate ? thanks.