10282 - Babelfish

[CodeMaker]

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

[sunny]

thank u very much i got AC.

[dontcry]

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]

Hi

I already got accepted in 10282.
But I

[mf]

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]

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]

Why do you use that vector variable vm?


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]

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]

deleted

[ishtiaq ahmed]

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

[rio]

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

----
Rio

[Riyad]

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

[ishtiaq ahmed]

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.

[mf]

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]

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