10062 - Tell me the frequencies!

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

Moderator: Board moderators

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

10062 -WA- Tell Me the Frequencies!

Post by sazzadcsedu » Sun Jan 18, 2009 11:52 am

whats wrong with my code??
WA.

Code: Select all

 #include<stdio.h>
            #include<memory.h> 


              int main()



			  { 
				  char str[1002];
				  int i,a,k,min,j,dis_chr;
				  int count[256];
 
				 
				  while(gets(str))

				  { 
                       dis_chr=0; 
					   memset(count,0,sizeof(count));

					  for(i=0;str[i];i++)

					  { 
						  a=int(str[i]);
						  //printf("%d\n",a);

						  if(count[a]==0)
                             dis_chr+=1; 

						  count[a]+=1;

					  }

					//  printf("%d\n",);
                     
                        
					    for(i=1;i<=dis_chr;i++)
						{ 
							
					            min=1010;  
					    
					       for(j=256;j>=0;j--)

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

							}
                               printf("%d %d\n",k,count[k]);
							   count[k]=1100;
							  
                                  
						}

						 printf("\n");
				  }
				      return 0;
			  }
[\code]
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

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

Re: 10062 - Tell Me the Frequencies!

Post by mf » Mon Jan 19, 2009 5:01 am

sazzadcsedu wrote: for(j=256;j>=0;j--)

{
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.

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

10062 - Tell Me the Frequencies!

Post by bm_anas » Sat May 30, 2009 9:14 pm

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=0;
ascii=i;
}

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

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

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,frq);

}

return 0;
}

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

Re: 10062 - Tips to solve this problem

Post by allenlam » Wed Jun 17, 2009 4:49 pm

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 bubblesort
std::stable_sort(), std::list<T>.sort(), std::stable_partition().
output

Code: Select all

121 1
117 1
109 1
108 1
116 2
115 2
114 2
111 2
101 2
32 3
98 4

112 1
110 1
84 1
62 1
60 1
101 2
98 2
95 2
46 2
44 2
32 2
114 3
111 3
108 3
105 3
100 3
97 3
41 3
40 3
58 6
115 8
116 10
The blank line between cases issue has been talked hundred times in previous messages. I don't repeat it here.

Good luck.

etameem
New poster
Posts: 5
Joined: Tue Jul 21, 2009 11:11 am
Location: (CSE, JU) Dhaka,Bangladesh
Contact:

Re: 10062 - Tell Me the Frequencies!

Post by etameem » Mon Aug 24, 2009 4:52 pm

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;
    }



i am getting a WA. please help me with this...

User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 10062 - Tell Me the Frequencies!

Post by tryit1 » Tue Aug 25, 2009 1:10 am

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.

etameem
New poster
Posts: 5
Joined: Tue Jul 21, 2009 11:11 am
Location: (CSE, JU) Dhaka,Bangladesh
Contact:

Re: 10062 - Tell Me the Frequencies!

Post by etameem » Tue Aug 25, 2009 3:59 pm

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 ???

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

Re: 10062 - Tell Me the Frequencies!

Post by noor_aub » Sun Nov 08, 2009 11:47 am

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
Thanks in advance.
Last edited by noor_aub on Fri Aug 13, 2010 11:15 am, edited 1 time in total.

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Re: 10062 - Tell Me the Frequencies!

Post by smilitude » Fri Jan 29, 2010 7:31 am

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>

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

10062 - Tell Me the Frequencies!

Post by rage009 » Wed Dec 14, 2011 2:26 pm

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=1;
}
n[0]=1;
k=0;
for(i=0;a;i=i+1)
{
if(a==1)
{
continue;
}
ar[k]=a;
for(j=i+1;a[j];j=j+1)
{
if(a==a[j])
{
n[k]=n[k]+1;
a[j]=1;
}
}
a=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>=33 && ar<=127)
{
printf("%d %d\n",ar,n);
}

}

}
return 0;
}

vril4296
New poster
Posts: 2
Joined: Wed Mar 28, 2012 1:20 pm

10062 - what's different???

Post by vril4296 » Wed Mar 28, 2012 1:30 pm

i get ac when i use gets, but get wa when i use fgets
can anyone tell me why???
thanks~

code use fgets

Code: Select all

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

int main()
{
    char text[1001];    //Maximum length of each line is 1000.(max 1001,include '\n' or '\r')
    int ascii[95],length,i,j,n=0;  //The given lines will contain none of the first 32 or last 128 ASCII characters.((0~31,)32~127,total 95)
    while(fgets(text,1001,stdin)!=NULL){
        if(n>0)
            printf("\n");
        for(i=0;i<95;i++)
            ascii[i]=0;
        length=strlen(text)-1;
        for(i=0;i<length;i++)
            ascii[text[i]-32]++;
        for(i=1;i<=length;i++)
            for(j=94;j>=0;j--)
                if(ascii[j]==i)
                    printf("%d %d\n",j+32,i);
        n++;
    }
    return 0;
}
I'm sorry for my poor English!

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

Re: 10062 - what's different???

Post by brianfry713 » Thu Mar 29, 2012 12:58 am

It could be because fgets includes the newline characters in the string but gets does not.
Check input and AC output for thousands of problems on uDebug!

vril4296
New poster
Posts: 2
Joined: Wed Mar 28, 2012 1:20 pm

Re: 10062 - what's different???

Post by vril4296 » Thu Mar 29, 2012 1:23 am

but I have considered about the newline

fgets : length=strlen(text)-1
gets : length=strlen(text)

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

Re: 10062 - what's different???

Post by brianfry713 » Fri Mar 30, 2012 3:06 am

What would happen to your code if it's encoded in DOS format "\r\n" instead of UNIX "\n"? How about if there is no newline on the last line of the input but it ends with EOF?

From the problem description "Of course lines may end with ‘\n’ and ‘\r’ but always keep those out of consideration."
Check input and AC output for thousands of problems on uDebug!

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 10062 - Tell Me the Frequencies!

Post by sith » Fri Jun 29, 2012 6:43 pm

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;
        }
    }

}


Post Reply

Return to “Volume 100 (10000-10099)”