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

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone » Wed Nov 23, 2005 4:03 pm

some words are reduplicate at the begining
these part shouldn't be done twice

tree can help you to solve :P

Tamagodzi
New poster
Posts: 22
Joined: Thu Apr 28, 2005 10:56 pm

Post by Tamagodzi » Wed Nov 23, 2005 8:10 pm

Dont know whats wrong with input yet. But this simple input checker gets tle :-)

Code: Select all

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

string s;
char c;
int t,d,q,m,n,i,j;

int main()
{
    cin >> t;
    while(t--)
    {
        cin >> d;
        while(d--)
        {
            cin >> s;
        }
        cin >> q;
        while(q--)
        {
            cin >> m >> n;
            cin.get();
            while(m--)
            {
               getline(cin,s);
            }
        }
    }
    return 0;
}

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

Post by Moha » Thu Nov 24, 2005 11:55 am

Read Character by character instead of reading line by line. It works OK!

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Wed Nov 30, 2005 10:20 pm

Hello all!

I was getting strange WAs, and then decided to make some input checkers. In the next lines I expose these input checkers and what are the OJ's replies.

input_checker_1

Code: Select all

int main ()
{
    int T, D, Q, M, N, i, j, k;
    char s[2005];
    
    cin >> T;
    assert(T>=1 && T<=10);
    for (k=1; k<=T; k++)
    {
        cin >> D;
        assert(D>=1 && D<=15000);
        for (i=0; i<D; i++) cin >> s;
        cin >> Q;
        assert(Q>=1 && Q<=100);
        for (j=1; j<=Q; j++)
        {
            cin >> M >> N;
            assert(M>=1 && M<=100 && N>=1 && N<=100);
            for (i=0; i<M; i++) cin >> s;
        }
    }
    
    return 0;
}
The reply is WA in 0.002


input_checker_2

Code: Select all

int main ()
{
    int T, D, Q, M, N, i, j, k;
    char s[2005];
    
    cin >> T;
    assert(T>=1 && T<=10);
    while (T--)
    {
        cin >> D;
        assert(D>=1 && D<=15000);
        while (D--) cin >> s;
        cin >> Q;
        assert(Q>=1 && Q<=100);
        while (Q--)
        {
            cin >> M >> N;
            assert(M>=1 && M<=100 && N>=1 && N<=100);
            while (M--) cin >> s;
        }
    }
    
    return 0;
}
The reply is RE in 0.002


input_checker_3

Code: Select all

int main ()
{
    int T, D, Q, M, N, i, j, k;
    char s[2005];
    
    cin >> T;
    while (T--)
    {
        cin >> D;
        while (D--) cin >> s;
        cin >> Q;
        while (Q--)
        {
            cin >> M >> N;
            while (M--) cin >> s;
        }
    }
    
    return 0;
}
The reply is TLE

Well, Could anyone say me what is the reason?
And by other hand, what is correct manner to make a good parse input?

Thanks!
I'm waitting some interesting reply :D

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

Post by Moha » Wed Nov 30, 2005 10:31 pm

As is said before, For reading the input matrix for this problem, you should read it, character by character, so, instead of reading m line, read m*n character!

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Thu Dec 01, 2005 2:43 am

To Moha:
Ok! The matrix m*n chars? I think m*(n+1) with '\n', or do you refer to valid chars only(lower case)?
And how do you read the rest of the input?
for ints -> scanf, cin, char by char?
for the words -> scanf, cin, char by char?
The size of your matrix is 101x101?
Thanks a lot of, in advance!


I have got about 35 WAs, REs, TLEs.
I have tested a lot of different methods, char by char, line by line, cin, gets, getc, getchar.
Is something wrong in the input specification?
Is the file input corrupted?
What is the reason why the AC rate is so slow?
Why my previous input checker codes give different answers when they must give the same?

If someone want to post his/her entire parse input method, or someone want describe it detailedly I think will give a lot of joy :D

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Thu Dec 01, 2005 6:50 am

Here is my input code:

Code: Select all

char buf[100000], sq[128][128];

int main()
{
   int D, Q, M, N, T, t, k;
   
   for(scanf("%d", &T), t=1; t<=T; t++)
   {
      scanf("%d", &D);
      for(k=0; k<D; k++)
         scanf("%s", buf);
      
      scanf("%d", &Q);
      for(k=1; k<=Q; k++)
      {
         scanf("%d %d", &M, &N);
         for(i=0; i<M; scanf("%s", sq[i++]));
      }
      
   }
   
   return 0;
}
Emilio wrote:Is something wrong in the input specification?
Is the file input corrupted?
I don't think so. I don't get any problem for reading input.
Emilio wrote:What is the reason why the AC rate is so slow?
Maybe, it is because the problem looks quite easy. At least everyone should know how to solve it with a brute-force method. But then, submitting the trivial solution will surely result in TLE.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Thu Dec 01, 2005 6:08 pm

Thanks Cho!

But I don't know why doesn't work with cin.
Now I have got MLE, I used trie. Well, this is another task, now I can think about other stuffs in this problem. :D

Tamagodzi
New poster
Posts: 22
Joined: Thu Apr 28, 2005 10:56 pm

Post by Tamagodzi » Sat Dec 03, 2005 2:53 am

Try to read m and n with cin >> m >> n and surprisingly u will get wa.

Does anyone know whats the difference between cin and scanf("%d.. in reading integers?

There is definitly something wrong around some inputs for m and n which scanf can handle somehow and cin not.

Tamagodzi
New poster
Posts: 22
Joined: Thu Apr 28, 2005 10:56 pm

Post by Tamagodzi » Sat Dec 03, 2005 3:27 am

My Guess is some input like:

Code: Select all

3 3
aaa
bbb
ccc

aaa
bbb
ccc

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

Post by Moha » Sat Dec 03, 2005 11:44 pm

I read the entire input with cin, and had no problem.

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

Reading input wich cin

Post by Moha » Sun Dec 04, 2005 11:55 pm

This is my code for reading input:

Code: Select all

main()
{
	int tn,ct=0;
	string tmp;
	for (fin>>tn;tn--;)
	{
		for(fin>>t;t--; )
			fin>>tmp;
		int ttn;
		fin>>ttn;
		for (int tc=0;tc<ttn;tc++)
		{
			fin>>m>>n;
			for(int i=0;i<m;i++)
				for (int j=0;j<n;j++)
					fin>>table[i][j];
		}

	}
	return 0;
}

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sat Dec 10, 2005 8:25 pm

Tamagodzi wrote:Try to read m and n with cin >> m >> n and surprisingly u will get wa.

Does anyone know whats the difference between cin and scanf("%d.. in reading integers?

There is definitly something wrong around some inputs for m and n which scanf can handle somehow and cin not.
Afaik there is no difference (except that cin>> is much more slower). How do you use it? You probably have a bug in your code.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10975 TLE

Post by Martin Macko » Sat Dec 10, 2005 9:05 pm

Wei-Ming Chen wrote:My code got TLE in this question.
And my method was find the first word, and checked the eight side of it. I thought it was too slow to solve this question. Can someone give me some hints to solve it?
Search for Aho-Corasick algorithm. It's based on KMP algorithm, but searches many patterns in a string at once.

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

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

You can solve it, using a trie data structure to keep the words.
That's simpler to implement than Aho-Corasick.

Post Reply

Return to “Volume 109 (10900-10999)”