10044 - Erdos Numbers

Krzysztof Duleba · Post by **Krzysztof Duleba** » Tue Oct 07, 2003 12:32 pm

Actually from the judge's reply it's not possible to tell whether abort() or terminate() function has been called. Terminate() is executed if an unhandled exception occurs.

BiK · Post by **BiK** » Tue Oct 07, 2003 7:58 pm

Is it possible that I crammed so much my containers that the program went out of memory and an exception was thrown? And since this exception is unhandled, terminate() is called, and instead of getting MLE, I receive RTE?

Krzysztof Duleba · Post by **Krzysztof Duleba** » Wed Oct 08, 2003 12:41 am

Yes, it is possible. You can try to add
[cpp]
#include <cstdlib>

#define safe_insert(map,pair)\
try{map.insert(pair)}\
catch(bad_alloc)\
{\
cout<<"out of memory"<<endl;\
exit(1);\
}\
catch(...)\
{\
cout<<"something else wend bad"<<endl;\
exit(2);\
}
[/cpp]
and use safe_insert(map_name, pair_name) instead of map_name.insert(pair_name) . It will help you to avoid unhandled exceptions. If OJ sends the error code, you will know what exactly has happened.[/cpp]

BiK · Post by **BiK** » Wed Oct 08, 2003 3:00 am

Thanks a lot. I'll try what you wrote. But before I saw the message I tried to organize my database (db) and map (m) more space-efficiently. However I could not compile the following function which is very strange to me:

[cpp]typedef set<string>::iterator iter;

set<string> allStrings;

void vectorToSet(int k, vector<string> &v, set< iter > &s) {
for(int i = 0; i < v.size(); i++)
if (i != k) {
iter it = allStrings.find(v);
s.insert(it); //compile error here
}
}[/cpp]

I decided that instead of keeping the strings in the containers (which I still think is not a problem since they are reference counted), I keep all the strings in the global set<string> variable allStrings and only iterators in the database (db), and the map (m). However, I could not compile the above excerpt. Any help please?

Krzysztof Duleba · Post by **Krzysztof Duleba** » Wed Oct 08, 2003 11:53 am

You're trying to insert a vector iterator (which is actually an ordinary pointer to string) into set of strings. Won't work. T is not *T.
All the collections in STL _copy_ their elements. So you can have the following code working:
[cpp]
vector<string> v;
new string * s;
*s="asdf";
v.push_back(*s);
delete s;
cout<<v.front()<<endl;
[/cpp]
Now I see why you're getting out of memory

This version does what you need:
[cpp]
vector<string *> v;
new string * s;
*s="asdf";
v.push_back(s);
delete s;
cout<<v.front()<<endl;
[/cpp]

BiK · Post by **BiK** » Wed Oct 08, 2003 3:48 pm

No you're wrong I try to insert set<string>::iterator into set<set<string>::iterator>. See the function vectorToSet. And it should be compiled.

Adrian Kuegel · Post by **Adrian Kuegel** » Wed Oct 08, 2003 4:14 pm

Try this:
[cpp]typedef set<string>::iterator iter;

struct mycomp {
bool operator()(iter a, iter b) {
return *a<*b;
}
};

set<string> allStrings;

void vectorToSet(int k, vector<string> &v, set< iter,mycomp> &s) {
for(int i = 0; i < v.size(); i++)
if (i != k) {
iter it = allStrings.find(v);
s.insert(it);
}
}
[/cpp]

Krzysztof Duleba · Post by **Krzysztof Duleba** » Wed Oct 08, 2003 4:25 pm

You can make a set of objects only if they are comparable with <. Set iterators are not. Try something like (works if all the strings are different)
[cpp]
class cmp
{
public:
bool operator()(const set<string>::iterator &i1, const set<string>::iterator &i2)
{
return (*i1 < *i2);
}
};

void vectorToString(int k, const vector<string> &v, set<set<string>::iterator, cmp> &s);
[/cpp]

BiK · Post by **BiK** » Wed Oct 08, 2003 9:17 pm

Thanks, really this was the problem. Now I compile the program but I get segment violation. I think it's because the set<string>::iterators get invalidated after an insertion in the set allStrings.

Since the problem statement (10044 - Erdos Numbers) does not specify any boundaries for the input, I thought that the perfect tool to use to solve the problem is STL. On the contrary it turned out a nightmare. Nevertheless I still want to make use of STL in at least one problem that I solved so please help me with any ideas.

Tahseen Mohammad · Post by **Tahseen Mohammad** » Wed Dec 17, 2003 7:34 am

Anupam

You are advising people to use the existing threads to keep
thing tidy at boards. Good Advice.

But why you yourself has creater a thread for p#10044 in
"other words" forum? It should be in forum "C".
And please use the problem number along with
the names. It helps in searching.

anupam · Post by **anupam** » Wed Dec 17, 2003 9:02 pm

Please specify the location. I will remove the post. In my case, I have to tell that, no one gave me the advice that i proposed here.

Tahseen Mohammad · Post by **Tahseen Mohammad** » Sun Dec 21, 2003 1:52 pm

It seems there is a lot of guessing going on about the input format.
Whether there is extra spaces before, after and within author names.

There is nothing like that. Input is precisely like that of sample.

So painful parsing is not necessary.

Tahseen Mohammad · Post by **Tahseen Mohammad** » Sun Dec 21, 2003 1:53 pm

Anupam,

You have create the thread regarding "Input limit of Erods number" in the
"other words" forum.

Give a search with erdos and you will find it.

anupam · Post by **anupam** » Sun Dec 21, 2003 8:16 pm

I have got the problem ac after rejudgement but now whenever i want to submit it for 2205 in archive it gives mle after mle and rte.
how can i fix the input size and ofcource my queue size.

--
thanks to all.
--
Anupam

Tahseen Mohammad · Post by **Tahseen Mohammad** » Mon Dec 22, 2003 11:39 am

I used an author size of 5000 for both 2205 & 10044 and got AC.
Used the STLs queue so no idea about queue size.

Hope this helps.

Now I understand why you post it in other words. We really need
a forum for archive. I think using the problem number may clarify
things a little bit.