10044 - Erdos Numbers

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

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
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

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?

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

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
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

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?

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

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
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

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]

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

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
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

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
Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
Location: Bangladesh

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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

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.
"Everything should be made simple, but not always simpler"

Tahseen Mohammad
Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
Location: Bangladesh

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
Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
Location: Bangladesh

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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

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
"Everything should be made simple, but not always simpler"

Tahseen Mohammad
Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
Location: Bangladesh

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.

Post Reply

Return to “Volume 100 (10000-10099)”