10686 - SQF Problems

[krijger]

I also keep getting WA (after numerous tries). It gives the right output on the examples given on this page. I think the mistake is in the input reading, but it could also be a minor dumb mistake (I'm good at that)Here is the relevant part of my code:

[cpp]typedef struct Cat { char name[50]; int nrkey,needed; set<str> key; } Cat;

Cat cat[MAXCAT];

void run() {
int nrcat; scanf("%d",&nrcat);
char buff[1000];
REP(i,nrcat) {
scanf("%s%d%d",cat.name,&cat.nrkey,&cat.needed); gets(buff);
REP(j,cat.nrkey) { scanf("%s",buff); cat.key.insert(str(buff)); gets(buff); }
}
set<str> words;
while(1) {
gets(buff);
if(strlen(buff)==0) break;
str cur;
for(int i=0;buff!='\0';++i) {
if(buff>='a'&&buff<='z'||buff>='A'&&buff<='Z')
cur+=buff[i];
else if(cur.SZ!=0) { words.insert(cur); cur=""; }
}
if(cur.SZ!=0) words.insert(cur);
}
bool first=true;
REP(i,nrcat) {
int nrmatch=0;
FORIT(j,cat[i].key) if(words.count(*j)) ++nrmatch;
if(nrmatch>=cat[i].needed) { if(!first) printf(","); else first=false; printf("%s",cat[i].name); }
}
if(first) printf("SQF Problem.\n"); else printf("\n");

}
[/cpp]

btw I use some macro's:
REP(i,n) is something like for(int i=0;i<n;++i)
FORIT(i,v) something like for(typeof(i) i=v.begin();i!=v.end();++i)
SZ is size()

[..]

No. The output should be:

Code: Select all

3
NeverOne 0 1
NeverTwo 1 2
dummy
NeverThree 2 2
dummy
dummy
This is a text where the word dummy apears twice!
Because I've added a dummy line. 

Code: Select all

SQF Problem.

What is the logic behind this case??
The words "dummy" appeared twice in the text and the category requires 2 appearance, so why the answer is SQF?

[little joey]

There is no logic behind it, it's just as it is. The problemsetter wanted to add some 'special cases', but failed to describe how the matching should be in cases where two (or more) keywords are the same. The whole idea of same keywords is s****d in my view.

BTW: I see you're about to pass me in the ranklist. Congrats! (I'll be back...)

[txandi]

AC

[A1]

There is no logic behind it, it's just as it is. The problemsetter wanted to add some 'special cases', but failed to describe how the matching should be in cases where two (or more) keywords are the same. The whole idea of same keywords is s****d in my view.

So what is the condition i should write in my code to get AC !!!!!

[DD]

It is really strange problem. I passed all input test cases on this board, and got lots of R.E. and W.A. After I changed my parsing from getline in C++ to gets in C. I got A.C. Still dunno why this happen...

[uDebug]

So, this is one of the more tricky problems out there. After struggling with it over a few days, this is what I discovered.

So I think that there are lines with whitespace before the newline-character where this was not to be expected.

This is not true. There are newlines - not newlines preceeded by spaces. Reading the input in this problem is tricky. Make sure your code passes little joey's test case.

Here's how I went about taking input (line by line).

Code: Select all

int main() {
	/* Read in the number of test Cases */
	getline(cin, aLine);
		
	istringstream ss(aLine);
	
	ss >> testCases;
	
	/* Process the test cases */
	for(t = 0; t < testCases; t++) {
		/* Read in the number of categories */	
		getline(cin, aLine);
		
		istringstream ss(aLine);
		
		ss >> categories;
		
		/* Process the categories */
		for(c = 0; c < categories; c++) {
			/* 
			  Read in the category name, the number of keywords and 
			  the number of critical keywords 
			*/
			string aCategory;
			
			getline(cin, aLine);
			
			istringstream ss(aLine);
			
			ss >> aCategory >> keywords >> criticalKeywords;
			
			/* Process the keywords */
			for(k = 0; k < keywords; k++) {
				
				/* Read in the keyword */
				string aKeyword;
				
				getline(cin, aLine);
				
				istringstream ss(aLine);
			
				ss >> aKeyword;
			}
		}
		/* Process the lines until a blank one's seen */
		while(1) {
			/* Read the entire line */
			getline(cin, aLine);
				
			/* Exit if there's a blank line */
			if(aLine == "") {
				break;
			} 
		}
	}
   return 0;
}

