Page 6 of 8

Posted: Mon Dec 18, 2006 10:21 pm
by Jan
Check the I/O sets...

Input:

Code: Select all

1

40
0U--4N712
---X2-KN-U-75
VR-J37G--3
85W-0Y6-V
85W-0Y6-V
85W-0Y6-V
--N-6AV4-NK
--XL----F-PO--B-0
-P-10167P
7--R8YME-N
P-U-1O6W-----1
X-KFK87--L
YFX63K-N
-3-73G---ELH
--2RD-6-IJ-Y
P2--SJ9G9
P2--SJ9G9
O-1----2287-2
-DC-C1L-3V
7963V68
U-66X52M
U-66X52M
-8-16F5TG
---YN-32E5-K
---YN-32E5-K
4--KDJ-PV2
4--KDJ-PV2
P27-42L2
P27-42L2
-MIWO-W5D
44M7675
F---6-7R80M
T5S6U1-P
T5S6U1-P
T5S6U1-P
BUM85L--3
BUM85L--3
DB1E---046
36O--7-1W2
-R--52-P-Y7H
Output:

Code: Select all

286-8553 2
453-5782 2
727-4252 2
727-5949 2
857-6817 3
859-0968 3
866-9526 2
963-2355 2
Hope you get accepted.

Posted: Tue Dec 19, 2006 9:18 pm
by kana
thanks again !!! :)

Re: why cpp with class usually be judged Compile Error ?

Posted: Mon Oct 06, 2008 6:34 pm
by lnr
Reason of compile error:

code.cpp: In member function 'bool TelNumber::operator<(TelNumber&)':
code.cpp:20: error: '_stricmp' was not declared in this scope

755) 487-3279 time limit exceeded...I'm desperate :(

Posted: Mon Jun 08, 2009 4:18 am
by panda_coder
This

Code: Select all

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;


public class Main {

	static class phoneNumber implements Comparable<phoneNumber>{
		String phone;
		int count;
		phoneNumber(String phone, int count) {
			this.phone = phone;
			this.count = count;
		}
		String getPhone() {
			return phone;
		}
		
		void incrementCount() {
			count++;
		}
		
		int getCount() {
			return count;
		}
		@Override
		public int compareTo(phoneNumber arg0) {
			return phone.compareTo(arg0.getPhone());
		}
	}
	
	public static void main(String[] args) throws Exception { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		LinkedList<phoneNumber> result = new LinkedList();
		int testSet = Integer.parseInt(br.readLine());
		
		for(int j=0; j<testSet; j++) {
		br.readLine();
		int testCase = Integer.parseInt(br.readLine()); 
		result.clear();
		for(int t = 0; t< testCase; t++) {
			String input = br.readLine().trim();
	 		StringBuffer phoneNum = new StringBuffer();
	 		int inputlength = input.length();
			for(int k = 0; k< inputlength; k++) {
				char chr;
				chr = input.charAt(k);
				if(chr != '-' && chr != ' ') {
					if((int)chr >= 48 && (int)chr <=57) { // ASCII code? 0 : 48
						phoneNum.append(chr);
					}
					else if(chr >= 'A' && chr <= 'Y' && chr != 'Q' && chr != 'Z') {
						int value = ((int)chr) - 65;
						if(value > 16) value = value -1;
						value = 2 + (int)value/3;   // 0,1,2 : A
						phoneNum.append(value);
					}
					if(phoneNum.length() == 3)
						phoneNum.append('-');
				}
			} 
			String phoneString = phoneNum.toString();
			boolean flag = false;
			int size = result.size();
			
			for(int m = 0; m<size; m++) {
				phoneNumber pn = result.get(m);
				if(pn.getPhone().equals(phoneString)) {
					int count = pn.getCount();
					pn.incrementCount();
					flag = true;
					break;
				}
			}
			if(flag == false) {
					result.add(new phoneNumber(phoneString,1));
			}		
		}
		
		
		Collections.sort(result);
		int size = result.size();
		boolean flagDup = false;
		
		for(int i=0; i<size; i++) {
			if(result.get(i).getCount() >= 2) {
				System.out.println(result.get(i).getPhone() + " " + result.get(i).getCount());
				flagDup = true;
			}
		}
		if(flagDup == false) {
			System.out.println("No Duplicates.");
		}
		}
	}
	
}

It keeps giving me time limit exceed.... when I implement it with a hashmap, it gave me the wrong answer..

Do you have ANY suggestion that makes this more effective, or any problem in the code that you can see?

