When I used BFS,I found it would exceed the time limit.
Does DFS also will exceed the time limit?

Maybe that is what i am doing wrong.

If i have a set of words, say:

it
your
reality
real
our

Can the output be something like:

reality our reality

or the words can't be repeated??

Edited by author 24.02.2014 14:44

please send me the test data at least for test 1,
i have trouble understanding what is wrong with the code just going blindly,
after running all the tests i could find and succeeding still not able to pass first one.

tx

Cual es la entrada y salida del test 4?

I'm using streamTokenizer and the maximum input it can handle seems to be double ( coz of streamtokenizer.nval is double)... how to input large numbers of order 10exp9??

I am having problem in 1. Plz tell me that what should i do to solve this?

Could anyone give me the test#6?
godsuriyel@gmail.com
thanks!

Could anyone give me the test#6?
godsuriyel@gmail.com
thanks!

WA4, i still don't know why :)
please give me some cool inputs and (optionally) your answers to them.

i use BFS and can't pass test 8 because MLE

help me, please

Edited by author 30.10.2012 09:44

solve it with c++

algo are:
dp[i,j]=dp[i,k]&&dp[k+1,j]

main code are:
for(length=0;length<n;length++)
    {
        for(i=0;i+length<n;i++)
        {
            if(find(i,i+length,maintree))
            {
                dp[i][i+length][0]=9999;
                dp[i][i+length][1]=1;
                save[i][i+length]=choose;
            }
            else
            {
                bestadd=100;bestj=-1;
                for(j=i+1;j<i+length;j++)
                if(dp[i][j][0]!=-1&&dp[j+1][i+length][0]!=-1)
                {
                    if(dp[i][j][1]+dp[j+1][i+length][1]<=bestadd)
                    {
                        bestadd=dp[i][j][1]+dp[j+1][i+length][1];
                        bestj=j;
                    }
                }
                dp[i][i+length][0]=bestj;
                dp[i][i+length][1]=bestadd;
            }
        }
    }

hope it will do you a favor

Hi

I have the solution which seems to work fine when I tested with sample input. But I get "wrong answer" judgement.
Can any please look at see if I am making some obvious mistake.

Many Thanks
-------------------------------------------------


#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <sstream>
using namespace std;
string code[] = {"oqz","ij","abc","def","gh","kl","mn","prs","tuv","wxy"};
int getArrMax(int *arr, int size){
    int temp = 0;
    int val = 0;
    for(int i=0; i<size; i++){
        if(arr[i] > val){
        val = arr[i];
        temp = i;
        }
    }
    return temp;
}

string match(string line, size_t start, size_t max_word_size, size_t& lastmatch, string* dictionary, int dict_size)
{
    int* match = new int[dict_size];
    for(int count=0;count<dict_size;count++) match[count]=0;
    for(size_t i=start;i < (start+max_word_size);i++)
    {
        const char c = line.at(i);
        int digit = atoi(&c);
        string rel_code = code[digit];
        //find max val in match arry
        int MAX = match[getArrMax(match,dict_size)];
        for(int k=0;k<dict_size;k++){
            string dict_word = dictionary[k];
            if((match[k] == MAX)&& (dict_word.length()>(i-start))
                &&(rel_code.find(dict_word.at(i-start))!=string::npos)){
                match[k]+=1;
            }
        }
    }
    int match_index = getArrMax(match,dict_size);
    string match_string = dictionary[match_index];
    if(match[match_index] != match_string.length())
        match_string = "";
    lastmatch = start + match_string.length();
    delete match;
    return match_string;
}

