10975 - Dueue's Quiz

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Sun Dec 11, 2005 10:10 pm

mf wrote:You can solve it, using a trie data structure to keep the words.
That's simpler to implement than Aho-Corasick.
In the Aho-Corasick implementation I know you build a trie from the words you search and then construct a set of "failure links". How does this differ from the solution you propose?

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

Post by mf » Sun Dec 11, 2005 11:05 pm

In my solution I only need the trie itself. I don't have to compute failure links.
For each starting cell and for each of the eight possible directions, I traverse the trie from the root, spelling out the corresponding string of letters. If some visited vertex represent the last character of a word, I increment the counter for that word.
My solution runs in O(n^3) time per query (where n=max(N,M)).

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Sun Dec 11, 2005 11:32 pm

mf wrote:In my solution I only need the trie itself. I don't have to compute failure links.
For each starting cell and for each of the eight possible directions, I traverse the trie from the root, spelling out the corresponding string of letters. If some visited vertex represent the last character of a word, I increment the counter for that word.
My solution runs in O(n^3) time per query (where n=max(N,M)).
Ah, OK, I thought that you meant a simpler way to achieve a time complexity comparable to Aho-Corasick :)

kalinov
New poster
Posts: 27
Joined: Tue Mar 29, 2005 3:10 pm
Location: Croatia

Wrong input

Post by kalinov » Sun Dec 18, 2005 3:04 pm

I believe the input file is wrong. I think there are some lines shorter than N characters.
I've tested it with this code:

Code: Select all

#include <cassert>
#include <cstdio>
#include <cstring>

using namespace std;

int main( void ) {
   int T, D, Q, M, N;
   char buff[10000];
   scanf( "%d", &T );
   
   for( int tt = 0; tt < T; ++tt ) {
      
      scanf( "%d", &D );
      for( int dd = 0; dd < D; ++dd ) 
         scanf( "%s", buff );

      scanf( "%d", &Q );
      for( int qq = 0; qq < Q; ++qq ) {
         scanf( "%d%d", &M, &N );
         for( int mm = 0; mm < M; ++mm ) {
            scanf( "%s", buff );
            assert( strlen( buff ) == N );
         }
      }
   }
   return 0;
}

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sat Sep 08, 2007 5:27 am

well i had lots of trouble witht he input system. so those who will try this problem for them:

(here: W is string, board[][] is char and others are int)

Code: Select all

	cin>>cases;
	for(ks=1;ks<=cases;ks++)
	{
		cin>>d;
		
		for(i=1;i<=d;i++)
		{
			cin>>W;
			if(W.size()<=100) //<---- this is important. without it u will get RTE. i dont know why!
                                    {
                                    }
		}

		cin>>Q;
		for(q=1;q<=Q;q++)
		{
			cin>>R>>C;
			for(i=0;i<R;i++)
				for(j=0;j<C;j++)
					cin>>board[i][j];
		}
	}
}
Self judging is the best judging!

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Wed Sep 12, 2007 11:08 pm

The inputs are correct. Also your point is correct, because you should throw away the words bigger than 100! You should deduce it from the problem description.

viniciusweb
New poster
Posts: 24
Joined: Sun Nov 12, 2006 3:38 pm

Re: 10975 - Dueue's Quiz

Post by viniciusweb » Mon Nov 03, 2008 3:50 am

WA here... What's the correct output for this case: http://paste-it.net/raw/public/n9a7fba/
(i'm linking it because it's too big to post)

Thanks.

chylek
New poster
Posts: 7
Joined: Fri Mar 22, 2013 7:50 pm
Location: Poland

Re: 10975 - Dueue's Quiz

Post by chylek » Wed Apr 02, 2014 1:38 pm

Can anyone tell me why do I get TLE? On the big input from this topic my program runs faster than accepted one (times: 0.9s and 1.1s).

Code: Select all

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <set>
#include <queue>

using namespace std;

int counter[15000];
string dict[15000];

struct letter
{
    letter *fail,*next[27];
    set<int> s;
};

void free (letter *_l)
{
    for(int i=0; i<26; i++)
        if(_l->next[i]!=NULL )
            free(_l->next[i]);
    delete[]_l;
}