Any comment would be welcomed, please!

Re: 755 - 487-3279

Posted: Mon Jun 08, 2009 10:31 am
by mf
Your algorithm is very inefficient.

First, you improperly use LinkedList - instead of iterating on it using iterators, you use LinkedList.get(), which is extremely slow. Actually, it's almost never a good idea to use LinkedList. Use ArrayList when in doubt.

Second, you have this loop that runs for each input phone number:

Code: Select all

             for(int m = 0; m<size; m++) {
                phoneNumber pn = result.get(m);
                if(pn.getPhone().equals(phoneString)) {
                   int count = pn.getCount();
                   pn.incrementCount();
                   flag = true;
                   break;
                }
             }
Well, it's not good. You can't afford to iterate over every number like that when you have millions of them.

You can replace this loop with some data structure, such as HashMap or TreeMap that can efficiently find objects by its key. Or just sort a list of all numbers, including all the duplicates, and remove duplicates after sorting.

Also, you must
http://acm.uva.es/p/v7/755.html wrote:Print a blank line between datasets.
and capitalization in this line is wrong:
System.out.println("No Duplicates.");

Re: 755 - 487-3279

Posted: Tue Nov 03, 2009 7:25 pm
by calicratis19
can anyone tell me why wa.checked all the input above.

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
int i,j,f,y,num,shudho,k,test,mn;
int cnt[10000010],intgr[1000010],store[100020];
char ans[100010][20],str[1000];
bool flag[10000010];

int sort_function( const void *a, const void *b)
{
   return( strcmp((char *)a,(char *)b) );
}

int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d",&test);
    while(test--)
    {
        mn = 0;
        scanf("%d",&num);
        for(j=0,y=0;j<num;j++)
        {
            scanf("%s",str);f=6;shudho=0;
            for(i=0;str[i]!=NULL;i++)
            {
                if(isalpha(str[i]))
                {
                    if(str[i]=='A' ||str[i]=='B' ||str[i]=='C')
                        shudho+=2*pow(10,f--);
                    if(str[i]=='D' ||str[i]=='E' ||str[i]=='F')
                        shudho+=3*pow(10,f--);
                    if(str[i]=='G' ||str[i]=='H' ||str[i]=='I')
                        shudho+=4*pow(10,f--);
                    if(str[i]=='J' ||str[i]=='K' ||str[i]=='L')
                        shudho+=5*pow(10,f--);
                    if(str[i]=='M' ||str[i]=='N' ||str[i]=='O')
                        shudho+=6*pow(10,f--);
                    if(str[i]=='P' ||str[i]=='R' ||str[i]=='S')
                        shudho+=7*pow(10,f--);
                    if(str[i]=='T' ||str[i]=='U' ||str[i]=='V')
                        shudho+=8*pow(10,f--);
                    if(str[i]=='W' ||str[i]=='X' ||str[i]=='Y')
                        shudho+=9*pow(10,f--);
                }
                if(isdigit(str[i]))
                    shudho+=(str[i]-'0')*pow(10,f--);

            }
            if( flag[shudho] )
            {
                cnt[shudho]++;
                if( cnt[shudho]==2 )
                {
                    intgr[y]=shudho;
                    ans[y][0]=shudho/1000000+'0';shudho%=1000000;ans[y][1]=shudho/100000+'0';shudho%=100000;ans[y][2]=shudho/10000+'0';shudho%=10000;
                    ans[y][4]=shudho/1000+'0';shudho%=1000;ans[y][5]=shudho/100+'0';shudho%=100;ans[y][6]=shudho/10+'0';shudho%=10;
                    ans[y][7]=shudho+'0';
                    ans[y][3]='-';
                    k=8;
                    sprintf(str,"%d",y);
                   // puts(str);
                    for(k=0;str[k]!=NULL;k++)
                        ans[y][8+k]=str[k];
                    y++;
                }
            }
            else
            {
                flag[shudho]=1;
                cnt[shudho]=1;
                store[mn++]=shudho;
            }

        }
        qsort((void *)ans, y, sizeof(ans[0]), sort_function);
        for(i=0;i<y;i++)
        {
            j=0;

            for(k=8;ans[i][k]!=NULL;k++)
                str[j++]=ans[i][k];
            str[j]=NULL;
            j = atoi(str);

            ans[i][8]=NULL;
            printf("%s %d\n",ans[i],cnt[intgr[j]]);
        }
        if(y==0)printf("No duplicates.\n");
        for(i=0;i<mn;i++)cnt[store[i]]=flag[store[i]]=0;
        if(test)printf("\n");
    }
    return 0;
}

