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

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Fri Mar 05, 2004 7:48 am

Well I ran your code using VC 6.0, and it gave me RTE for the sample input.

One thing I have noticed in your code is you are trying to use Class and dynamic memory initialization. This is hardly necessary to solve acm problem.

Just take a set of input, process and give output and go onto take input for next set.

I did not inspect your code, but the runtime error is most probably due to
improper way of handling dynamic memory.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Fri Mar 05, 2004 5:22 pm

don't leave your ids here.
"Everything should be made simple, but not always simpler"

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Sat Mar 27, 2004 10:01 pm

Unfortunately the following C++ code takes almost 7 seconds.... for me it means this problem was set up only for C (printf/scanf addicted) or pascal fans....

[cpp]
#include <iostream>
#include <algorithm>
#include <string>
#include <map>

using namespace std;

int main(int argv, char **args) {

int casos = 0;
cin >> casos;
map<string,long> meuMapa;
for(int i=0;i!=casos;i++) {

if(i!=0) cout << endl;

int num;
cin >> num;

meuMapa.clear();

for(int z=0;z!=num;z++) {

string s;
cin >> s;


}


}


}



[/cpp]

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Sat Mar 27, 2004 10:05 pm

i have just changed CIN to SCANF in the 3 input lines and it ran in 0.6 second. hmm.... shouldnt the time limit be extended to allow other competitors who use java/c++ functions to also get it right?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Sun Mar 28, 2004 1:42 am

It's well known , that object stream as input is much slower than printf / scanf pair.
Your proposal means, that you have to create distinct rankings for every lnguage in which we can solve any problem. It's not fair for me ... Why people who solve problem in i.e. C, can be treated diffrent from C++ users ? Or Java users ?
I don't want to be offensive, but if you want to improve your time, sometimes you must change your coding style and code something in pure C or Pascal instead of C++ or Java ;-) Personally I solve all problems in C (excluding one or two). Pay attention that in some problems is written explicite, that you should use C-like input ...

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Mon Mar 29, 2004 4:00 pm

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
New poster
Posts: 33
Joined: Tue Apr 27, 2004 7:41 pm
Location: Santa Clara / Mountain View, CA, USA
Contact:

755 What should I do? Sorted when Inserting

Post by 20717TZ » Sat May 08, 2004 4:12 pm

755 What should I do? Sorted when Inserting
I Believe I Can - leestime.com

20717TZ
New poster
Posts: 33
Joined: Tue Apr 27, 2004 7:41 pm
Location: Santa Clara / Mountain View, CA, USA
Contact:

755 why TLE my source program is simple (i guess),????

Post by 20717TZ » Sat May 08, 2004 7:17 pm

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=='-')continue;
t+=Translation.find(s)/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]
I Believe I Can - leestime.com

emka
New poster
Posts: 10
Joined: Sat Oct 19, 2002 7:20 am
Location: Singapore
Contact:

755 - "487-3279" WA

Post by emka » Mon Jun 21, 2004 5:58 am

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 == 'A' || s == 'B' || s == 'C' || s == '2' ) dig = 2;
else if ( s == 'D' || s == 'E' || s == 'F' || s == '3' ) dig = 3;
else if ( s == 'G' || s == '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]
-mk

Bug!
New poster
Posts: 24
Joined: Thu Oct 30, 2003 10:19 am

755 - Need help for fast algorithm

Post by Bug! » Tue Jul 27, 2004 5:42 am

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... :cry:
can we use qsort with this prob???

Thx in advance...
Andre :lol:

Andrew Neitsch
New poster
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm

Post by Andrew Neitsch » Tue Jul 27, 2004 5:56 pm

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!
New poster
Posts: 24
Joined: Thu Oct 30, 2003 10:19 am

Post by Bug! » Wed Jul 28, 2004 3:02 am

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 :D

Thx...
Andre

Andrew Neitsch
New poster
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm

Post by Andrew Neitsch » Wed Jul 28, 2004 6:50 am

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!
New poster
Posts: 24
Joined: Thu Oct 30, 2003 10:19 am

Post by Bug! » Wed Jul 28, 2004 11:23 am

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
Last edited by Bug! on Tue Aug 03, 2004 9:01 am, edited 1 time in total.

Andrew Neitsch
New poster
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm

Post by Andrew Neitsch » Wed Jul 28, 2004 6:28 pm

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.

Post Reply

Return to “Volume 7 (700-799)”