## 11991 - Easy Problem from Rujia Liu?

Moderator: Board moderators

iriz7482
New poster
Posts: 15
Joined: Mon Apr 04, 2011 3:18 pm

### 11991 - Easy Problem from Rujia Liu?

hello everyone, sorry for creating this thread if you think it's useless
I had got TLE in this problems many times and after 6 tries I got AC in 0.104 sec using my struct . But I found some guys got AC in about 0.08 or even 0.03 ~ 0.05 . I tried coding like this and send to judge to find out how long it takes to input/output, it was about 0.080 . So I'm confused how they got AC under 0.08 , is there any way to get fast I/O?

Code: Select all

``````#include<stdio.h>

main()
{
int m, n, a, k, v, i;
while(scanf("%d %d",&m,&n)==2)
{
for(i=0; i<m; i++)
{
scanf("%d",&a);
}
while(n-- > 0)
{
scanf("%d %d",&k,&v);
printf("0\n");
}
}
}
``````

rujialiu
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 am

### Re: 11991 - Easy Problem from Rujia Liu?

Does the following code make sense to you?

Code: Select all

``````inline int readint() {
char c = getchar();
while(!isdigit(c)) c = getchar();

int x = 0;
while(isdigit(c)) {
x = x * 10 + c - '0';
c = getchar();
}
return x;
}
``````
BTW: You don't need this kind of tricks to get AC for any problem in this problemset. In most cases I/O is not the bottleneck.

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

### Re: 11991 - Easy Problem from Rujia Liu?

@ rujialiu

I try to solved this problem this way:

i take 3 parallel array
1=> For frequency of each number
2=>For last position of given numbers
3=>For parent of each index of given numbers.

Now when i take a query only i take the last position of this number and from last to climbing first position and check the frequency.

This algorithm Give TLE.
Please explain me why it give TLE.
sorry my poor English.

iriz7482
New poster
Posts: 15
Joined: Mon Apr 04, 2011 3:18 pm

### Re: 11991 - Easy Problem from Rujia Liu?

@ Rujialiu
I found that using fread/fwrite can get I/O much faster but I don't know how to use them
BTW, this is a nice problem. I think it can't be solve without using suitable data structure

rujialiu
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 am

### Re: 11991 - Easy Problem from Rujia Liu?

@MRH

if i understand your algorithm correctly, if all the numbers are equal, each query would be linear on average, so TLE

shaon_cse_cu08
New poster
Posts: 50
Joined: Tue May 25, 2010 9:10 am
Contact:

### Re: 11991 - Easy Problem from Rujia Liu?

Hai.. I have tried it with a structure...1st i store every data with there position in the input....aftef dat i sorted them to apply Binary search... dan from the 1st occurance i jumped to k-th occurance...If the number equals to 'v' dan i hv printed the actual location... I can't find any critical input for which my code fails....please provide me some critical input....This is my WA code....

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

struct fnd
{
long num;
long ind;
};

bool comp(fnd a,fnd b)
{
return a.num<b.num;
}
int b_src(fnd a[],long n,long x);

int main()
{
struct fnd a[100001];

long n,m,k,v,i,j,loc,count;

while(scanf("%ld %ld",&n,&m)!=EOF)
{
for(i=1;i<=n;i++)
{
scanf("%ld",&a[i].num);
a[i].ind=i;
}

sort(a,a+n+1,comp);

for(j=0;j<m;j++)
{
scanf("%ld %ld",&k,&v);

loc=count=0;

loc=b_src(a,n,v);

for(i=loc;i>0;i--)
{
if(a[i].num!=v)
{
loc=i+k;
break;
}
}

if(i==0)
loc=k;

if(a[loc].num==v)
printf("%ld\n",a[loc].ind);
else
printf("0\n");
}
}
return 0;
}

int b_src(fnd a[],long n,long x)
{
int ini,end,mid;

ini=1;
end=n;

while(ini<=end)
{
mid=(ini+end)/2;

if(x==a[mid].num)
return (mid);

else if(x>a[mid].num)
ini=mid+1;

else
end=mid-1;
}

return 0;
}
``````
I'll keep holding on...Until the walls come tumbling down...And freedom is all around .....

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Contact:

### Re: 11991 - Easy Problem from Rujia Liu?

Here is my code:

Code: Select all

``````#include <cstdio>
#include <cmath>

int main()
{
unsigned long n,m, in[1000000];
while(scanf("%lu %lu",&n,&m)==2)
{
for(unsigned long i=0 ; i<n ; i++)
scanf("%lu",&in[i]);
unsigned long k,v, fag,times;
for(unsigned long i=0 ; i<m ; i++)
{
fag=0, times=0;
scanf("%lu %lu",&k,&v);
for(unsigned long j=0 ; j<n ; j++)
{
if(v==in[j])
{
times++;
}
if(times==k)
{
printf("%lu\n",j+1);
fag=1;
break;
}
}
if(fag==0)
printf("0\n");
}
}
return 0;
}

``````

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

### Re: 11991 - Easy Problem from Rujia Liu?

You need to precompute the answer for all possible queries.
Check input and AC output for thousands of problems on uDebug!

