Moderator: Board moderators

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan
sakhassan wrote:still no clue!!!!!!!!!! still RTE

ok , your "char hash[M][N]; " , if we increase the size of N to
1000000 , what will happen ??

think about it , maybe you shoud find a better solution !
studying @ ntu csie

xlspace
New poster
Posts: 2
Joined: Sat Dec 23, 2006 3:38 pm

### I get TLE

Code: Select all

``````#include <string>
#include <map>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;

#define TSIZE 13881
typedef vector<map<string ,int> > HashTable;

void hash(string & sub, int & key1)
{
key1 = 0;
int i;
int t = 1;
int len = min<int>(5,sub.size());
t = 1;
for(i=0;i<len;i++)
{
t = (i<<1);
key1 += (((int)(sub[i])-97))<<t;

}
key1 = key1%TSIZE;
}

int insert(HashTable & HT, string & sub)
{
int key1;
hash(sub,key1);
map<string ,int>::iterator pos;
pos = HT[key1].find(sub);
if(pos == HT[key1].end())
{
HT[key1][sub] = 1;
return 1;
}
else
{
pos->second++;
return pos->second;
}
}

string search(int N, string & S)
{
int i,k;
string sub;
int T = 0;
int t;
string ret;
HashTable HT = HashTable(TSIZE+1);
sub = S.substr(0,N);
k = 0;
for(i=1;i<S.length()-N+1;i++)
{
sub.erase(sub.begin());
sub.append(1,S[i+N-1]);
t = insert(HT,sub);
if(T < t)
{
T = t;
k = i;
}
}
ret = S.substr(k,N);
return ret;
}
int main()
{
int N;
string buffer;
while(cin>>N>>buffer)
{
cout<<search(N,buffer)<<endl;
}
}``````
I use hashtable, but can also not solve, get TLE

can anyone help me

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
The best cpu time of this problem is near 1sec, so I think it will be hard to avoid TLE using STL.

xlspace
New poster
Posts: 2
Joined: Sat Dec 23, 2006 3:38 pm

### get AC

I get AC now,
first I not use substr function in string
second , I use pair<unsigned int, unsigned int> to represent a string

Thanks

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

### Re: get AC

rio wrote:The best cpu time of this problem is near 1sec, so I think it will be hard to avoid TLE using STL.
I modified xlspace's code and got AC in 3.787 sec. It's possible to get AC using STL.
xlspace wrote:I get AC now,
first I not use substr function in string
second , I use pair<unsigned int, unsigned int> to represent a string.
Actually, you can use 'long long' to represent a string instead. That makes things simplier.

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

### Re: get AC

DJWS wrote:Actually, you can use 'long long' to represent a string instead. That makes things simplier.
Cool idea I'll try it.

MaVa
New poster
Posts: 6
Joined: Wed Oct 25, 2006 6:01 pm

