ACM - My problem with the output of " 10789 - Prime Frequency "

[bahador saket]

Dear All

10789 - Prime Frequency "
http://uva.onlinejudge.org/external/107/10789.html

I have tried to solve this question but unfortunately I can not
understand this paragraph in explanation of out put :

"this line contains the serial of output followed by the characters
whose frequency in the input string is a prime number. These
characters are to be sorted in lexicographically ascending order. Here
``lexicographically ascending" means ascending in terms of the ASCII
values".

so my out put should followed by the characters whose frequency in the
input?
OR
it should sorted in lexicographically ascending order?

because I think ( I AM NOT SURE ) according to this sentence "put
should followed by the characters whose frequency in the input? "

input:
AAAbbbcccddLLLLLLLLL222

out put should be:
Case 1: Abc2

According to: These characters are to be sorted in lexicographically
ascending order. Here ``lexicographically ascending" means ascending
in terms of the ASCII values".

input:
AAAbbbcccddLLLLLLLLL222

out put should be:
Case 1: 2Abc


Regards,
Bahador Saket

[Josiah]

Choose only characters where the frequency is a prime number, and then
sort these characters according to their ASCII value.

e.g.

input: BBBBDDDDDAA

frequencies:
B=4 (not prime)
D=5 (prime)
A=2 (prime)

output: AD

J

[bahador saket]

Dear Josiah

I solved this problem according to what you said but UVa did not accept it.
I attached my code here, it would be must appreciated if you check it.

Cheers,
Bahador
 

--
Post: fit-ca...@googlegroups.com
Unsubscribe: fit-cafeteri...@googlegroups.com
Visit: http://groups.google.com/group/fit-cafeteria?hl=en

[Josiah]

Your program fails when the characters are not contiguous (for example
CABCC, or 7k7k7k).
It should work once you fix the counting part (UVa has accepted your
code that I've modified, but I'll let you have a go at fixing it
yourself ;) ).

(Hint: the "map" STL container could be useful for such problems).

Best,
J

>  2.txt
> < 1KViewDownload
>
>  new5.cpp
> 2KViewDownload

[bahador saket]

Dear Josiah

tnx for your answer.:)
I solved some bugs of my code, but it is not accepted by UVa.
Can you check it from following link please?

http://www.easy-share.com/1910967785/new5.cpp

Please do not write correct code for me, only say the part that has a
bug because i want to try first :) :)


Best Regards,
Bahador

[Josiah]

Try these inputs...

idufjdklmvlkue342494832674921487 (Expected output: 234789dklu)
76583hjfkshgkiKJDNHFKJSkjsdnksi (Expected output: JKhijs)
iutioerniIHGFSDHuyeuiu735982347kkj (Expected output: 37Hek)

Happy debugging! :)

J

[bahador saket]

Dear Josiah

Finally, UVa accept my solution:D:D
but exactly, my solution is not optimize, it is about 100 lines and I am sure it will not suitable solution.

today I found vectors are not good solutions for these cases.

what should I do when I encounter some questions that I need sort 2 parameters.
like this case that I should sort one character and its counter in same time..... (in fact, counter should be connect to its character when we want to search).
you mentioned map before it, how should I use it?

tnx.:)

Regards,
Bahador Saket

[Josiah]

Good job! :)

Maps are data structures which can be used to store (key, value)
pairs, where each key can be mapped to a corresponding value. Useful
for things like (Student ID, Student Name), (Name, Phone Number), or
for this example (Character, Frequency). They're also known as
dictionaries, associative arrays, hashtables, hashmaps, etc. depending
on what programming language you're using.

Here's a C++ example on using STL's map to compute the frequencies of
each character (remember to #include <map>).

string input = "adcBaDaDcdcdBcaccdaBe";

map<char, int> freq;
for (int i=0; i<input.length(); i++) {
freq[input[i]] = freq[input[i]] + 1;
}

...and to print out all (key, value) pairs...

map<char, int>::iterator it;
for (it=freq.begin(); it!=freq.end(); it++) {
cout << it->first << " => " << it->second << endl;
}

...resulting in the output:
B => 3
D => 2
a => 5
c => 6
d => 4
e => 1

Notice that the keys have been sorted for you. Very convenient for
your "Prime Frequency" problem :)

Read the C++ documentation or Google for more info.



Best,
J

On Jun 15, 7:04 pm, bahador saket <bahador.sa...@gmail.com> wrote:
> Dear Josiah
>

> Finally, UVa accept my solution:D:D
> but exactly, my solution is not optimize, it is about 100 lines and I am
> sure it will not suitable solution.
>

> *today I found vectors are not good solutions for these cases.*

[Josiah]

Just realised that I may have given away too much information! Should
have let you discover it yourself... sorry! :P

J

[johnsee]

josiah, u bad!
it was really for them to try :P

[bahador saket]

Dear JohnSee

Josiah did not complete my code.... :D
I tried,tried and tried to solve my problem.:D
And after 2 days I solved it.
but exactly, I am going to learn more about the maps:)

Cheers,
Bahador

[bahador saket]

Dear JohnSee and Josiah

Finally, I solved the question in much better way ...:D:D:D:D
obviously,it is really gooooooooooooooooooooooood and easy when we use
map:)

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main () {
int a;
cin>>a;
cin.ignore();
int counter=0;
string line=" ";
while(a--)
{
map<char,int> temp;
getline(cin,line);
for(int i=0;i<line.length();i++)
{
if(line[i]!=' ')
temp[line[i]]=temp[line[i]]+1;

}
map<char,int>::iterator it;
map<char,int>::iterator it1;
cout<<"Case"<<counter<<": ";
int temp1=0;
for(it=temp.begin();it!=temp.end();it++)
{
if(it->second==2)
{
cout<<it->first;
temp1++;
}
else if(it->second>2)
{
int n=0;
for(int j=2;j<it->second;j++)
{
if(it->second%j==0)
{
n=0;
break;
}
else n=1;
j++;
}
if(n==1)
{
cout<<it->first;
temp1++;
}
}
}
if(temp1==0)
{
cout<<"empty";
}
cout<<endl;
counter++;
}
}

Cheers,
Bahador