10282 - Babelfish

All about problems in Volume 102. 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
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Mon Sep 26, 2005 2:43 pm

Hi, you have so many mistakes. the reason of RTE is bsearch i think as i changed the line

Code: Select all

if(low==high) {if(strcmp(key,forgn[low])==0) return low; else return 0;} 
to

Code: Select all

if(low>high)
return 0;
then your code gave wrong answer instead of run time error

and your sorting is not working, u know u cant do binary search when ur array is not sorted.

if you think your sorting works, than try this and see the output:

Code: Select all

input

hsjsjs sjsjsj
fdidks sksks
ddosls dkdjkdk
dkjdsk dsksks
adskjs akkaka

your code output after sorting:

hsjsjs sjsjsj
ddosls dkdjkdk
dkjdsk dsksks
adskjs akkaka
fdidks sksks
Jalal : AIUB SPARKS

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny » Tue Sep 27, 2005 12:41 am

thank u very much i got AC.

dontcry
New poster
Posts: 5
Joined: Sun Aug 06, 2006 9:55 pm

Post by dontcry » Sun Aug 13, 2006 2:49 pm

You are saving the words in the map in the wrong way. You should search by word in *babelfish*, not by word in english. It should work that way.
Try the input given. Regards.

moonstruck
New poster
Posts: 3
Joined: Thu Aug 24, 2006 9:20 am

10282

Post by moonstruck » Sun Aug 27, 2006 3:29 am

Hi

I already got accepted in 10282.
But I

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

Post by mf » Tue Aug 29, 2006 3:58 am

The way you use 'char *' with STL's map is wrong. char* is just a pointer to something in C/C++ (think, a 32-bit integer - memory address), it doesn't represent a string, or any other data by itself; and map<char*, char*> basically maps one pointer to another.
In your case, 'm' will map address of 's2' to the address of 's1', nothing more!

Use string class to represent strings.
I think may be my input taking approach is also not good enough as I'm handy with c, not c++.
It's good enough, if it works ;)
Besides, iostream is going to be several times slower than stdio...
Can anyone suggest me how to take input using only <iostream>?

Code: Select all

#include <iostream>
#include <sstream>
using namespace std;

int main() {
	for (;;) {
		string line;
		getline(cin, line);

		istringstream is(line);
		string s1, s2;
		if (!(is >> s1 >> s2)) break;

		// process pair of words s1 and s2
	}

	string s;
	while (cin >> s) { /* process word s */ }
}

chetan
New poster
Posts: 43
Joined: Sun Sep 24, 2006 2:39 pm

memory limit exceeded

Post by chetan » Sun Apr 15, 2007 3:13 pm

hi i am trying to solve the problem babelfish (10282) using STL map

i am gettin gmemory limit exceede.
plz help me out .

Code: Select all

# include <iostream>
# include <map>
# include <vector>
# include <algorithm>
# include <sstream>
# include <cstdio>
# include <string>

using namespace std;

int main()
{
    map<string,string> m;
    vector< map<string,string> > vm;
    string s1,s2;
    char arr[100];
    
    vm.clear();
    for(;;)
    {
        gets(arr);
           
        istringstream iss(arr);
        
        if(!(iss>>s1>>s2))
            break;
        m[s2]=s1;
        vm.push_back(m);
    }
    
  while( cin>>s1)
    cout<<m[s1]<<'\n';
    
    
return 0;
}

        
thanks

Kire Sopov
New poster
Posts: 7
Joined: Wed Sep 15, 2004 2:01 am

Post by Kire Sopov » Thu Apr 19, 2007 1:00 am

Why do you use that vector variable vm? :o


That's what probably causes the memory overflow.
And btw, you haven't handled the case where the word doesn't exist in the dictionary (you should output 'eh' in that case).

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris » Sun Apr 22, 2007 12:50 am

