Page 3 of 17

Posted: Thu Jul 04, 2002 6:43 am
by taj79
Thanks
now i understand what the problem is saying regarding the order of the elements.

I could handle it by writing a function.

But in my latest prog since i am storing all the strings hence it gives segmentation fault as i increase MAX1 to store all the strings,say of elements >9.

I will have to follow your advice by modifying my comb() .
I will try to use your advice.
Thanks again

Posted: Thu Jul 04, 2002 12:09 pm
by taj79
THANKS TO ALL OF U .
I have solved the problem with just presentation error( i always get this).

Few days back,I had posted my prog for prob 124 in this volumeI forum.
Now I will try to put this algo in that prob also

I had also tried to do Prob no 101 but failed.
I had put my problem (prog) in this forum.
But till now, no one has helped me.
Please also help me in doing that prob.

Special thanks for picard

195 - Too slow.

Posted: Sat Jul 06, 2002 10:14 pm
by waffle
As far as I can tell, my program for 195 does everything it needs to do, including removing redudant entries and getting the correct sorting. However, it is much too slow. Can anyone help me fix my algortihm?

[cpp]/* @JUDGE_ID: 20852KJ 195 C++ "Recurse+Kludges" */

#include <iostream>
#include <string.h>
#include <string>
#include <set>

using std::string;

struct cmp
{

bool
operator () (const string one, const string two) const
{
return (one < two);
}
};

set < string, cmp > THESET;


void
clearlist ();
void
addlist (string x);
bool
checklist (string x);
/*string
list[5000];
int
list_index =
0;
*/

int
compare (string one, string two);

void
anagram (string pre, string post);

int
main ()
{
int
number;
string input[100];
cin >> number;
int
length;
int
i,
j,
z,
y;
string
min;
char
temp;

if (number < 0)
{
cout << "negative number of words to do?!?!?!" << endl;
return (0);
}
// Get inputs
for (i = 0; i < number; i++)
{
cin >> input;
}

//Sort inputs.
for (i = 0; i < number; i++)
{
for (int z = 0; z < input.size () - 1; z++)
{
y = z;
min = input.substr (y, 1);
for (j = z + 1; j < input.size (); j++)
{
if (compare (min, input.substr (j, 1)))
{
y = j;
min = input.substr (y, 1);
}

}
input[y] = input[z];
input[z] = min[0];
}

}
//Process and do output
for (i = 0; i < number; i++)
{
clearlist ();
anagram ("", input);
}
}


void
anagram (string pre, string post)
{
int
i,
j;
string one, two, temp;
if (post.size () > 2)
{
for (i = 0; i < post.size (); i++)
{
one = pre;
one += post.substr (i, 1);

two = post;
two.erase (i, 1);


// If string = ABCD, call Anagram 4 times:
// anagram(A, BCD)
// anagram(B, ACD)
// anagram(C, ABD)
// anagram(D, ABC)
//
// anagram(A, BCD) would call these:
// anagram(AB, CD)
// anagram(AC, BD)
// anagram(AD, BC)

anagram (one, two);
}
}
else if (post.size () == 2)
{
// Base case. POST is 2 characters.
// Display PRE+POST and then PRE+(reversed POST)

temp = pre + post;


if (checklist (temp) == false)
{
cout << temp << endl;
addlist (temp);
}

temp = pre + post[1] + post[0];

if (checklist (temp) == false)
{
cout << temp << endl;
addlist (temp);
}
return;
}
else
{
cout << "undefined";
}
}

int
compare (string one, string two)
{
char
a,
b;
a = one[0];
b = two[0];
if (toupper (a) != toupper (b))
return (toupper (a) > toupper (b));
else
return (a > b);

}



void
clearlist ()
{
THESET.clear ();
}

void
addlist (string x)
{
THESET.insert (x);
}

bool
checklist (string x)
{

set < string, cmp >::iterator it = THESET.find (x); // O(Log N) or O(N)??
// Hash table would
// provide O(1).
if (it == THESET.end ())
return false;
return true;
}
[/cpp]

195: anagram, wrong answer

Posted: Sat Jul 13, 2002 11:09 pm
by irmen
Hi I keep getting "wrong answer" although I'm pretty sure my output is correct. What do I miss here?

