755 - 487--3279

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

Moderator: Board moderators

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post 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.
Ami ekhono shopno dekhi...
HomePage

kana
New poster
Posts: 19
Joined: Mon Mar 13, 2006 6:03 pm
Location: dhaka

Post by kana »

thanks again !!! :)

lnr
Experienced poster
Posts: 142
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

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

Post 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

panda_coder
New poster
Posts: 7
Joined: Mon Jun 08, 2009 4:02 am

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

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

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

Re: 755 - 487-3279

Post 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.");

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 755 - 487-3279

Post 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;
}
Heal The World

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 755 - 487-3279

Post by Jehad Uddin »

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

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

Re: 755 - 487-3279

Post by calicratis19 »

I tried with manual power function.But it is no use. Still wa. :o :o
Heal The World

kamiloj
New poster
Posts: 9
Joined: Fri Dec 29, 2006 3:34 pm

Re: 755 - 487-3279

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

Dark Lord
New poster
Posts: 2
Joined: Mon Sep 27, 2010 11:27 am

Re: 755 - 487-3279

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

c0debreak
New poster
Posts: 10
Joined: Mon Aug 13, 2012 5:32 am

755 - (487--3279) - WA ?

Post by c0debreak »

Can anyone provide a test case ?

Code: Select all

Cut after AC
Last edited by c0debreak on Tue Sep 11, 2012 2:22 am, edited 3 times in total.

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

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

Post by brianfry713 »

Print a blank line between datasets.
Check input and AC output for thousands of problems on uDebug!

c0debreak
New poster
Posts: 10
Joined: Mon Aug 13, 2012 5:32 am

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

Post by c0debreak »

Hi, Thanks,

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

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

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

Post by brianfry713 »

On my system, for input:

Code: Select all

1

2
9999999
9999999
Your code produces output:

Code: Select all

999-9999 10
Check input and AC output for thousands of problems on uDebug!

c0debreak
New poster
Posts: 10
Joined: Mon Aug 13, 2012 5:32 am

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

Post by c0debreak »

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

Post Reply

Return to “Volume 7 (700-799)”