## 10062 - Tell Me the Frequencies!

Moderator: Board moderators

### Re: 10062 - Tell Me the Frequencies!

{
if(count[j]<min && count[j]>0)
{
min=count[j];
k=j;
}

}

In this section your program accesses count[256], which is undefined.

Also don't print the blank line at the end of output.
mf
Guru

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

### 10062 - Tell Me the Frequencies!

i m getting wa wa wa!
could anyone check and tell my errors.
here is my code-

#include<stdio.h>
#include<string.h>
#include<ctype.h>

int main()
{
int value[258],ascii[258],frq[130],i,j,k,tmp,start=0,len;
char input[1000];

while(gets(input)!=NULL)
{

if(start)
printf("\n");
start=1;

for(i=0;i<258;i++)
{
value[i]=0;
ascii[i]=i;
}

len=strlen(input);
for(i=0;i<len;i++)
value[input[i]]++;

for(i=0,j=0;i<256;i++)
if(value[i])
{
ascii[j]=i;
frq[j++]=value[i];
}

for(i=0;i<j-1;i++)
for(k=0;k<j-1;k++)
if(frq[k]<=frq[k+1])
if((frq[k]<frq[k+1])||(ascii[k]<ascii[k+1]))
{
tmp=frq[k];
frq[k]=frq[k+1];
frq[k+1]=tmp;
tmp=ascii[k];
ascii[k]=ascii[k+1];
ascii[k+1]=tmp;
}
for(i=0;i<j;i++)
printf("%d %d\n",ascii[i],frq[i]);

}

return 0;
}
bm_anas
New poster

Posts: 10
Joined: Fri May 15, 2009 9:13 pm

### Re: 10062 - Tips to solve this problem

How to solve
1. do a character count for each existing chars in the input string. Store the counting result in a map-like structure, mapping each char to its count. You get an array of the map structure.
2. sort the array by the char, in descending order.
3. sort the array by the count, in ascending order.
4. output the array according to the needed format.

How to sort
You need a sorting algorithm that is stable. It means the relative order of records with equal key is maintained.
Bubble sort is the most well-known and easy-to-implement stable sorting. Insertion sort and merge sort are stable and fast. Quick sort is unstable. Better avoid it in this problem. My AC solution is using bubble sort.

Test cases
input
Code: Select all
`sort me by bubblesortstd::stable_sort(), std::list<T>.sort(), std::stable_partition().`

output
Code: Select all
`121 1117 1109 1108 1116 2115 2114 2111 2101 232 398 4112 1110 184 162 160 1101 298 295 246 244 232 2114 3111 3108 3105 3100 397 341 340 358 6115 8116 10`

The blank line between cases issue has been talked hundred times in previous messages. I don't repeat it here.

Good luck.
allenlam
New poster

Posts: 8
Joined: Tue Jun 09, 2009 6:46 am

### Re: 10062 - Tell Me the Frequencies!

this is my code:

Code: Select all
`#include <iostream>using namespace std;int main(){string a;char b[200];int c,d,i,j,k,array[1000],l=0,count[1000],count2[1000],array2[1000],q=0,u,y,temp,temp2;while(cin>>a){q=0;for(i=0;a[i]!='\0';i++){    array[i]=a[i];}for(y=0;y<i;y++)    for(u=0;u<i-1;u++)        {            if(array[u]<array[u+1])                {                    temp=array[u];                    array[u]=array[u+1];                    array[u+1]=temp;                    }            }for(j=0;j<i;j++)count[j]=0;for(j=0;j<i;j++)    {        if(array[j]!=0)            {count[j]=1;                for(k=j+1;k<i;k++)                    {                        if(array[j]==array[k])                            {                                count[j]++;                                array[k]=0;                                }                        }                }        }for(j=0;j<i;j++){    if(count[j]!=0 && array[j]!=0)        {            count2[q]=count[j];            array2[q]=array[j];            q++;            }    }for(y=0;y<q;y++)    for(u=0;u<q-1;u++)        {            if(count2[u]>count2[u+1])                {                    temp=count2[u];                    count2[u]=count2[u+1];                    count2[u+1]=temp;                    temp2=array2[u];                    array2[u]=array2[u+1];                    array2[u+1]=temp2;                    }            }for(j=0;j<q;j++)    {        cout<<array2[j]<<" "<<count2[j]<<endl;        }  cout<<endl;  //printf("\r");}    return 0;    }`

etameem
New poster

Posts: 5
Joined: Tue Jul 21, 2009 11:11 am

### Re: 10062 - Tell Me the Frequencies!

uvatoolkit.com has program which accepts inputs and produces outputs for AC solution. You can generate some test cases and check it if it is the same as uvatoolkit.com. It doesn't have source , only it produces output for AC solution.

tryit1
Experienced poster

Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 10062 - Tell Me the Frequencies!

yes. i know about uvatoolkit.com and i have checked some input there. but can't find any difference between my output and uvatoolkit.com output. but then why i am getting WA ???
etameem
New poster