I've kludged with the input code to accept even empty lines (empty words) but this didn't help.

Here's my program:
(as you see, it uses STL algorithms, so there should be nothing wrong with the algorithm)
[cpp]
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>

using namespace std;


int main(int argc, char** argv)
{
int amount;
cin >> amount;
cin.get();

for(int i=0; i<amount; ++i)
{
char buf[10000];
cin.getline(buf,'\n');
string word(buf);

sort(word.begin(), word.end());

cout << word<<endl;
while(next_permutation(word.begin(),word.end()))
{
cout <<word <<endl;
}
}

return 0;
}
[/cpp[/cpp][/code]

Posted: Sun Jul 14, 2002 6:38 am
by rascle
Sorry,my program language background is poor.
So I can't understand you code.

But the only problem that I ran into is the sequence is

A<a<B<b<C<c.....<Z<z

Wish this suggestion can help you ....

sorting... that must be it

Posted: Sun Jul 14, 2002 1:21 pm
by irmen
Argh ofcourse now I'm reading the problem description again,
and I see my sorting is not quite right :P Thanks

(edit)
GRR :evil: I changed the sorting and still a Wrong Answer.
with input: 1 aabB my program outputs:
aaBb
aabB
aBab
aBba
abaB
abBa
Baab
Baba
Bbaa
baaB
baBa
bBaa

I think I covered all cases here: my program accepts empty
words, it doesn't print duplicates when letters occur >1x, and the sorting
is correct, right? (A<a<B<b<....<Z<z). What else is going on!?

Posted: Sun Jul 14, 2002 3:49 pm
by rascle
The last thing I can thought is ....

" Initialize.."

You can try these cases

3
aaBBe
bb
eeeb

At my first time,"bb" case has five characters.

Posted: Sun Jul 14, 2002 4:00 pm
by irmen
Initialization is ok,
rascle wrote:You can try these cases

3
aaBBe
bb
eeeb
I get the following output with this test case:

aaBBe
aaBeB
aaeBB
aBaBe
aBaeB
aBBae
aBBea
aBeaB
aBeBa
aeaBB
aeBaB
aeBBa
BaaBe
BaaeB
BaBae
BaBea
BaeaB
BaeBa
BBaae
BBaea
BBeaa
BeaaB
BeaBa
BeBaa
eaaBB
eaBaB
eaBBa
eBaaB
eBaBa
eBBaa
bb
beee
ebee
eebe
eeeb


This is correct, right? I'm beginning to think there is something fishy in the input test case of the judge, that breaks my program... but what? I can accept 10,000 char words and even empty words....?

Posted: Mon Jul 15, 2002 3:35 am
by rascle
Sorry,I don't know what's wrong with your code..
You can get my code,and test many inputs on your code and mine...
Maybe you will get a detection from the answers between them ..

Good lock...

If you want my code ..please mail to

u891504@oz.nthu.edu.tw

I will send my code to you as soon as possible..

Posted: Tue Jul 16, 2002 3:59 am
by rascle
Hi

I've sent you my code 195.c

I implemented the problem 10098 yesterday,it is same as 195,the only
difference is the A<B<C <..<Z<a<b...<z and A<a<B<b<C<c..<Z<z

I found the problems are only initializaion and noting the order.


^^..

195 - WA again and again

Posted: Tue Jul 16, 2002 1:11 pm
by karl
It's terrible, always WA WA WA.
I studied your advices given before very carefully; I guess, my prog generates no duplicates and sorting is okay.
Do you have any hints or more test data???

[code]
#include <strstream.h>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


char line[8192];
char z;
int z_mod;

int n_of_runs;
int run;


void do_the_job()
{
vector<char> v;
char i;

gets(line);
istrstream mystream1(line);
while (mystream1 >> z)
{
z_mod=(int) z;
if ((z_mod>55) && (z_mod<91))
v.push_back((z_mod-65)*2+1);
else
v.push_back((z_mod-96)*2);
}
sort(v.begin(), v.end());
for (i=0; i<v.size(); i++)
{
if ((v[i])%2==1)
cout << ((char)(((v[i]-1)/2)+65));
else
cout << ((char)(((v[i])/2)+96));
}
cout << endl;

while (next_permutation(v.begin(), v.end()))
{
for (i=0; i<v.size(); i++)
{
if ((v[i])%2==1)
cout << ((char)(((v[i]-1)/2)+65));
else
cout << ((char)(((v[i])/2)+96));
}
cout << endl;
}
cout << endl;
}



int main()
{

cin >> n_of_runs;
for (run=0; run<n_of_runs; run++)
do_the_job();

return 0;
}

[/code]


Any help welcome!!![/cpp]

Re: 195 - WA again and again

Posted: Tue Jul 16, 2002 8:16 pm
by irmen
Your prog doesn't compile here without changing #include <strstream.h> to #include <strstream>

After that, I can't get your prog to read a basic input file:

1
test

It doesn't read the word. Just exits...

Posted: Wed Jul 17, 2002 8:13 am
by karl
:D

I got it!!!
Problem was: How to deal with empty lines...

I changed input handling to

[cpp] do
{
gets(line);
} while (strlen(line)==0);
[/cpp]


Thanks a lot!!!

Posted: Wed Jul 24, 2002 4:36 pm
by bundy
ok I think I have finally figured this out. I wrote my own compare routine for the sort algorithm to call. the program compiles on my system (win 2k and vc++) but I get a few compile errors from the judge. here are the errors I am getting.

00973177_24.c: In function `bool bSorted(basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >, basic_string<char,string_char_traits<char>,__default_alloc_template<true,0> >)':
00973177_24.c:74: implicit declaration of function `int _strdup(...)'
00973177_24.c:76: implicit declaration of function `int _strupr(...)'

I thought _strdup and _strupr was declared in string.h. I also had an earlier error where i ended up having to do a cast because it was return an int when i expected a char*.

Here is my code. Any help is appreciated.

[cpp]
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <malloc.h>

using namespace std;

string toString(vector<char> &data);
bool bSorted(string x, string y);
void printEntry(vector<string> &data);


int main()
{

int numberOfWords = 0;
int count = 0;
vector<char> combo;
string input = "";
vector<string> output;


cin >> numberOfWords;

while (count++ < numberOfWords)
{
int i = 0;

combo.clear();
output.clear();
input = "";

cin >> input;

for (;i < input.size();i++)
combo.push_back(input);

sort(combo.begin(), combo.end());
output.push_back(toString(combo));

while(next_permutation(combo.begin(),combo.end()))
{
output.push_back(toString(combo));
}

sort(output.begin(),output.end(),bSorted);
printEntry(output);
}

//cout << "in test " << ("e" < "b") << endl;
//cout << bSorted("eaaBB","BBaae");


return 0;
}

void printEntry(vector<string> &data)
{
for(int i = 0; i < data.size(); i++)
cout << data << endl;
return;
}

bool bSorted(string x, string y)
{
char *xCopy;
char *yCopy;
char *xCap;
char *yCap;

xCopy = reinterpret_cast<char*> (_strdup(x.c_str()));
yCopy = reinterpret_cast<char*> (_strdup(y.c_str()));
xCap = reinterpret_cast<char*> (_strupr(xCopy));
yCap = reinterpret_cast<char*> (_strupr(yCopy));

if (x == y)
{
//cout << "equal" << endl;
return true;
}
else
{
if ( strcmp(xCap,yCap) == 0)
{

if (x < y)
{
//cout << "caps equal and x less than" << endl;
return true;
}
else
{
//cout << "caps equal and x greater than" << endl;
return false;
}
}
else
{
if (x < y)
{
//cout << "caps less than" << endl;
return true;
}
else
{
//cout << "caps greater than" << endl;
return false;
}

}
}

free(xCopy);
free(yCopy);
free(xCap);
free(yCap);
}


string toString(vector<char> &data)
{
string temp = "";
for (int i = 0; i < data.size();i++)
temp += data;
return temp;
}


[/cpp]

Posted: Wed Jul 24, 2002 6:13 pm
by LawrenceT
my guess is that you are programming in windows.. probably using microsoft visual c or some variant...

cos these functions starting with '_' do not exist in ANSI C, which is generally (with a few exceptions - for example, the long long int type) what the judge is running...

so, use other functions that have the same effect...