10679 - I Love Strings!!
Moderator: Board moderators
10679 - I Love String!! - Is rejudging possible?
Last year (when I was very new to UVa), I accidentally figure out the test cases of this problem and thus able to generate correct output even without reading the input. I really did so to see how high I can climb on the ranklist.
I now think what I did is a bit childish and like to remove the record. So, is it possible to append one more data set (random data is good enough) to the test cases and rejudge the solutions?
By the way, I believe those sub-1-second solution was doing similar thing as mine to achieve that result. (Please let me know if I am wrong.)
I now think what I did is a bit childish and like to remove the record. So, is it possible to append one more data set (random data is good enough) to the test cases and rejudge the solutions?
By the way, I believe those sub-1-second solution was doing similar thing as mine to achieve that result. (Please let me know if I am wrong.)
- little joey
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
Hi Cho,
Are you sure you are talking about this problem? I see you have a fast time, but a printf solution would have 0.000 seconds. And yes, my solution is <1 second and it is genuine, as are many other sub second solutions from respectable people.
Personally, I wouldn't bother too much if you've made the occasional misstep; there are enough people who do this systematically without remorse.
For this problem, I don't think it would be a good idea to add more cases: there are some people who just made the time limit, and they would be disadvantaged. You could ask the judges to reorder the testcases, but I don't think they would be very willing to do so.
But I see you have a time of 0.383 seconds. It is a bit of work, but why don't you try to write an even faster genuine solution? It should be possible and then you clean your sleeves.
Are you sure you are talking about this problem? I see you have a fast time, but a printf solution would have 0.000 seconds. And yes, my solution is <1 second and it is genuine, as are many other sub second solutions from respectable people.
Personally, I wouldn't bother too much if you've made the occasional misstep; there are enough people who do this systematically without remorse.
For this problem, I don't think it would be a good idea to add more cases: there are some people who just made the time limit, and they would be disadvantaged. You could ask the judges to reorder the testcases, but I don't think they would be very willing to do so.
But I see you have a time of 0.383 seconds. It is a bit of work, but why don't you try to write an even faster genuine solution? It should be possible and then you clean your sleeves.
I didn't keep the cheated solution so don't know exactly what I did. As I can remember, I scanf all the input, then printf the output y or n directly (I can determine the answer with a single if condition only) without any processing of the input strings. And this gave me .383 second.
That's why I think anyone with submission in similar running time cheated as well. I'm sorry about my judgement to those who really solved this problem with decent time.
I know suffix tree or suffix array are the state-of-the-art pattern matching algorithm with linear running time. But there is quite a lot of processing, I really cannot foresee I can implement any of them and solve this problem in less than one second.
That's why I think anyone with submission in similar running time cheated as well. I'm sorry about my judgement to those who really solved this problem with decent time.
I know suffix tree or suffix array are the state-of-the-art pattern matching algorithm with linear running time. But there is quite a lot of processing, I really cannot foresee I can implement any of them and solve this problem in less than one second.
I've just submitted the following WA code and it took 0.428 to finish. That's why it's too hard for me to imagine there are genuine solutions to solve it at similar or even faster speed.
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char text[102400], query[1024];
void main()
{
int t, n;
for(scanf("%d", &t); t--; )
{
scanf("%s", text);
for(scanf("%d", &n); n--; )
{
scanf("%s", query);
printf("%c\n", 'y');
}
}
}
- little joey
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
You can improve much on your reading part. The following gives WA in 0.086 seconds:
I admit that this code is not very fail-safe, but it worked for me on this problem.
The reason that scanf is so slow for big input is that most compilers don't actually compile code for it, but include a little interpreter that processes the format string and input at runtime.
But it will be a great task to get the rest of the code under 0.3 seconds
Code: Select all
#include <stdio.h>
char string[128*1024];
char query[1024];
int main(){
int cases;
int queries;
scanf("%d\n",&cases);
while(cases--){
fgets(string,sizeof(string),stdin);
/* ... */
scanf("%d\n",&queries);
while(queries--){
fgets(query,sizeof(query),stdin);
/* ... */
}
}
return 0;
}
The reason that scanf is so slow for big input is that most compilers don't actually compile code for it, but include a little interpreter that processes the format string and input at runtime.
But it will be a great task to get the rest of the code under 0.3 seconds

