11991 - Easy Problem from Rujia Liu?

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

Moderator: Board moderators

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

11991 - Easy Problem from Rujia Liu?

Post by iriz7482 » Tue Apr 26, 2011 3:08 pm

hello everyone, sorry for creating this thread if you think it's useless :D
I had got TLE in this problems many times and after 6 tries I got AC in 0.104 sec using my struct :D . But I found some guys got AC in about 0.08 or even 0.03 ~ 0.05 :o . 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?

Post by rujialiu » Thu Apr 28, 2011 1:21 pm

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?

Post by MRH » Sat Apr 30, 2011 7:29 am

@ 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.
Thanks in advance.

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

Re: 11991 - Easy Problem from Rujia Liu?

Post by iriz7482 » Sun May 01, 2011 9:51 pm

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

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

Re: 11991 - Easy Problem from Rujia Liu?

Post by rujialiu » Tue May 03, 2011 3:30 pm

@MRH

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

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

Re: 11991 - Easy Problem from Rujia Liu?

Post by shaon_cse_cu08 » Tue Jun 21, 2011 11:10 am

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 ..... :x

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

Re: 11991 - Easy Problem from Rujia Liu?

Post by uvasarker » Fri Feb 17, 2012 5:53 am

Anyone will help me please. I am getting TLE. Please help me so that I can get rid of this problem.
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?

Post by brianfry713 » Fri Feb 17, 2012 10:00 pm

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

Post by atiburrahman09 » Fri Jun 29, 2012 1:58 am

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

Post by brianfry713 » Sat Jun 30, 2012 12:26 am

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

Post by esharif » Thu Jul 05, 2012 12:41 am

:oops: 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

Post by brianfry713 » Fri Jul 06, 2012 1:45 am

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

Post by wonderful008 » Sat Sep 08, 2012 6:21 am

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 link;       
	};

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;
	node->link = NULL;
	
	return node;
}


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

Re: 11991 run time error

Post by brianfry713 » Mon Sep 10, 2012 10:44 pm

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?

Post by zlshang » Thu Jan 03, 2013 9:50 am

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.... :D :D

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
*/

Post Reply

Return to “Volume 119 (11900-11999)”