I agree. Your vm.push_back(m) in particular -- you're making a copy of the dictionary so far and pushing it into the vector...so at the end you end up with a vector with O(n^2) string pairs inside...

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
Location: (CSE,DU), Dhaka,Bangladesh

Post by ishtiaq ahmed » Fri Aug 10, 2007 8:32 am

deleted
Last edited by ishtiaq ahmed on Fri Aug 10, 2007 3:32 pm, edited 1 time in total.
No venture no gain

with best regards
------------------------
ishtiaq ahmed

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
Location: (CSE,DU), Dhaka,Bangladesh

TLE(Babelfish)

Post by ishtiaq ahmed » Fri Aug 10, 2007 8:33 am

i am facing TLE. I have used simple two dimensional string to solve it. Can anybody inform me how i can cirrect my program according to my algorithm. If there is no way then tell me what can i do?

Code: Select all

removed
Waiting for your reply
Last edited by ishtiaq ahmed on Fri Sep 14, 2007 8:16 pm, edited 1 time in total.
No venture no gain

with best regards
------------------------
ishtiaq ahmed

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Fri Aug 10, 2007 9:56 am

Linear Search is too slow for this problem.
Use a data structure that can search more fast.

----
Rio

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

Post by Riyad » Sun Aug 12, 2007 7:17 pm

two ways to do it
1) qsort then binary search
2) binary search tree is also an option
think about it ... you will get the idea
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
Location: (CSE,DU), Dhaka,Bangladesh

10282 Babelfish[compilation error]

Post by ishtiaq ahmed » Fri Sep 14, 2007 4:09 pm

Ok, i rewrite my code. Here i did two things
1. qsort
2. binary + lenear search
But it stands for compilation error.Here is my code

Code: Select all

 
removed
hope you will reply soon.
Last edited by ishtiaq ahmed on Fri Sep 14, 2007 8:21 pm, edited 1 time in total.
No venture no gain

with best regards
------------------------
ishtiaq ahmed

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

Post by mf » Fri Sep 14, 2007 4:30 pm

Here are g++ 3.4.4's error messages:

Code: Select all

p.cc:11: error: `int index' redeclared as different kind of symbol
/usr/include/string.h:56: error: previous declaration of `char* index(const char*, int)'
p.cc:11: error: declaration of `int index'
/usr/include/string.h:56: error: conflicts with previous declaration `char* index(const char*, int)'
p.cc: In function `void taking_input()':
p.cc:17: error: assignment of function `char* index(const char*, int)'
p.cc:17: error: cannot convert `int' to `char*()(const char*, int)' in assignment
p.cc:27: error: ISO C++ forbids incrementing a pointer of type `char*(*)(const char*, int)'
p.cc:27: error: non-lvalue in increment
p.cc:29: error: invalid types `info[1000000][char*()(const char*, int)]' for array subscript
p.cc: In function `int binary_search(char, char*)':
p.cc:74: error: invalid conversion from `char*(*)(const char*, int)' to `int'
p.cc:88: error: ISO C++ forbids comparison between pointer and integer
p.cc: In function `int main()':
p.cc:115: error: invalid conversion from `char*(*)(const char*, int)' to `int'
p.cc:115: error:   initializing argument 2 of `void quick_sort(int, int)'
It doesn't like your 'int index;' declaration, because there's a system function with that name.

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
Location: (CSE,DU), Dhaka,Bangladesh

post reply

Post by ishtiaq ahmed » Fri Sep 14, 2007 5:33 pm

Dear mf,
Thanks for replying . But one thing i cannot understand. I did many programs in which i used 'int index' variable , and those were accepted too. So why it conflicts with previous declaration `char* index(const char*, int)' . Its really hard to understand. What should i do now? Please inform me where the changes are to be required. I have used microsoft visual studio compiler and totally in dark of g++ compiler. Please help me.

Waiting for your reply
No venture no gain

with best regards
------------------------
ishtiaq ahmed

Post Reply

Return to “Volume 102 (10200-10299)”