Posts: 5
Joined: Tue Jul 21, 2009 11:11 am

### Re: 10062 - Tell Me the Frequencies!

I have change My Code. But Still W/A

My Code is
Code: Select all
`#include<iostream>//#include<conio.h>using namespace std;int flag=0;void p(char a,int n,int cf[100],int c[100]){   int j=0,i=0;   if(a=='\n')   {    n++;    for(i=0;i<96;i++)    {      for(j=0;j<95;j++)      {         if(cf[j]>cf[j+1])         {           swap(cf[j],cf[j+1]);           swap(c[j],c[j+1]);         }         else if((cf[j]==cf[j+1]&&c[j]<c[j+1]))         {           swap(cf[j],cf[j+1]);           swap(c[j],c[j+1]);         }      }    }    if(flag==1)        cout<<endl;    flag=1;    for(j=0;j<96;j++)    {      if(cf[j]&&c[j])      cout<<c[j]<<' '<<cf[j]<<endl;      c[j]=0;    }    int b=0;   }}int main(){   freopen("in.txt","r",stdin);   char a;   int i=0;   int cf[100];   for(i=0;i<100;i++)      {         cf[i]=0;      }   int n=0;   while(1)   {     int c[100];     if((a=getchar())==EOF)     {        a='\n';        p(a,n,cf,c);        break;     }      i=0;      int x=(int)a;      if(x>=32&&x<=128)      {         i=x-32;         //cout<<i;         c[i]=i+32;         cf[i]++;      }     p(a,n,cf,c);   }   //getch();   return 0;}`

I Have check uvatoolkit all my I/O are OK. But Still W/A
Last edited by noor_aub on Fri Aug 13, 2010 11:15 am, edited 1 time in total.
noor_aub
New poster

Posts: 26
Joined: Sat Aug 22, 2009 12:16 pm

### Re: 10062 - Tell Me the Frequencies!

I can't see why I am getting WA. I tried to read the older post and got more confused. Am I missing something or there is something stupid with the dataset?
Code: Select all
`#include<cstdio>#include<sstream>#include<cstdlib>#include<cctype>#include<cmath>#include<algorithm>#include<set>#include<queue>#include<stack>#include<list>#include<iostream>#include<fstream>#include<numeric>#include<string>#include<vector>#include<cstring>#include<map>#include<iterator>using namespace std;#define REP(i,n) for(int i=0; i<(n); i++)#define ALL(x) x.begin(), x.end()#define pb push_back#define sz size()typedef pair<int,int> pii;bool comp( pii a, pii b ) {    if( a.second == b.second ) return a.first > b.first;    else return a.second < b.second;}int main() {     char line[1005];    bool newln = 0;    while( gets( line ) ) {        char freq[500] = {};         int len = strlen( line );        REP(i,len) freq[ line[i] ] ++;         vector< pii > v;        REP(i,500) if( freq[i] ) v.pb( make_pair( i, freq[i] ) );        sort( ALL(v), comp );        if( newln ) cout << endl; newln = 1;        REP(i,v.sz) cout << v[i].first <<" " << v[i].second << endl;    }    return 0;}`
fahim
#include <smile.h>

smilitude
Experienced poster

Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

### 10062 - Tell Me the Frequencies!

any body plz help me with my code

#include <stdio.h>

int main()
{
int i,j,k,n[100],ar[100],asc,temp,e=1;
char a[1005];
while(gets(a))
{
if(e!=1)
{
printf("\n");
}
e=0;
for(i=0;i<=100;i=i+1)
{
n[i]=1;
}
n[0]=1;
k=0;
for(i=0;a[i];i=i+1)
{
if(a[i]==1)
{
continue;
}
ar[k]=a[i];
for(j=i+1;a[j];j=j+1)
{
if(a[i]==a[j])
{
n[k]=n[k]+1;
a[j]=1;
}
}
a[i]=1;
k=k+1;
}
for(i=0;i<k;i=i+1)
{
for(j=0;j<k-1;j=j+1)
{
if(ar[j]<ar[j+1])
{
temp=ar[j];
ar[j]=ar[j+1];
ar[j+1]=temp;
temp=n[j];
n[j]=n[j+1];
n[j+1]=temp;
}
}
}
for(i=0;i<k;i=i+1)
{
for(j=0;j<k-1;j=j+1)
{
if(n[j]>n[j+1])
{
temp=ar[j];
ar[j]=ar[j+1];
ar[j+1]=temp;
temp=n[j];
n[j]=n[j+1];
n[j+1]=temp;
}
}
}
for(i=0;i<k;i=i+1)
{
if(ar[i]>=33 && ar[i]<=127)
{
printf("%d %d\n",ar[i],n[i]);
}

}

}
return 0;
}
rage009
New poster

Posts: 1
Joined: Thu Nov 24, 2011 9:00 am

### Re: 10062 - Tell Me the Frequencies!

Hello
Why am I getting WA?