int main(){
    vector<string> vec;
    string line;
    while(getline(cin,line) && line !="-1"){
        std::stringstream trimmer; trimmer << line; trimmer >> line;
        cin.clear(); fflush(stdin);
        int dict_size; cin >> dict_size;
        string* dict = new string[dict_size];
        size_t max_word_size = 0;
        for(int i=0;i<dict_size;i++)
        {
            cin.clear(); fflush(stdin);
            string dict_word;
            getline(cin,dict_word);
            std::stringstream trimmer; trimmer << dict_word; trimmer >> dict_word;
            dict[i] = dict_word;
            if( max_word_size < dict_word.length() ) max_word_size = dict_word.length();
        }
        size_t lastmatch = 0;
        while(lastmatch >= 0 && lastmatch < (line.length()-1)){
            size_t thismatch = lastmatch;
            string ss = match(line,lastmatch,
                max_word_size < (line.length()-lastmatch) ? max_word_size : (line.length()-lastmatch),
                lastmatch,dict,dict_size);
            if(thismatch==lastmatch)
                lastmatch = -1;
            else {
                vec.push_back(ss);
                if(lastmatch != line.length())
                    vec.push_back(" ");
            }
        }
        if(lastmatch == line.length())
            vec.push_back("\n");
        else
            vec.push_back("No solution.\n");
        delete[] dict;
    }
        copy(vec.begin(),vec.end(),ostream_iterator<string>(cout,""));
}

wondering, how can executing time = 0.001 sec be gained? or at least 0.015? Which struct dictionary should have?

As for me, I used lower_bound to find out needed word in dictionary (::vector) in my solution and got 0.041 sec time (memory usage is not so interesting)

Edited by author 11.03.2017 03:23

Edited by author 11.03.2017 03:24

In http://timustests.lx.ro/, the test solution 8 is "****** bargo ********" but the word "bargo" is not in the dictionary.

Could anyone post 1st test? My solution passes all tests I found here or come up with myself, but still get WA1.

Will there be nested words in the dictionary? Example: test and tests.

I got crass on test #5 for serval times.

finally I change the limit about given words (<= 100000),  digits length (<=200) and length of word (<=100).

then I got AC.

My program gives a wrong answer with test#9,but I don't know where the mistake is,please help me correct it
program ural1002;
var
  f,w:array[0..100,0..100]of longint;
  s:string;
  n:longint;
  ans:longint;
  c,cc:array[1..50000]of string[51];
  list:array['0'..'9',1..50,0..500]of longint;
const
  func:array['a'..'z']of char
  =('2','2','2','3','3','3','4','4','1','1','5','5',
    '6','6','0','7','0','7','7','8','8','8','9','9','9','0');
procedure init;
var
  i,j,k,l:longint;ss:string[51];
begin
  readln(s);
  if s='-1' then halt;
  readln(n);
  for i:=1 to n do
  begin
    readln(c[i]);
    cc[i]:=c[i];
  end;
  fillchar(list,sizeof(list),0);
  for i:=1 to n do
  begin
    ss:='';
    for j:=1 to length(c[i]) do ss:=ss+func[c[i,j]];
    c[i]:=ss;
    inc(list[c[i,1],length(c[i]),0]);
    list[c[i,1],length(c[i]),list[c[i,1],length(c[i]),0]]:=i;
  end;
  for i:=0 to length(s) do for j:=0 to length(s) do
  w[i,j]:=i;
  for i:=0 to length(s) do for j:=0 to length(s) do if i=j then
  f[i,j]:=0 else f[i,j]:=n+1;
  for i:=1 to length(s) do
  for j:=1 to 50 do
  for k:=1 to list[s[i],j,0] do
  if copy(s,i,j)=c[list[s[i],j,k]] then
  begin
    f[i-1,i+j-1]:=1;
    w[i-1,i+j-1]:=-list[s[i],j,k];
  end;
end;
function dp:longint;
var
  i,j,k:longint;
begin
  for k:=0 to length(s) do
  for i:=0 to k do
  for j:=k to length(s) do
  if f[i,k]+f[k,j]<f[i,j] then
  begin
    f[i,j]:=f[i,k]+f[k,j];
    w[i,j]:=k;
  end;
  dp:=f[0,length(s)];
end;
procedure print(l,r:longint);
begin
  if w[l,r]<0 then
  begin
    write(cc[-w[l,r]]);
    if r<length(s) then write(' ')else writeln;
    exit;
  end
  else
  begin
    print(l,w[l,r]);
    print(w[l,r],r);
  end;
end;
begin
  while true do
  begin
    init;
    ans:=dp;
    if ans<=n then
    print(0,length(s))
    else
    writeln('No solution.');
  end;
end.