10686 - SQF Problems

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

Moderator: Board moderators

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » Tue Aug 17, 2004 10:06 pm

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()

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sun Sep 12, 2004 4:25 pm

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.
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? :o
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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Sep 12, 2004 6:21 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...)

txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

Post by txandi » Sun Nov 14, 2004 1:12 am

AC
Last edited by txandi on Mon Jul 09, 2007 10:12 pm, edited 1 time in total.

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Sun Feb 27, 2005 4:14 pm

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.
So what is the condition i should write in my code to get AC !!!!! :(

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10686 - SQF

Post by DD » Fri Apr 01, 2011 12:26 am

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. :o 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?
If so, you need to read Elements of Programming Interviews.

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10686 - SQF

Post by uDebug » Mon Jun 09, 2014 12:11 pm

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
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 106 (10600-10699)”