Re: 755 - 487-3279

Posted: Thu Nov 05, 2009 7:09 pm
by Jehad Uddin
Try to use manual power function and also see the previous posts and I/O s,

Re: 755 - 487-3279

Posted: Thu Nov 05, 2009 7:56 pm
by calicratis19
I tried with manual power function.But it is no use. Still wa. :o :o

Re: 755 - 487-3279

Posted: Sat Jul 31, 2010 6:08 am
by kamiloj
if you are solving it in java avoid TLE use TreeMap, the search is O(nlog2n) but when you end of append all the directory it is sorted, in other hand using hashmap hashset, and other tecniques, cause a TLE.

and of course use a buffer to print, don't print directly because the output is very large.

Re: 755 - 487-3279

Posted: Fri Feb 18, 2011 10:44 pm
by Dark Lord
Hello, Can anyone help me to fix my problem with this code cause i'm getting WA with this solution.
Here is my code....

Code: Select all

#include<stdio.h>
#include<string.h>
#include<vector>
#include<ctype.h>
#include<algorithm>
using namespace std;
#define pb push_back
vector<int> vec;
int main(){
    int t,n;
    char s[100];
    scanf("%d",&t);
    char c[10];
    bool cou=true;
    for(;t>0;t--){
              scanf("%d",&n);
              gets(s);
    bool fou=true;
    for(int i=0;i<n;i++){
            gets(s);
            int j=0;
    for(int i=0;i<strlen(s);i++){
          if(s[i]=='-') continue;
     else if(isdigit(s[i])){c[j]=s[i]; j++;}
     else if(s[i]=='A' || s[i]=='B' || s[i]=='C') {c[j]='2'; j++;} 
     else if(s[i]=='D' || s[i]=='E' || s[i]=='F') {c[j]='3'; j++;}
     else if(s[i]=='G' || s[i]=='H' || s[i]=='I') {c[j]='4'; j++;}
     else if(s[i]=='J' || s[i]=='K' || s[i]=='L') {c[j]='5'; j++;}
     else if(s[i]=='M' || s[i]=='N' || s[i]=='O') {c[j]='6'; j++;}
     else if(s[i]=='P' || s[i]=='R' || s[i]=='S') {c[j]='7'; j++;}
     else if(s[i]=='T' || s[i]=='U' || s[i]=='V') {c[j]='8'; j++;}
     else if(s[i]=='W' || s[i]=='X' || s[i]=='Y') {c[j]='9'; j++;}
     }
     c[j]='\0';
      int a;
      sscanf(c,"%d",&a);
      //printf("%d\n",a);
      vec.pb(a);
  }
  sort(vec.begin(),vec.end());
 vector<int>:: iterator it;
 vector<int>:: iterator wt;
 if(cou==false) printf("\n");
 cou=false;
 for(int i=0;i<vec.size();){
    it=lower_bound(vec.begin(),vec.end(),vec[i]);
    wt=upper_bound(vec.begin(),vec.end(),vec[i]);
    int p=wt-it;
    if((wt-it)>1){
     fou=false;
     sprintf(c,"%d",vec[i]);
     printf("%c%c%c-%c%c%c%c %d\n",c[0],c[1],c[2],c[3],c[4],c[5],c[6],wt-it);
     }
    i+=p;
    }
 if(fou==true) printf("No duplicates.\n");
 vec.clear();
}
return 0;
}
Please,help.

755 - (487--3279) - WA ?

Posted: Thu Sep 06, 2012 5:58 am
by c0debreak
Can anyone provide a test case ?

Code: Select all

Cut after AC

Re: 755 - (487--3279) - WA ?

Posted: Thu Sep 06, 2012 10:56 pm
by brianfry713
Print a blank line between datasets.

Re: 755 - (487--3279) - WA ?

Posted: Fri Sep 07, 2012 2:43 am
by c0debreak
Hi, Thanks,

Now I print blank line between datasets; handled "no duplicates", still WA, code updated in above

Re: 755 - (487--3279) - WA ?

Posted: Fri Sep 07, 2012 8:15 pm
by brianfry713
On my system, for input:

Code: Select all

1

2
9999999
9999999
Your code produces output:

Code: Select all

999-9999 10

Re: 755 - (487--3279) - WA ?

Posted: Sun Sep 09, 2012 5:19 am
by c0debreak
Hmm, the case is passed by increasing hash size .. still WA...code updated