int main()
{
    int tests,d,queries,m,n;
    char str[1001];
    string s,words[100],w;
    letter l,*tmp,*x;
    set<int> in;
    queue<letter*> q;
    s.reserve(100);
    for(int i=0; i<15000; i++)
        dict[i].reserve(1000);
    for(int i=0; i<100; i++)
        words[i].reserve(100);
    w.reserve(400000);
    scanf("%d",&tests);
    for(int t=1; t<=tests; t++)
    {
        l.fail=NULL;
        for(int i=0; i<26; i++)
            l.next[i]=NULL;
        l.next[26]=&l;
        l.s.clear();
        printf("Test Case #%d\n",t);
        scanf("%d",&d);
        getchar();
        for(int i=0; i<d; i++)
        {
            fgets(str,sizeof(str),stdin);
            str[strlen(str)-1]=0;
            if(strlen(str)<101)
            {
                dict[i]=string(str);
                counter[i]=0;
            }
            else
            {
                d--;
                i--;
            }
        }

        // tworzenie drzewa Trie
        for(int i=0; i<d; i++)
        {
            tmp=&l;
            for(unsigned int j=0; j<dict[i].size(); j++)
            {
                if(tmp->next[dict[i][j]-97]==NULL)
                {
                    tmp->next[dict[i][j]-97]=new letter[1];
                    tmp=tmp->next[dict[i][j]-97];
                    for(int j=0; j<26; j++)
                        tmp->next[j]=NULL;
                    tmp->next[26]=&l;
                }
                else
                    tmp=tmp->next[dict[i][j]-97];
            }
            tmp->s.insert(i);
        }

        // uzupelnianie fail przejsc (skroty na drzewie)
        for(int i=0; i<26; i++)
            if(l.next[i]!=NULL)
            {
                l.next[i]->fail=&l;
                q.push(l.next[i]);
            }
            else
                l.next[i]=&l;
        while(!q.empty())
        {
            tmp=q.front();
            q.pop();
            for(int i=0; i<26; i++)
                if(tmp->next[i]!=NULL)
                {
                    q.push(tmp->next[i]);
                    x=tmp->fail;
                    while(x->next[i]==NULL)
                        x=x->fail;
                    x=x->next[i];
                    tmp->next[i]->fail=x;
                    tmp->s.insert(x->s.begin(),x->s.end());
                }
        }

        scanf("%d",&queries);
        for(int c_queries=1; c_queries<=queries; c_queries++)
        {
            printf("Query #%d\n",c_queries);
            w="";
            scanf("%d %d",&m,&n);
            getchar();

            // konwersja tabeli na 1 dlugi napis
            for(int i=0; i<m; i++)      // wczytywanie + poziomo
            {
                fgets(str,sizeof(str),stdin);
                str[strlen(str)-1]=0;
                words[i]=string(str);
                w+=words[i]+'{';
            }
            for(int i=0; i<n; i++)      // pionowo
            {
                s="";
                for(int j=0; j<m; j++)
                    s+=words[j][i];
                w+=s+'{';
            }
            for(int i=m-1; i>0; i--)    // na ukos \ (w pionie)
            {
                s="";
                for(int j=0; i+j<m && j<n; j++)
                    s+=words[i+j][j];
                w+=s+'{';
            }
            for(int i=0; i<n; i++)      // na ukos \ (w poziomie)
            {
                s="";
                for(int j=0; i+j<n && j<m; j++)
                    s+=words[j][i+j];
                w+=s+'{';
            }
            for(int i=m-1; i>0; i--)    // na ukos / (w pionie)
            {
                s="";
                for(int j=0; i+j<m && j<n; j++)
                    s+=words[i+j][n-1-j];
                w+=s+'{';
            }
            for(int i=n-1; i>=0; i--)   // na ukos / (w poziomie)
            {
                s="";
                for(int j=0; i-j>=0 && j<m; j++)
                    s+=words[j][i-j];
                w+=s+'{';
            }

            // wyszkiwanie wzorcow
            tmp=&l;
            for(unsigned int i=0; i<w.size(); i++)
            {
                n=w[i]-97;
                while(tmp->next[n]==NULL)
                    tmp=tmp->fail;
                tmp=tmp->next[n];
                for(set<int>::iterator it=tmp->s.begin(); it!=tmp->s.end(); it++)
                {
                    counter[*it]++;
                    in.insert(*it);
                }
            }
            tmp=&l;
            for(int i=w.size()-1; i>=0; i--)
            {
                n=w[i]-97;
                while(tmp->next[n]==NULL)
                    tmp=tmp->fail;
                tmp=tmp->next[n];
                for(set<int>::iterator it=tmp->s.begin(); it!=tmp->s.end(); it++)
                {
                    counter[*it]++;
                    in.insert(*it);
                }
            }
            for(set<int>::iterator it=in.begin(); it!=in.end(); it++)
                //printf("%s %d\n",dict[*it].c_str(),counter[*it]);
                cout<<dict[*it]<<' '<<counter[*it]<<endl;
            in.clear();
        }
        for(int i=0; i<26; i++)
            if(l.next[i]!=NULL)
            {
                if(l.next[i]!=&l)
                    free(l.next[i]);
                l.next[i]=NULL;
            }
        printf("\n");
    }
}
thanks in advance ;)

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10975 - Dueue's Quiz

Post by brianfry713 » Fri Apr 04, 2014 12:00 am

What is the O() runtime for your code? Describe your algorithm.

printf is faster than cout. C style char[] are faster than C++ strings.
Check input and AC output for thousands of problems on uDebug!

chylek
New poster
Posts: 7
Joined: Fri Mar 22, 2013 7:50 pm
Location: Poland

Re: 10975 - Dueue's Quiz

Post by chylek » Fri Apr 04, 2014 5:09 pm

I don't know the O() runtime, but I'm using Aho-Corasick for serching words which should have linear complexity and reserving memory for strings (so concatenations are done without any reallocation).
I have second code with char[] and printf instead of string and cout but it gets about 15s on my computer for this big input (and also gets TLE on UVa). What's about the cout - I'm using it in only one place to print strings (on my computer string::c_str() and printf gets more time than cout).

Algorithm:
-read dictionary
-create Trie and fail connections on it (algorithms from web)
-read the query
-tranform the table of words into one big string, with '{' as marker which is the next character after 'z' in ASCII (preallocated memory -no reallocations)
-search words in both directions on the big string using Aho-Corasick (algorithm from web)
-output the answer.

The accepted code which I have (it's not mine) works in the same way but:
-reading words in every direction instead of creating this big string
-works on char[] (but containers are with string)
-uses map (!)

My IT teacher also doesn't know what's wrong with my code :D

Post Reply

Return to “Volume 109 (10900-10999)”