Run Time Error
I am having runtime error using strstr function . Can any one tell me Why?
10679 - I Love String (STL) Why TLE?
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
using namespace std;
int n, j, find, i, k;
int main()
{
scanf("%d",&n);
for(j=0;j<n;j++)
{
string s;
cin >> s;
string::size_type idx;
cin >> find;
for(i=0;i<find;i++)
{
k=0; string strFind;
cin >> strFind;
idx=s.find(strFind);
if(idx!=string::npos)
{
string subs = s.substr(idx, strFind.size());
cout << "y" << endl; k=1;
}
idx=s.find(strFind, idx + strFind.size());
if(idx!=string::npos)
{
string subs = s.substr(idx, strFind.size());
cout << "y" << endl; k=1;
}
if(k==0)
cout << "n" << endl;
}
}
return 0;
}
Why TLE?

I used STL.....
#include <cstring>
#include <cstdio>
#include <string>
using namespace std;
int n, j, find, i, k;
int main()
{
scanf("%d",&n);
for(j=0;j<n;j++)
{
string s;
cin >> s;
string::size_type idx;
cin >> find;
for(i=0;i<find;i++)
{
k=0; string strFind;
cin >> strFind;
idx=s.find(strFind);
if(idx!=string::npos)
{
string subs = s.substr(idx, strFind.size());
cout << "y" << endl; k=1;
}
idx=s.find(strFind, idx + strFind.size());
if(idx!=string::npos)
{
string subs = s.substr(idx, strFind.size());
cout << "y" << endl; k=1;
}
if(k==0)
cout << "n" << endl;
}
}
return 0;
}
Why TLE?



I used STL.....
Last edited by Psyco on Fri Feb 03, 2006 1:47 pm, edited 1 time in total.
Thanks
Thanks......
But I can't using KMP...
I am serching many question, But they are all says "Using KMP"
Need I using KMP?
Please.... Hint....
타임 리미트...I want to Accpted
But I can't using KMP...
I am serching many question, But they are all says "Using KMP"
Need I using KMP?
Please.... Hint....
타임 리미트...I want to Accpted
- tmdrbs6584
- Learning poster
- Posts: 98
- Joined: Sat Jan 21, 2006 12:45 pm
- Location: Busan,Corea(Republic of)
RE:물음
You are Hooked up!!!
Archaan
CAN YOU BEAT ME?
http://acm.uva.es/problemset/usersjudge.php?user=19788
AND,
http://acm.uva.es/problemset/submit.php
http://online-judge.uva.es/problemset/submit.php
SUBMIT AND GET AC!!!
CAN YOU BEAT ME?
http://acm.uva.es/problemset/usersjudge.php?user=19788
AND,
http://acm.uva.es/problemset/submit.php
http://online-judge.uva.es/problemset/submit.php
SUBMIT AND GET AC!!!
10679 - I Love String ( STL ) Why TLE???
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
using namespace std;
int n, j, find, i, k;
int main()
{
scanf("%d",&n);
for(j=0;j<n;j++)
{
string s;
cin >> s;
string::size_type idx;
cin >> find;
for(i=0;i<find;i++)
{
k=0; string strFind;
cin >> strFind;
idx=s.find(strFind);
if(idx!=string::npos)
{
string subs = s.substr(idx, strFind.size());
cout << "y" << endl; k=1;
}
idx=s.find(strFind, idx + strFind.size());
if(idx!=string::npos)
{
string subs = s.substr(idx, strFind.size());
cout << "y" << endl; k=1;
}
if(k==0)
cout << "n" << endl;
}
}
return 0;
}
Why TLE?
I used STL.....
#include <cstring>
#include <cstdio>
#include <string>
using namespace std;
int n, j, find, i, k;
int main()
{
scanf("%d",&n);
for(j=0;j<n;j++)
{
string s;
cin >> s;
string::size_type idx;
cin >> find;
for(i=0;i<find;i++)
{
k=0; string strFind;
cin >> strFind;
idx=s.find(strFind);
if(idx!=string::npos)
{
string subs = s.substr(idx, strFind.size());
cout << "y" << endl; k=1;
}
idx=s.find(strFind, idx + strFind.size());
if(idx!=string::npos)
{
string subs = s.substr(idx, strFind.size());
cout << "y" << endl; k=1;
}
if(k==0)
cout << "n" << endl;
}
}
return 0;
}
Why TLE?
I used STL.....
AFAIK, STL string's find() is implemented with O(nm) algorithm (n,m=length of strings.)Psyco wrote:Why TLE?
I used STL.....
It would be a too trivial problem, if such algorithms were allowed to pass!
You can also use suffix trees/arrays or Aho-Corasick to get accepted.Need I using KMP?
P.S. Please, don't create several identical threads!