Page 5 of 7
Posted: Tue Jul 24, 2007 3:38 pm
by TimeString
Thanks Maniac. I simply followed what you said and got AC. The limit you gave is helpful.
Let me try to say the input format again(for each case):
Code: Select all
P N
paper database 1
paper database 2
...
paper database P
author 1
author 2
...
author N
For each line of paper database, like Maniac said, there are two formats, one of these is:
Code: Select all
FirstName1, LastName1, FirstName2, LastName2, ... FirstNameX, LastNameX: <the rest is not important, just ignore it>
Then this paper contains X authors.
Or another kind:
Code: Select all
FirstName1, LastName1, FirstName2, LastName2, ... FirstNameX, LastNameX, FirstNameY: <the rest is not important, just ignore it>
This is also contains X authors. Ignore FirstNameY.
Finally, the format of name lines is:
Note that the format of all available names, i.e., excluding like FirstNameY:, in the input is:
Code: Select all
FirstName, LastName
(FirstName, follows a comma, follows at least one whitespace, follows LastName)
So I assure Alexis Blaze that the input you post would not appear in judge data.
Runtime Error - Invalid Memory Reference
Posted: Thu Aug 02, 2007 1:57 pm
by TripShock
My program gives Runtime Error - Invalid Memory Reference. I understand this could be because my arrays are going out of bounds some place but I can't spot anything. Someone help please...
Code: Select all
#include <iostream>
#include <cstring>
#include <cctype>
using namespace std;
const int MAX = 6000;
char Connections[MAX][MAX] = { 0 };
char Authors[MAX][1024] = { 0 };
int NumAuthors = 0;
char NewAuthors[MAX][1024] = { 0 };
int NumNewAuthors = 0;
int ErdosNumber[MAX] = { 0 };
void DoErdos(int Source)
{
int Number = ErdosNumber[Source] + 1;
for (int i = 0; i < NumAuthors; i++)
{
if ((i != Source) && Connections[Source][i] && ((Number < ErdosNumber[i]) || (ErdosNumber[i] == -1)))
{
if (Number)
ErdosNumber[i] = Number;
DoErdos(i);
}
}
}
int main()
{
int Scenarios = 0;
int Papers = 0;
int Names = 0;
cin >> Scenarios;
for (int i = 1; i <= Scenarios; i++)
{
cin >> Papers;
cin >> Names;
cin.get();
memset(Connections, 0, MAX * MAX);
for (int j = 1; j <= Papers; j++)
{
char FirstName[1024] = { 0 };
char LastName[1024] = { 0 };
char Input = 0;
int Pos = 0;
NumNewAuthors = 0;
while (Input != ':')
{
Input = 0;
Pos = 0;
while ((Input = cin.get()) == ' ');
do
{
FirstName[Pos++] = tolower(Input);
Input = cin.get();
} while ((Input != ',') && (Input != ':'));
FirstName[Pos] = 0;
if (Input != ':')
{
Input = 0;
Pos = 0;
while ((Input = cin.get()) == ' ');
do
{
LastName[Pos++] = tolower(Input);
Input = cin.get();
} while ((Input != ',') && (Input != ':'));
LastName[Pos] = 0;
strcat(FirstName, ",");
strcat(FirstName, LastName);
strcpy(NewAuthors[NumNewAuthors++], FirstName);
bool Duplicate = false;
for (int k = 0; k < NumAuthors; k++)
{
if (!strcmp(Authors[k], FirstName))
{
Duplicate = true;
break;
}
}
if (!Duplicate)
strcpy(Authors[NumAuthors++], FirstName);
}
}
while (cin.get() != '\n');
for (int k = 0; k < NumNewAuthors; k++)
{
for (int l = 0; l < NumNewAuthors; l++)
{
int Index1 = 0;
int Index2 = 0;
for (Index1 = 0; strcmp(Authors[Index1], NewAuthors[k]); Index1++);
for (Index2 = 0; strcmp(Authors[Index2], NewAuthors[l]); Index2++);
Connections[Index1][Index2] = 1;
Connections[Index2][Index1] = 1;
}
}
}
for (int j = 0; j < NumAuthors; j++)
ErdosNumber[j] = -1;
int ErdosIndex = 0;
for (ErdosIndex = 0; (ErdosIndex < NumAuthors) && strcmp(Authors[ErdosIndex], "erdos,p."); ErdosIndex++);
if (ErdosIndex < NumAuthors)
{
ErdosNumber[ErdosIndex] = 0;
DoErdos(ErdosIndex);
}
cout << "Scenario " << i << endl;
for (int j = 1; j <= Names; j++)
{
char Name1[1024] = { 0 };
char Name2[1024] = { 0 };
cin.getline(Name1, 1024);
int l = 0;
for (int k = 0; Name1[k]; k++)
{
if (Name1[k] != ' ')
Name2[l++] = tolower(Name1[k]);
}
Name2[l] = 0;
int Index = 0;
for (Index = 0; strcmp(Authors[Index], Name2); Index++);
cout << Name1 << " ";
if (ErdosNumber[Index] != -1)
cout << ErdosNumber[Index];
else
cout << "infinity";
cout << endl;
}
}
return 0;
}
Posted: Thu Aug 09, 2007 4:57 pm
by andysoft
Hi ppl!
Can anyone with AC solution please provide me some tricky testcases for that problem. I don't want to post source as it might be hard to read for you, so I'd like to get the cases instead.
I have array [1..1002][1..5001] for the Graph and I know it's enough, and I have a queue with 50000 elements, the queue is (dunno in English...) "looped".
Thanx!
Posted: Thu Aug 09, 2007 5:16 pm
by helloneo
My AC program can take maximum 10000 authors..
I don't know how many authors there would be..
But, I'm sure it'll be more than 5000 ...
weird memory limit exceeded
Posted: Wed Aug 22, 2007 1:11 pm
by zero_cool
Hi guys,
I got the message memory limit exceeded which I don't understand why. Can you guys please help me out? Thanks.
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;
const int MAX=6000;
const int MAXC=200;
int connection[MAX][MAX];
char authors[MAX][MAXC];
int numAuthors;
char newAuthors[MAX][MAXC];
int numNewAuthors;
int erdosNumber[MAX];
int main() {
int tc;
int P,N;
char input;
int pos;
int index1,index2;
char firstName[MAXC];
char lastName[MAXC];
cin >> tc;
for (int h=0;h<tc;h++) {
cin >> P >> N;
cin.ignore(1000,10);
// Initialize
numAuthors=1;
strcpy(authors[0],"ERDOS,P.");
erdosNumber[0]=0;
for (int i=0;i<MAX;i++)
for (int j=0;j<MAX;j++)
connection[j]=0;
for (int i=0;i<P;++i) {
input=0;
numNewAuthors=0;
while (input!=':') {
input=cin.get();
while (input==' ' || input=='\t' || input=='\r') input=cin.get();
pos=0;
while (input!=',') {
firstName[pos++]=toupper(input);
input=cin.get();
}
firstName[pos]=0;
input=cin.get();
while (input==' ' || input=='\t' || input=='\r') input=cin.get();
pos=0;
while (input!=',' && input!=':' && input!='\n' && input!=EOF) {
//cout << input;
lastName[pos++]=toupper(input);
input=cin.get();
}
lastName[pos]=0;
strcat(firstName,",");
strcat(firstName,lastName);
strcpy(newAuthors[numNewAuthors++],firstName);
bool duplicate = false;
for (int k = 0; k < numAuthors; k++) {
if (strcmp(authors[k], firstName)==0) {
duplicate = true;
break;
}
}
if (!duplicate)
strcpy(authors[numAuthors++], firstName);
}
cin.ignore(1000,10);
/* Debugging
for (int j=0;j<numNewAuthors;j++)
cout << newAuthors[j] << ' ';
cout << endl;
*/
for (int j=0;j<numNewAuthors;j++) {
index1=0;
while (index1<numAuthors && strcmp(newAuthors[j],authors[index1])!=0) index1++;
for (int k=j+1;k<numNewAuthors;k++) {
index2=0;
while (index2<numAuthors && strcmp(newAuthors[k],authors[index2])!=0) index2++;
connection[index1][index2]=1;
connection[index2][index1]=1;
}
}
}
/* Debugging
for (int j=0;j<numAuthors;++j)
cout << authors[j] << ' ';
cout << endl;
*/
cout << "Scenario " << h+1 << endl;
for (int i=0;i<N;++i) {
cin.getline(firstName,1000);
cout << firstName << endl;
}
}
return 0;
}
Re: weird memory limit exceeded
Posted: Wed Aug 22, 2007 1:23 pm
by mf
And what did you expect?
"int connection[6000][6000];" is 6000^2*4 bytes = 137.3 Mb. Default memory limit is 32 Mb.
Posted: Wed Aug 22, 2007 11:56 pm
by zero_cool
Thanks for your reply. I try to delete all the code and just have the main method to return 0. It doesn't return memory limit exceeded that way. But, when I put some code, it returns memory limit exceeded. Can anyone explain to me why this is happening? Is the way the compiler work ignored unused declaration of array?
Posted: Thu Aug 23, 2007 2:54 am
by mf
If you see "Minimum" as memory usage, that means the judge couldn't determine your program's memory usage. This often happens for programs that terminate very quickly.
WA/RTE
Posted: Mon Sep 24, 2007 4:33 pm
by Ion2Atom
I finally figured out how to get past the TLE. Unfortunately now I have WA on PC and RTE on UVA. Can anybody give out some test cases? I did a simple one like this:
Code: Select all
1
12 16
Erdos, P., C, C: asdf
Erdos, P., B, B: asdf
Erdos, P., A, A: asdfa
B, B, G, G: asdf
A, A, H, H: asdf
H, H, I, I: asdf
I, I, J, J, K, K: asdf
J, J, L, L: asdf
L, L, F, F: asdf
C, C, F, F: aadsf
F, F, D, D, E, E: asdf
M, M, N, N, O, O: asdf
Erdos, P.
A, A
B, B
C, C
D, D
E, E
F, F
G, G
H, H
I, I
J, J
K, K
L, L
M, M
N, N
O, O
which gives the output of:
Code: Select all
Scenario 1
Erdos, P. 0
A, A 1
B, B 1
C, C 1
D, D 3
E, E 3
F, F 2
G, G 2
H, H 2
I, I 3
J, J 4
K, K 4
L, L 3
M, M infinity
N, N infinity
O, O infinity
It also passes the sample input, and double sample input. I'm really stumped on why this is incorrect. Thanks for any help! (code following)
Note: I have tried removing all white space (/t, /r, ' ', & '.') like it says earlier in the thread, and it still doesn't work. So I think I must be doing something different wrong. :\
Code: Select all
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <list>
#include <queue>
//max links 500
//max person names length 100
//max input line length 10000
//max names 5000
std::vector<bool> T;
std::vector<int> mem;
std::vector<std::vector<bool> > matrix;
void solve(int from);
std::string removeWhite(std::string str);
int main(){
int cases;
int paper_count;
int author_count;
int count;
int C;
int B;
std::string line;
std::string temp;
char A[1000];
char *P;
std::vector<std::vector<std::string> > papers;
std::vector<std::string> S;
std::map<std::string, int> authors;
std::map<std::string, int>::iterator iter;
std::cin >> cases;
for(int i = 0; i < cases; i++){
papers.resize(0);
matrix.resize(0);
T.resize(0);
authors.erase(authors.begin(), authors.end());
std::cin >> paper_count >> author_count;
papers.resize(paper_count);
count = 0;
std::getline(std::cin, line); //garbage - whitespace
for(int j = 0; j < paper_count; j++){
line = "";
std::getline(std::cin, line);
strcpy(A, line.c_str());
P = strtok(&A[0], ",");
while(P != NULL){
temp = std::string(P);
papers[j].push_back(temp);
P = strtok(NULL, ",");
}
line = papers[j][papers[j].size()-1];
papers[j].pop_back();
strcpy(A, line.c_str());
P = strtok(&A[0], ":");
temp = std::string(P);
papers[j].push_back(temp);
while(P != NULL){
P = strtok(NULL, ":");
}
S.resize(0);
for(int p = 0; p < papers[j].size(); p+=2){
S.push_back(papers[j][p]+ "," + papers[j][p+1]);
}
papers[j] = S;
//remove leading spaces
for(int o = 0; o < papers[j].size(); o++){
if(papers[j][o][0] == ' '){
papers[j][o] = papers[j][o].substr(1, papers[j][o].length()-1);
}
authors[papers[j][o]] = count++;
}
}
//init matrix
T.resize(count, false);
matrix.resize(count, T);
//adjacency matrix
for(int pedro_for_president = 0; pedro_for_president < papers.size(); pedro_for_president++){
for(int w = 0; w < papers[pedro_for_president].size(); w++){
C = authors[papers[pedro_for_president][w]];
for(int q = 0; q < papers[pedro_for_president].size(); q++){
B = authors[papers[pedro_for_president][q]];
if(C != B){
matrix[C][B] = true;
}
}
}
}
std::cout << "Scenario " << i+1 << "\n";
mem.resize(0);
mem.resize(matrix.size(), -1);
solve(authors["Erdos, P."]);
for(int k = 0; k < author_count; k++){
std::getline(std::cin, line);
//output
std::cout << line << " ";
if(mem[authors[line]] == -1){
std::cout << "infinity";
}
else{
std::cout << mem[authors[line]];
}
std::cout << "\n";
}
}
}
void solve(int from){
std::vector<bool> visited;
std::queue<int> Q;
int jumps = 0;
int to_pop;
visited.resize(0);
visited.resize(matrix.size(), false);
visited[from] = true;
Q.push(from);
while(Q.empty() == false){
to_pop = Q.size();
for(int j = 0; j < to_pop; j++){
mem[Q.front()] = jumps;
for(int i = 0; i < matrix.size(); i++){
if((matrix[Q.front()][i]) &&
(visited[i] == false)){
visited[i] = true;
Q.push(i);
}
}
Q.pop();
}
jumps++;
}
}
std::string removeWhite(std::string str){
}
[/code][/list]
help
Posted: Sat Dec 01, 2007 12:58 pm
by kason
could someone tell me....
if the paper database is
___A,___B___,_C,_D_,_E,_F: Newtonian forms of prime factor matrices
the authors' name are still
A,_B
C,_D
E,_F
or
A,___B
C,_D
E,_F
or
something else ~"~?????
ps. _ mean a space
Re: help
Posted: Sat Dec 01, 2007 1:14 pm
by helloneo
kason wrote:could someone tell me....
if the paper database is
___A,___B___,_C,_D_,_E,_F: Newtonian forms of prime factor matrices
the authors' name are still
A,_B
C,_D
E,_F
or
A,___B
C,_D
E,_F
or
something else ~"~?????
ps. _ mean a space
You should change it this way..
A,_B
C,_D
E,_F
Hope this help..
Posted: Fri Mar 21, 2008 11:11 pm
by turcse143
can some give me some special input-output?
i got WA
I ALSO check all the input which is given in this board.
but i don't know whats my problem.
is it ok to get the input format?
or is it okk to run the loop until ':';
Code: Select all
for(j=1;j<=x;j++)
{
gets(string);
count=0;
s=0;
d=0;
ch='2';
for(k=0;ch!=':';k++)
{
....................................
....................................
ples tell me.
Re: 10044 - Erdos Numbers
Posted: Mon Jul 14, 2008 2:45 pm
by rs17
After lots of REs I realize that there must be some extra empty lines in the input file!!!(There's nothing about this in the problem statement.) I changed my program and got Accepted.
Isn't that meaningless?!
Posted: Sat May 30, 2009 9:14 pm
by AltCtrlDel
I kept wondering about why I am getting RTE until I found on this forum a hint about a possible author name without first name initials and that it should be ignored! Now I got AC. But isn't it meaningless?! What skill does such trick measure?!! This is nonsensical!
Re: 10044 - Erdos Numbers
Posted: Sun Jan 10, 2010 11:28 am
by Ivan Goroun
Well, this is one messed up problem. Here's the input/output pair which finally got my code accepted. Part of it was earlier in this thread, but it was not sufficient.
Input:
Code: Select all
2
4 3
Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factor matrices
Erdos, P., Reisig, W.: Stuttering in petri nets
Smith, M.N., Chen, X.: First oder derivates in structured programming
Jablonski, T., Hsueh, Z.: Selfstabilizing data structures
Smith, M.N.
Hsueh, Z.
Chen, X.
12 19
Erdos, P., C, C., FUFAIL: asdf
Erdos, P., B, B.: asdf
Erdos, P., A, A.: asdfa
B, B., G, G.: asdf
A, A., H, H.: asdf
H, H., I, I.: asdf
I, I., J, J., K, K.: asdf
J, J., L, L.: asdf
L, L., F, F.: asdf
C, C., F, F.: aadsf
F, F., D, D., E, E.: asdf
M, M., N, N., O, O.: asdf
Erdos, P.
A, A.
B, B.
C, C.
D, D.
E, E.
F, F.
G, G.
H, H.
I, I.
J, J.
K, K.
L, L.
M, M.
N, N.
O, O.
WTF, F.
WTF.
WTF, U.
Output:
Code: Select all
Scenario 1
Smith, M.N. 1
Hsueh, Z. infinity
Chen, X. 2
Scenario 2
Erdos, P. 0
A, A. 1
B, B. 1
C, C. 1
D, D. 3
E, E. 3
F, F. 2
G, G. 2
H, H. 2
I, I. 3
J, J. 4
K, K. 4
L, L. 3
M, M. infinity
N, N. infinity
O, O. infinity
WTF, F. infinity
WTF. infinity
WTF, U. infinity
I'm sure there's some overkill here, but if your program handles this input it should be accepted. Oh, and that "FUFAIL" in the paper authors without an initial - you must handle that 100%. Same goes for "WTF" without the initial in the names list.