Note the cutest bit of code but I can guarantee it works for this problem and there's nothing more crazy in regards to the input that's going on.

Also, I really found this days to figure out so I thought I'd share: Tthere are characters in the input not found on a standard US keyboard. So, make sure your parsing doesn't rely on something like this

Code: Select all

/* Tokenize the string so that only alphabets are left */
pch = strtok(line, "`~1!2@3#4$5%6^7&8*9(0)-_=+[{]}\\|;:'\",<.>/? ");

Because there are going to be characters like so

Code: Select all

ãáàâçéêíõóô

and that could mess up your program big time.

Finally, here are some test cases I found useful during testing / debugging. (Thanks to MNDrebin for the last test case.)

Code: Select all

15
4
Biology 14 5
plant
animal
life 
cell
earth
soil
water
plant
animal
life 
cell
earth
soil
water
Zoology 10 5
plant
animal
life 
cell
earth
plant
animal
life 
cell
earth
Numerology 5 0
plant
animal
life 
cell
earth
Toxicology 4 7
plant
animal
life 
cell
plant
animal life cell earth plant
animal!
life. 
cell;
earth? plant animal life 
cell earth plant...animal life  cell earth
plant
animal
life 
cell
earth

4
Biology 14 1
plant
animal
life 
cell
earth
soil
water
plant
animal
life 
cell
earth
soil
water
Zoology 10 5
plant
animal
life 
cell
earth
plant
animal
life 
cell
earth
Numerology 5 0
plant
animal
life 
cell
earth
Toxicology 4 1
plant
animal
life 
cell
plant
animal life cell earth plant
animal!
life. 
cell;
earth? plant animal life 
cell earth plant...animal life  cell earth
plant
animal
life 
cell
earth

1
Geography 0 1
Some rubbish text
This should not be processed

1
Geography 1 1
sudan

3
Imaginography 3 2
imagine
imagine
real
Geography 2 1
chad
sudan
Countrygraphy 2 2
chad
sudan
chad;imaginesudan is also in africa 
chad;imagine sudan is also in africa
chad;sudan is also in africa
chad;sudan is also in africa|real

0

0
But still rubbish text and this is 
going to be processed????

2
Cryptology 2 2
          cipher             
                               decipher                       
      Cryptography 1                0
      key             
cipher cipher cipher
cipher[][230492-4923decipher<>>>>key 

2
Cryptology 2 2
          cipher             
                               decipher                       
      Cryptography 1                0
      key             

2
category 3 2
category
category
category 
Category 3 1
category 
category 
category 
category Category

2
category 3 0
category
category
category 
Category 3 0
category 
category 
category 

1
HipHop 0 10
FloRida LilWayne

3
Math 3 2
plus 
minus
equals
Physics 4 1
mass
plus
Physics
plus
Chemistry 2 2
atom
reaction
reaction plus plus plus not equals 

1
Graph 2 2
edge
these
We need an edge! And theseãáàâçéêíõóôúü are portuguese characters that are 
embedded so make sure you parse them

3
Cat 2 1
batmouse
supermouse
Eats 2 1
spidermouse
CaptainAmericaMouse
Dog 1 1
hahahaitsavalidword
I Can't hear you "AYE AYE CAPTAIN"
Ohh...
Who lives in a pineapple under the sea
"Spongebob squarepants"
Absorbant batmouse and yellow and porous is he
"Spongebob Squarepants"
If nautical nonsense be something you wish
"Spongebob *34*54545*CaptainAmericaMouse*5*5**5445* Squarepants"
Then @@hahahaitsavalidword. drop on the super.mouse deck and flop like a fish
"Spongebob Squarepants"
READY batmouse of course
Spongebob squarepants
Spongebob squarepants
Spongebob squarepants

AC Output:

Code: Select all

Biology,Zoology,Numerology
Biology,Zoology,Numerology,Toxicology
SQF Problem.
SQF Problem.
Imaginography,Geography,Countrygraphy
SQF Problem.
SQF Problem.
Cryptology,Cryptography
Cryptography
Category
category,Category
SQF Problem.
Math,Physics
Graph
Cat,Eats,Dog