atiburrahman09
New poster
Posts: 6
Joined: Mon Mar 26, 2012 10:12 pm

### 11991

I need some Help....
i am trying to solve this problem. but i cann't understand this line.

"For each query, print the 1-based location of the occurrence. If there is no such element, output 0 instead."

Any help will be great....

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

### Re: 11991

Sample Input

Code: Select all

``````8 4
1 3 2 2 4 3 2 1
1 3
2 4
3 2
4 2``````
Sample Output

Code: Select all

``````2
0
7
0``````
The array has 8 elements, position 1 through 8. First you are looking for the first 3, that is at position 2 in the array. Next you want the second 4, but since there is only one 4 print 0 instead. Next the third 2, which is at position 7. Finally the fourth 2, but there are only three 2's, so print 0 instead.
Check input and AC output for thousands of problems on uDebug!

esharif
New poster
Posts: 18
Joined: Sun Jun 03, 2012 11:56 pm

### How can I improve time limit for 11991, help plzzzzz

I can't continue without WA or TL, I'm verily in downgrade.
but I wanna solve problems, help me to this approach. Firstly see the code below:

Code: Select all

``````#include<stdio.h>

int main()
{
long int i, j, s, count, n, m, k, v, a[100001];
while(scanf("%ld%ld",&n, &m)==2)
{
for(i=1; i<=n; i++)
{
scanf("%ld", &a[i]);
}
for(j=1; j<=m; j++)
{
count=0, s=0;
scanf("%ld%ld", &k, &v);
for(i=0; i<=n; i++)
{
if(a[i]==v)
count++;
if(count==k)
{
s=i;
break;
}
}
printf("%ld\n", s);
}
}
return 0;
}
``````

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

### Re: How can I improve time limit for 11991, help plzzzzz

You need to precompute the answer for all possible queries.
Check input and AC output for thousands of problems on uDebug!

wonderful008
New poster
Posts: 2
Joined: Thu Jul 26, 2012 4:26 pm

### 11991 run time error

I used C with linked list to solve this problem.
But there is still some run time errors...
I could not find out them, help, please...

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#define MAX 255
typedef struct list_node *list_ptr;
struct list_node {
int data;
};

list_ptr create(int data);

int main()
{
int len, num, data, temp, i = 0;
int value, times, none;
scanf("%d %d", &len, &num);
list_ptr node[MAX];
temp = len;

while (temp--) {
none = scanf("%d", &data);
node[i++] = create(data);
}

while (num--) {
int count = 0;
scanf("%d %d", &times, &value);
for (i = 0; i < len; i++) {
if (node[i]->data == value)
count++;
}
int count2 = 0;
if (count >= times) {
for (i = 0; i < len; i++) {
if (node[i]->data == value)
count2++;
if (count2 == times) {
printf("%d\n", i+1);
break;
}
}
}
else
printf("0\n");
}

return 0;
}

list_ptr create(int data)
{
list_ptr node;
node = (list_ptr)malloc(sizeof(16));
node->data = data;

return node;
}

``````

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

### Re: 11991 run time error

Try the gift I/O files for problem E at http://uva.onlinejudge.org/contests/278 ... _files.zip
Check input and AC output for thousands of problems on uDebug!

zlshang
New poster
Posts: 4
Joined: Wed Jan 02, 2013 8:51 pm

### Re: 11991 - Easy Problem from Rujia Liu?

Hello everyone This problem I want to solve with binary search. But in the end ,I found I was fault .Every samples I can thought is OK in this code ,but I continuely got WA.I can't find any criticle input for which my codes fails....please provide me some criticle input...PLZZZZZZZ....

Code: Select all

``````#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <cmath>
using namespace std;
int n,m,a[1000001],b[1000001],c[1000000],k,v;
bool  cmp(int x,int y)
{
return a[x]<a[y];
}

int find( )
{
int left=0,right=n-1,mid;
while(left<right)
{
mid=(left+right)/2;
if(a[b[c[mid]]]<v) left=mid+1;
else right=mid;
}
return left;
}
int main()
{
while(scanf("%d%d",&n,&m)==2)
{
memset(a,1,sizeof(a));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=c[i]=i;
}
sort(b+1,b+n+1,cmp);
for(int i=0;i<m;i++)
{
int p;
scanf("%d%d",&k,&v);
p=find();
if(p==0)
{
if(a[b[0]]==v) printf("%d\n",a[b[k-1]]==v? b[k-1]:0);
else if(a[b[1]]==v) printf("%d\n",a[b[k]]==v? b[k]:0);
else printf("0\n");
}
else
{

if(a[b[p-1]]==v) printf("%d\n",a[b[p+k-2]]==v? b[p+k-2]:0);
else if(a[b[p]]==v) printf("%d\n",a[b[p+k-1]]==v? b[p+k-1]:0);
else if(a[b[p+1]]==v) printf("%d\n",a[b[p+k]]==v? b[p+k]:0);
else printf("0\n");
}
}
}
return 0;
}
/*
8 9
1 3 2 2 4 3 2 1
1 3
2 4
3 2
4 2

8 4
1 3 4 5 6 7 8 9
*/
``````