755 - 487--3279

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

[kana]

thanks again !!!

[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

[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!

[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

Print a blank line between datasets.

and capitalization in this line is wrong:

System.out.println("No Duplicates.");

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

[Jehad Uddin]

Try to use manual power function and also see the previous posts and I/O s,

[calicratis19]

I tried with manual power function.But it is no use. Still wa.

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

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

[c0debreak]

Can anyone provide a test case ?

Code: Select all

Cut after AC

[brianfry713]

Print a blank line between datasets.

[c0debreak]

Hi, Thanks,

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

[brianfry713]

On my system, for input:

Code: Select all

1

2
9999999
9999999

Your code produces output:

Code: Select all

999-9999 10

[c0debreak]

Hmm, the case is passed by increasing hash size .. still WA...code updated