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 » Mon Dec 18, 2006 10:21 pm

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

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

Post by kana » Tue Dec 19, 2006 9:18 pm

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 » Mon Oct 06, 2008 6:34 pm

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 » Mon Jun 08, 2009 4:18 am

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 » Mon Jun 08, 2009 10:31 am

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 » Tue Nov 03, 2009 7:25 pm

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 » Thu Nov 05, 2009 7:09 pm

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 » Thu Nov 05, 2009 7:56 pm

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 » Sat Jul 31, 2010 6:08 am

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 » Fri Feb 18, 2011 10:44 pm

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 » Thu Sep 06, 2012 5:58 am

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 » Thu Sep 06, 2012 10:56 pm

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 » Fri Sep 07, 2012 2:43 am

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 » Fri Sep 07, 2012 8:15 pm

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 » Sun Sep 09, 2012 5:19 am

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

Post Reply

Return to “Volume 7 (700-799)”