755 - 487-3279

[technobug]

Hello Dominik,

I know.... I even tought about suggesting such a thing, different ranklists and time limits for different programming languages.... i believe my point is strong as someone who codes java doesnt know a thing about c and would not be able to solve a problem in a contest due to his language. And the other way around.... java users know how easy it is to play with geometric problems due to its api...

Anyhow, I know its not worthy and could not be used to measure two programmers from two distinct languages... so it sucks....

Anyhow it would be nice to add a note to this problem saying that its impossible to use cin/string as it is done with some problems you have mentioned.

I had a problem with Doublets (dunno the number) which I think might be the same.... use char* instead of string....

Summing up, your point is stronger than mine therefore it would be nice to add the small ref saying that cin and string might be too slow for this thing

Guilherme

[20717TZ]

755 What should I do? Sorted when Inserting

[20717TZ]

755 why TLE my source program is simple (i guess),????
here is my C++ code:
[cpp]
#include <stdio.h>
#include <iostream.h>
#include <string>
#include <map>
#include <algorithm>
#define MAX 1000
using namespace std;

map<string,long> PhoneBook;
string Translation="000011112ABC3DEF4GHI5JKL6MNO7PRS8TUV9WXY";

void fnFormat(string &s)
{
int len=s.length();
string t="";

for(int i=0;i<len;i++)
{
if(s[i]=='-')continue;
t+=Translation.find(s[i])/4+'0';
}
s=t;
}

void fnPrint()
{
int mark=0;
map<string,long>::const_iterator i=PhoneBook.begin();

for(i=PhoneBook.begin();i!=PhoneBook.end();i++)
{
if((*i).second>1)
{
mark=1;
printf("%s-%s %d\n",(*i).first.substr(0,3).c_str(),
(*i).first.substr(3).c_str(),(*i).second);
}
}

if(mark==0)
printf("No duplicates.\n");
}

void main()
{
FILE* fp=fopen("Input.txt","r");
int n,i;
long m,j;
char cs[MAX]="";
string s="";

//the blue colour means multiple input
fscanf(fp,"%ld",&n);

for(i=0;i<n;i++)
{
PhoneBook.clear(); //reset
fscanf(fp,"%ld",&m);
for(j=0;j<m;j++)
{
fscanf(fp,"%s",cs);
s.assign(cs);

fnFormat(s);
PhoneBook[s]++;
}
if(i!=0) printf("\n");//newline for multiple input

fnPrint();
}
}
[/cpp]

[emka]

Hi,

I've tested my code with all possible input characteristics... and seems to be working correctly....
but when I tried to submit it, it keeps giving me WA.... can anyone find where the the bugs are...

[c]
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

long list[100005];
long cnt, n;

long numerize( char * s ){
unsigned int i, lens = strlen(s);
long result = 0;
int dig;
for ( i = 0; i < lens; i++ ){
dig = -1;
if ( s[i] == 'A' || s[i] == 'B' || s[i] == 'C' || s[i] == '2' ) dig = 2;
else if ( s[i] == 'D' || s[i] == 'E' || s[i] == 'F' || s[i] == '3' ) dig = 3;
else if ( s[i] == 'G' || s[i] == 'H' || s[i] == 'I' || s[i] == '4' ) dig = 4;
else if ( s[i] == 'J' || s[i] == 'K' || s[i] == 'L' || s[i] == '5' ) dig = 5;
else if ( s[i] == 'O' || s[i] == 'N' || s[i] == 'O' || s[i] == '6' ) dig = 6;
else if ( s[i] == 'P' || s[i] == 'R' || s[i] == 'S' || s[i] == '7' ) dig = 7;
else if ( s[i] == 'T' || s[i] == 'U' || s[i] == 'V' || s[i] == '8' ) dig = 8;
else if ( s[i] == 'W' || s[i] == 'X' || s[i] == 'Y' || s[i] == '9' ) dig = 9;
else if ( s[i] == '0' ) dig = 0;
else if ( s[i] == '1' ) dig = 1;
if ( dig >= 0 ){
result *= 10;
result += dig;
}
}
return result;
}

void printformat( int num, int dig ){
int dignum = 0, x = num, i;
while ( x > 0 ){
dignum++;
x /= 10;
}

for (i = 0; i < (dig-dignum); i++)printf("0");
if ( num > 0 ) printf("%d", num);
}

void printnumber( long num ){
printformat( (int)num/10000, 3 );
printf("-");
printformat( num%10000, 4 );
}

int bcompare (const void * a, const void * b)
{
return (*(int*)a)-(*(int*)b);
}

int main(void){
long t;
int first = 1;
for ( scanf("%ld", &t); t > 0; t-- ){
char ss[300];
int duplicate = 0, i;

scanf( "%ld", &n );
cnt = 0;

for ( ; n > 0; n-- ){
scanf("%s", ss);
list[cnt++] = numerize(ss);
}
qsort( list, cnt, sizeof(long), bcompare );

if ( first ) first = 0;
else printf("\n");

for ( i = 0; i < cnt-1; i ++ ){
if ( list[i] == list[i+1] ){
int j;
for ( j = 2; list[i+j] == list[i]; j++ );
printnumber(list[i]);
printf(" %d\n", j);
duplicate = 1;
i = i+j-1;
}
}

if ( !duplicate ) printf("No duplicates.\n");
}
return 0;
}[/c]

[Bug!]

Hi all, I've got TLE with this prob, i wonder how can my program got TLE..
This is my algorithh...

- take input
- remove '-' from the input
- decode to normal form
- find in the array using binary search
- if we find them just add total
- else insert new number into an array, and then sorting data using qsort
- print output

simple, but still confusing me...
can we use qsort with this prob???

