11201 - The problem of the crazy linguist

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

Moderator: Board moderators

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

11201 - The problem of the crazy linguist

Post by Victor Barinov » Sat May 19, 2007 2:57 pm

Why WA?

my coefficients of average of the SBC are:

AV[0] = 0;
AV[1] = 5506 / 2100;
AV[2] = 216824 / 10500;
AV[3] = 299414 / 10500;
AV[4] = 678002 / 10500;
AV[5] = 271884 / 3500;
AV[6] = 461178 / 3500;
AV[7] = 1576244 / 10500;

But i have WA :( why?

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sat May 19, 2007 3:45 pm

Did you take in account the first letter of each word?

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

Post by Victor Barinov » Sat May 19, 2007 5:38 pm

Yes

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny » Sat May 19, 2007 7:13 pm

i didnt understand how u are handling the first letter.
for any length, starting a word with different consonants the SBC average would be different. u can precalculate the 21*7 averages.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sun May 20, 2007 8:04 am

well... my code got ac in .027s.. i did not do any pre computation. just a bit tricky bruteforce!
Self judging is the best judging!

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

Post by Victor Barinov » Sun May 20, 2007 11:55 am

Oh!

"...and start with the same letter than w"

((( now I understand my mistake.


AC now :) in my solution no brute force. Complexity is O(len(s))

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

WA.....

Post by ayeshapakhi » Mon May 21, 2007 9:26 am

Someone please provide some test cases..
i got wa.. used brute force to find answer....

regards...

h_davary
New poster
Posts: 4
Joined: Tue May 15, 2007 8:29 am

Runtime error about this Crazy Linguist

Post by h_davary » Tue May 22, 2007 2:47 pm

before i sent this code to online judge i had test it with dev4.9.9.2 and visual studio C++ 6.0 and worked well :D
but i dont know why it says it has "runtime error!" :
:roll:
------------------------------
Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference


Before crash, it ran during 0.002 seconds.
-----------------------------


can anyone help me?
:cry:

Code: Select all

#include <iostream>
#include <string>
using namespace std;

double p[]={12.53,1.42,4.68,5.86,13.68,0.69,1.01,0.70,6.25,0.44,0.00,4.97,3.15,6.71,8.68,2.51,0.88,6.87,7.98,4.63,3.93,0.90,0.02,0.22,0.90,0.52};

double sbc(string w)
{
	int k;
double su=0;

	for (k=0;k<w.length();k++)
	{
		su += k*p[(int(w[k])-97)];

	}
	return su;
}

int main()
{
int i,l,k,m,n;
double j[100];
string str[100];
	cin >> i ;
	for (l=0;l<i;l++)
	{
		cin >> str[l];
		j[l]=sbc(str[l]);
		
	}
	for (l=0;l<i;l++) 
	{
	m = str[l].length();
	n=0;	
	double sum=0,av = 0;
		for (k=0;k<i;k++)
		{
			if (str[k].length() == m)
			{
				n +=1;
				sum += sbc(str[k]);
			}
		}
	av = sum / n;
	if (sbc(str[l]) < av) cout << "below"<< endl;
	else cout << "above or equal" << endl;
	}
	

return 0;

}


Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Tue May 22, 2007 3:27 pm

Why is your array size 100? It could be the reason :wink:

Mushfiqur Rahman
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Location: (CSE, SUST) Sylhet, Bangladesh
Contact:

Post by Mushfiqur Rahman » Wed May 23, 2007 2:17 pm

h_davary wrote
before i sent this code to online judge i had test it with dev4.9.9.2 and visual studio C++ 6.0 and worked well
but i dont know why it says it has "runtime error!" :
Emilio wrote
Why is your array size 100? It could be the reason
Yes this is the reason of getting u run time. But I think if u increase the array size u will get wrong answer because u missunderstood the problem.

In this problem u have to calculate the SBC of all the words which start with the same latter as given word( with the same length ) then find the average and have to determine the given words SBC is "below" or "above or below" than the average.

suhendry
New poster
Posts: 14
Joined: Sat Aug 31, 2002 6:55 am

Post by suhendry » Fri May 25, 2007 8:17 pm

Victor Barinov wrote:Oh!

"...and start with the same letter than w"
I don't understand this part. Does it mean "all valid words that start with x1" ?
Suhendry Effendy

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Sat May 26, 2007 2:55 am

Yes.
All the words that can be constructed folowing the above pattern starts with x1.

h_davary
New poster
Posts: 4
Joined: Tue May 15, 2007 8:29 am

oh yes..

Post by h_davary » Sun May 27, 2007 2:38 pm

Emilio wrote
Why is your array size 100? It could be the reason :wink:
Mushfiqur Rahman wrote
But I think if u increase the array size u will get wrong answer because u missunderstood the problem...
oh, thanks :D ...you'r right the size of my array wasn't sufficent and
in general i missed the main point of this problem ...

I will try to solve it again but one question :lol: is there anyway to solve it other than brute forceing :roll:
maybe it takes a long time to do brute forceing :D

Piklu_sust
New poster
Posts: 23
Joined: Fri Sep 01, 2006 10:17 am
Location: CSE, SUST

Post by Piklu_sust » Wed May 30, 2007 7:20 am

Ya, you can use combinatorics. But for the length(s) = 7, it is bit harder.
I also use combinatorics, but get wrong answer several time but didn't know why. At last, I get accepted using backtracking (Complete brutforce).

TimeString
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 am

Post by TimeString » Sun Jun 03, 2007 4:27 am

note that the summantion of all letters' possibilitiy is not exactly 100 ( over than it).

Post Reply

Return to “Volume 112 (11200-11299)”