I am getting SIGSEGV for the this problem. The solutions are as follow
http://www.codechef.com/viewsolution/6007537
In this I have used for the memory allocation for the variables…the approach is mentioned in the comments itself …And the other one is :-
http://www.codechef.com/viewsolution/6009342
Here I have used the same approach but with name of the variables as it is…Thanks for the help !!
The problem in your code is: the ids are not necessarily in the range 50,000. Say, the id is 10000000. Then your code will try to access the location which is undefined as per your code. This is giving you RTE. Also, whenever you are declaring large-sized arrays, go for heap allocation (global), not the stack one(local).
Also,
Why are you declaring the two arrays? We need just one, for counting. See this:
map<in,int>count; // I am using this map for counting.
count.clear();
int n1,n2,n3,ele,i;
scanf("%d %d %d",&n1,&n2,&n3);
int max=0;
while(n1)
{
scanf("%d",&ele); // taking input using just one single variable ele
count[ele]++;
if(ele>max)
max=ele;
n1--;
}
while(n2)
{
scanf("%d",&ele);
count[ele]++;
if(ele>max)
max=ele;
n2--;
}
while(n3)
{
scanf("%d",&ele);
count[ele]++;
if(ele>max)
max=ele;
n3--;
}
int ans=0;
for(i=1;i<=max;i++)
{
if(count[i]>=2)
ans++;
}
printf("%d\n",ans);
for(i=1;i<=max;i++)
{
if(count[i]>=2)
printf("%d\n",i);
}
I used map because I am currently unaware of the fact how much memory I need. The memory I need is the maximum ele I’ll get above. I can simple declare an array of 500001 and get the task done but the dynamic allocation is handled much more efficient way in map. Lets say, the mapp first allocated n1 amount of storage, but when it needs the space beyond n1, it allocates 2n1 storage, copies the first n1 in this new 2n1 storage and then works upon storing elements beyond n1(if taken amortized, this happens in linear time). Thus, it is more better in my terms. Lets me know If I am wrong somewhere…
@damn_me, just to save my writing time I used two arrays…That’s why I gave the link to the second one too…and yes I will try this with map approach…thanks for the info …
But I have one doubt , it will be great if you clear it :-
What if the memory allocation by map after it encounters the highest element is greater than the memory allocated to program ?? I guess it will also generate SIGSEGV
Yes, that will generate SIGSEGV. But the memory allocated to a program is and must be in accordance with such situations. I think online judges are made to handle such situations. Its just the matter of fact of reusability, the space which map used earlier will be destructed and is now re-usable. That’s why dynamic allocation handles the given memory in a better way.
See the edit, RTE in your code is not because of memory size but because of array index out of bounds exception which your code throws.
@damn_me … I got you …Will try this approach …IF you know any other approach to this problem other than this please do share …THANKS FOR YOUR EFFORTS
nickzuck_007 Your approach is correct, the only points you are missing is the fact that range of ids is not the same as that of the range of n1,n2 or n3 given. Any other approach will have the other way of using the possible various data structures. I hope you got by my RTE point, if not, you may ask here.
I understood each of your points perfectly …Thanks for that …But I was asking for some other approach (ofcourse via other DS) …It would be great if you name on or two for this problem
One technique is we can store all numbers in one array and then sort them and in linear time, we can find which are repeating and which not. That’ll not add on to the space complexity for the count array we are doing. If you want to use sets, then insert the pair(element,count) in the set. Whenever you take input, search(Logn time) for that input number in the set, if found just increase the count, if not, insert the new pair(inp_element,1) as the new pair in the set.
Or you may create a structure having fields(element,count) and create a linked list or insert a struct node, insert in some vector or set and then iterate…