Thx in advance...
Andre

[Andrew Neitsch]

This is a problem where I would use C++ maps for simplicity. When I first solved it, I did not know about them, so I just had a huge array of size ten million; for each number n, I would just increment T[n]; then when all the numbers were read, just step through the array and print the required information.

Since there could be up to 100,000 of a number, and 10 million * sizeof(int) > memory limit, I had to store 24 bit integers.

In conclusion: if the problem can be solved with such a ridiculous algorithm, and you are timing out on binary search, there is a problem with your implementation.

Hold on: why are your qsorting? When your search terminates, without finding the number, you know where the number is supposed to go, so just insert it there after shifting all the succeeding elements right.

qsort() is order O(n^2) on already-sorted data, so you are running an O(n^3) algorithm many times on inputs with n=100000. There is your TLE.

[Bug!]

Hi Andrew... I've changed my code n remove qsort, n just insert it into an array.. But still got TLE.

Here's my new pseudocode...
- take input
- remove '-' from the input
- decode to normal form
- find in the array using binary search
- if we find them just add total
- else insert new number into an array from the current position
- print output

This is my stat...

full program : 0:10.053 s
input and decode : 0:00.986 s
Only Input : 0:00.268 s

I can't imagine how can people got AC only in 0:00.330 s

Thx...
Andre

[Andrew Neitsch]

Since there are n numbers, the search is O(log n), and the insertion is linear, your algorithm is O(n^2 log n),

which is quite slow if n=100000.

why is your decoding taking such a long time? Are you calling isdigit() or something like that? The linux-on-intel architecture is very mean with respect to function call overhead.

As for a faster algorithm, try using C++ maps. They are one of only about 4 reasons I can think of to use C++. Do this

#include <map>
using namespace std;

map<int,int> T;
/* This says you want to map integers to
integers, as opposed to something like
strings to ints or ints to strings... */

int main() {
int phonenumber,occurrences;
...
while(numcases--) {
T.clear(); /* clear the map */
foreach input {
T[phonenumber]++;
/* This looks up phonenumber in the map;
if it is not in the map, it creates a
map entry with count set to 0, and
then increments that */
}
map<int,int>::iterator ptr=T.begin();
map<int,int>::iterator end=T.end();
do{
phonenumber=ptr->first;
occurrences=ptr->second;
...
} while(++ptr!=end);
}
}

The map is implemented as a 'set' of 'pairs' (where the 'first' and 'second' come from) which is implemented as a 'Red Black Tree' or something equally mysterious. There is a lot of extra overhead, but it is usually fast enough, and faster than implementing your own 'Red Black Trees'. The stuff they do is mostly O(log n), so that will make your algorithm O(n log n) which should be good enough.

Think of maps as magical arrays that take arbitrary ordered types as indices, and only create the entries if you need them.

C++ is very nearly a superset of C, so you can #include <stdio.h> and do all your scanf()ing and such, and need not change any of your non-storing-phone-numbers code when using the above.

Hopefully that helps. Also note I have not bothered actually compiling or testing the code above, so you may encounter problems.

[Bug!]

I can't use visual C++.... :p
Maybe u can look at my code and see what's wrong with this...
I still confuse why the process need more than 9 s to solve it...

[c]
*code removed*
[/c]

Thx...
Andre

[Andrew Neitsch]

Suppose you are given 100000 distinct phone numbers in decreasing order. Then you will have to move about 100000*99999/2 pieces of information. If you could do that in one clock cycle on the judge (which you cannot), with the judge running at 800MHz, it would take 6.24 seconds. Since moving the data will take about thirty clock cycles if you optimize it in assembly, just moving the data to do the insertion will take 180s, or three minutes. And that is just one input case. That is why your algorithm is too slow.

No amount of optimizing your current algorithm will fix this; you need to find an algorithm that does less than linear work on inserting into a sorted data structure. Using a linked list would allow constant time insertions, but then searches would be linear as well. You need a data structure that allows a sorted list to be searched and inserted in sub-linear time. A Red Black tree is one such structure, so you can either use C++ maps or implement Red Black Trees yourself.

Why can you not use C++? g++ ,Visual C++, and several others are free downloads.

[Bug!]

Hi... I try to changed my algorithm n it can passed TLE.. But Now i've got WA for this prob.. Can u give me any critical i/o ??
Thx a lot..
Andre

[watershed]

I use C++ map , but I still got TLE
who can fix my program
I know my code isn't very good
thanks for your help.....

[cpp] CUT ^^"... [/cpp]

[Andrew Neitsch]

Why on earth are you using a map<char,char> to get the value of each letter? That's insane. Use a switch statement.

Do

map<int,int> phonenumbercount;

When you have the phone number as an INT (which you don't use any C++, ever, to figure out), do phonenumbercount[number]++.

The print your phone number with printf("%03d-%04d",n/10000,n%10000);

The only thing you need from C++ is a single map, indicating how many of each phone number there are, and an iterator to step through them afterwards.

[watershed]

Why on earth are you using a map<char,char> to get the value of each letter? That's insane. Use a switch statement.

I think fast for the way , but actually I wrong

Do
map<int,int> phonenumbercount;
When you have the phone number as an INT (which you don't use any C++, ever, to figure out), do phonenumbercount[number]++.
The print your phone number with printf("%03d-%04d",n/10000,n%10000);
The only thing you need from C++ is a single map, indicating how many of each phone number there are, and an iterator to step through them afterwards.

thanks your correction and help , I got AC.....

[tetuya]

I've gotten WA for long time.
I tried test input on this board and mine.
please tell me my mistake or some advice.
[cpp]

Accepted nasty my code is cleared.

And Thank you Hiloshi!

[/cpp]

thank you