Don't give up, it is possible to solve this problem in Java!
Darko wrote:This is what I do (n - number given (<=10), slen - length of the string):
- read string into an array (O(n))
- sort pointers to substrings (O(n*slen*log(slen)) <- bad?
- go through list of pointers and find the longest repeating sequence (O(n*slen))
Maybe your runningtime is too slow?
Representing the substrings as longs will help, then a comparison of two substrings is 1 operation, not n.
My solution uses almost 3sec, if I were to multiply by n, I would get TLE.
O() notation is nice, but remember that the constant term is very important:
O(n*slen) might be larger than O(slen*log(slen)) in practice.

zwshen
New poster
Posts: 1
Joined: Mon Apr 16, 2007 7:46 pm

### serveral times of WA

I had improved my code to overcome the Time Limit Exceeded.
The improvement approaches are using "constant-time sub-string" and
"Customized Hash function instead STL map". The code can be judged
in 2 sec. However, I meet several times of WA.

I thought that the possible reason is the collision of Hash function.
Because I applied the joaat_hash approach and a prime number 99991 as the maximum size of hash table, is the prime number not as large as enough?

Thanks you and have a nice day.

Juan Gomez
New poster
Posts: 1
Joined: Tue Jun 19, 2007 6:20 pm
I have implemented a TRIE to store the possible passwords and it runs on 3.754 secs. It's no too fast but I think the source of the problem is in the way I'm reading the input. Have a nice day.

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Contact:
I used hashing.. I tried TRIES, they would have been fast if I had been able to use fixed links and not get MLE.

Anyway tho, hashing is fast enough.. and if you get the right hashing function (i.e. one of the more sensible obvious ones), you can avoid key errors while using unsigned int's. Also... If you assume something very dangerous about the nature of the most likely randomly generated larger test case, you can half your time.

gaucho.andre
New poster
Posts: 3
Joined: Fri Aug 31, 2007 8:33 am
That' my code. The algorythim seems ok and it works fine on eclipse, but i still get Compile Error message. Does anybody have a clue about waht's wrong on this program? P.S. JAVA program:

Code: Select all

``````import java.io.IOException;
import java.util.StringTokenizer;

class Problem902 {

static StringTokenizer st;
static short N, m, max;

public static void main(String[]args){

while(true){
input();
if(testCase == null)break;
input(testCase);
setArrays();

for(short i = 0; i <= (code.length-N); i++){

}
System.out.println(findPass());

}

}

//Method to read from input, copied from problem100 sample solution
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;

try
{
while (lg < maxLg)
{
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}

//Method to read a line from the input
static void input(){
}

//Method to convert the line read from the other method into a number (N) and a string(codeLine)
static void input(String linha){

st = new StringTokenizer(linha);
N = Short.parseShort(st.nextToken());
codeLine = st.nextToken();

}

//Method to convert codeLine into a char Array and to create 3 other arrays
static void setArrays(){

code = codeLine.toCharArray();
}

//Method to get 3 chars in a row and convert to a String
static String getPass(short i){

for(short j = 0; j < N; j++, i++) passwordVet[j] = code[i];
return pass;

}

//Method to use a String and check if i has already been read
static void checkPass(String pass){

for(m = 0; m < allPasswords.length; m++){
break;
}

break;
}
}
}

static String findPass(){
max = 0;
for(short i = 0; i < numPasswords.length; i++){
}
for(short i = 0; i < numPasswords.length; i++){
}
return "";

}

//Method to compare 2 Strings. P.S. Don't know why, but using "if(a == b)" didn't work
static boolean saoIguais(String a, String b){
char[] aa = a.toCharArray();
char[] bb = b.toCharArray();

for(short i = 0; i < aa.length; i++){
if(aa[i] != bb[i])return false;
}
return true;

}
}
``````

Code: Select all

``````Here are the compiler error messages:

05882640_24.java: In class `Main':
05882640_24.java: In method `main(java.lang.String[])':
05882640_24.java:21: Internal compiler error in `expand_expr', at expr.c:5844
``````
So, does anybody can see which is the compile error on this code?

kenneth
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am
Hi Guys, I got my solution accepted with run time of 2.830 seconds so it's not extremely fast but it's not bad.

I can see that there are lots of ideas came up in the discussion but I solved this problem just by brute force using substring function and a map (I coded in C++).

Say for string "baababacb", you can use a map to count the number of occurance of each substring

baa 1
aab 1
aba 2
bab 1
bac 1
acb 1

After that, just find the max number of occurance which is 2 and the answer is aba. There is no special case, that is you will never have more than 1 substrings that could be the answer.

The complexity of the algorithm is O(n) as you only need to go thru the string once followed by going thru the map once. Hope this helps.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
kenneth wrote:The complexity of the algorithm is O(n) as you only need to go thru the string once followed by going thru the map once. Hope this helps.
but access map and insertion in map will cost O(logn), Sor your algorithm is not O(n) it is O(nlogn).

kenneth
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am
emotional blind wrote:
kenneth wrote:The complexity of the algorithm is O(n) as you only need to go thru the string once followed by going thru the map once. Hope this helps.
but access map and insertion in map will cost O(logn), Sor your algorithm is not O(n) it is O(nlogn).
Thanks for pointing that out. But the STL has optimised that so it is much more efficient than you trying to build a binary tree yourself

Like I said it's not super fast but enough to run within 10 seconds.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am