Code: Select all
`import java.io.*;import java.util.*;class Main {    private static final char NEW_LINE = '\n';    public static void main(String[] args) {        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 1024 * 1024);        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));        int intchr;        try {            Map<Integer, Entry> map = new HashMap<Integer, Entry>();            while ((intchr = reader.read()) != -1) {                if (intchr == NEW_LINE || intchr == '\r') {                    if (map.isEmpty()) {                        continue;                    }                    printResult(writer, map, true);                    writer.write("\n");                    map = new HashMap<Integer, Entry>();                    continue;                }                Entry integer = map.get(intchr);                if (integer == null) {                    integer = new Entry(intchr);                    map.put(intchr, integer);                }                integer.frequency++;            }            printResult(writer, map, false);            writer.flush();        } catch (IOException e) {        }    }    private static void printResult(BufferedWriter writer, Map<Integer, Entry> map, boolean printLastN) throws IOException {        Entry[] values = map.values().toArray(new Entry[map.size()]);        Arrays.sort(values, new Comparator<Entry>() {            public int compare(Entry o1, Entry o2) {                int compare = o1.compareTo(o2);                if (compare == 0) {                    return o2.value - o1.value;                }                return compare;            }        });        for (int i = 0; i < values.length; i++) {            Entry value = values[i];            writer.write(String.valueOf(value.value));            writer.write(" ");            writer.write(String.valueOf(value.frequency));            if (i + 1 == values.length && !printLastN) {                continue;            }            writer.write("\n");        }    }    static class Entry implements Comparable<Entry> {        int frequency;        final int value;        Entry(int value) {            this.value = value;        }        @Override        public boolean equals(Object o) {            if (this == o) return true;            if (o == null || getClass() != o.getClass()) return false;            Entry entry = (Entry) o;            if (value != entry.value) return false;            return true;        }        @Override        public int hashCode() {            return value;        }        public int compareTo(Entry o) {            return frequency - o.frequency;        }    }}`
sith
Learning poster

Posts: 67
Joined: Sat May 19, 2012 7:46 pm

### Re: 10062 - Tell Me the Frequencies!

Don't print a blank line at the end of the output.
brianfry713
Guru

Posts: 1742
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10062 - Tell Me the Frequencies!

My solution doesn't print last line!
sith
Learning poster

Posts: 67
Joined: Sat May 19, 2012 7:46 pm

### Re: 10062 - Tell Me the Frequencies!

http://ideone.com/uh8sz

For the sample input, your output is:
Code: Select all
`67 166 265 349 150 251 3`
AC output is:
Code: Select all
`67 166 265 349 150 251 3`
brianfry713
Guru

Posts: 1742
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10062 - Tell Me the Frequencies!

There is no extra line in my IDE(IntellijIDEa) for this solution, but I still get WA

Code: Select all
`import java.io.*;import java.util.*;class Main {    private static final char NEW_LINE = '\n';    public static void main(String[] args) {        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));        int intchr;        try {            Map<Integer, Entry> map = new HashMap<Integer, Entry>();            while ((intchr = reader.read()) != -1) {                if (intchr == NEW_LINE || intchr == '\r') {                    if (map.isEmpty()) {                        continue;                    }                    printResult(writer, map, true);                    writer.write("\n");                    map = new HashMap<Integer, Entry>();                    continue;                }                Entry integer = map.get(intchr);                if (integer == null) {                    integer = new Entry(intchr);                    map.put(intchr, integer);                }                integer.frequency++;            }            printResult(writer, map, false);            writer.flush();        } catch (IOException e) {        }    }    private static void printResult(BufferedWriter writer, Map<Integer, Entry> map, boolean printLastN) throws IOException {        Entry[] values = map.values().toArray(new Entry[map.size()]);        Arrays.sort(values, new Comparator<Entry>() {            public int compare(Entry o1, Entry o2) {                int compare = o1.compareTo(o2);                if (compare == 0) {                    return o2.value - o1.value;                }                return compare;            }        });        for (int i = 0; i < values.length; i++) {            Entry value = values[i];            writer.write(String.valueOf(value.value));            writer.write(" ");            writer.write(String.valueOf(value.frequency));            if (i + 1 == values.length && !printLastN) {                continue;            }            writer.write("\n");        }    }    static class Entry implements Comparable<Entry> {        int frequency;        final int value;        Entry(int value) {            this.value = value;        }        @Override        public boolean equals(Object o) {            if (this == o) return true;            if (o == null || getClass() != o.getClass()) return false;            Entry entry = (Entry) o;            if (value != entry.value) return false;            return true;        }        @Override        public int hashCode() {            return value;        }        public int compareTo(Entry o) {            return frequency - o.frequency;        }    }}`
sith
Learning poster

Posts: 67
Joined: Sat May 19, 2012 7:46 pm

### Re: 10062 - Tell Me the Frequencies!

Try putting a newline at the end of the last input line.
brianfry713
Guru

Posts: 1742
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

PreviousNext