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()
10686 - SQF Problems
Moderator: Board moderators
What is the logic behind this case??little joey wrote: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.
The words "dummy" appeared twice in the text and the category requires 2 appearance, so why the answer is SQF?
My signature:
- Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code. - I HATE testing account.
- Don't send me source code for debug.
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
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...)
BTW: I see you're about to pass me in the ranklist. Congrats! (I'll be back...)
So what is the condition i should write in my code to get AC !!!!!little joey wrote: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.
-
- Experienced poster
- Posts: 145
- Joined: Thu Aug 14, 2003 8:42 am
- Location: Mountain View, California
- Contact:
Re: 10686 - SQF
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...
Have you ever...
- Wanted to work at best companies?
- Struggled with interview problems that could be solved in 15 minutes?
- Wished you could study real-world problems?
Re: 10686 - SQF
So, this is one of the more tricky problems out there. After struggling with it over a few days, this is what I discovered.
Here's how I went about taking input (line by line).
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
Because there are going to be characters like so
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.)
AC Output:
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.So I think that there are lines with whitespace before the newline-character where this was not to be expected.
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;
}
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)-_=+[{]}\\|;:'\",<.>/? ");
Code: Select all
ãáàâçéêíõóô
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
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