10107 - What is the Median?

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

Moderator: Board moderators

deadangelx
New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

10107 WA, why??

Post by deadangelx » Wed Feb 14, 2007 6:03 pm

My OS is windows XP SP2
I use DEV-C to compile
It seems right
But when I transfered on ACM, I got WA
I try mant sample input, and the answer is right

Code: Select all

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
  long long int data;
  struct node *next; 
}root;

main()
{
  int i,flag,count;
  root *list; root *firstNode; root *insertNode; root *head;
  i=1;
  list=(root*)malloc(sizeof(struct node));
  head=(root*)malloc(sizeof(struct node));
  list->data=-1;
  head->data=-1;
  firstNode=(root*)malloc(sizeof(struct node));
  while(scanf("%lld",&firstNode->data)==1)
    {if(0<=firstNode->data) break;}
  printf("%lld\n",firstNode->data);
  firstNode->next=NULL;
  list->next=firstNode;
  head->next=firstNode;
  i++; 
  while(i<=10000)
  {
    flag=1; count=0;
    insertNode=(root*)malloc(sizeof(struct node));
    while(scanf("%lld",&insertNode->data)==1)
      {if(0<=insertNode->data) break;}
    insertNode->next=NULL;
    list=head;
    if(list->next!=NULL)
    {
      while(((list->next)->data)<(insertNode->data))
      {
        list=list->next;
        if(list->next==NULL)
        {
          list->next=insertNode;
          flag=0;
        }
      }
      if(flag)
      {
        insertNode->next=list->next;
        list->next=insertNode;
      }
    }
    else
      list->next=insertNode;
    list=head;
    while(count<((i+1)/2)) {list=list->next; count++;}
    if(i&0x00000001==1)
      printf("%lld\n",list->data);
    else
      printf("%lld\n",((list->data+(list->next)->data)/2));  
    i++;
  }
}


abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 10107 - What is the Median?

Post by abid_iut » Fri Dec 05, 2008 11:35 am

someone please help
I am getting WA for this problem but i think it passes all the I/O
please someone check the code and tell me where is the mistake
here is the code:

Code: Select all

Removed After AC

pls help :cry:
Last edited by abid_iut on Sat Dec 06, 2008 1:08 pm, edited 1 time in total.
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10107 - What is the Median?

Post by Articuno » Fri Dec 05, 2008 12:19 pm

You are using wrong format specifier. Change the data type to long long. That will do. Good luck
May be tomorrow is a better day............ :)

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 10107 - What is the Median?

Post by abid_iut » Fri Dec 05, 2008 7:46 pm

Yhankx for ur help Articuno
But TLE
is there any other problem I should sort out
pls help
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10107 - What is the Median?

Post by Articuno » Fri Dec 05, 2008 8:17 pm

I submiited your code and it was 2.430s not TLE. Your problem is in data type. Pls recheck and declare all variables as long long. Check carefully. You shouldn't get TLE with this code though it will take more than 2 seconds.

And also replace this part of your code:

Code: Select all

sort(input,input+c);
with this:

Code: Select all

stable_sort(input,input+c);
I got AC using stable_sort().
Hope it helps.
Wish you good luck. :-?
May be tomorrow is a better day............ :)

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 10107 - What is the Median?

Post by abid_iut » Sat Dec 06, 2008 8:27 am

Thankx Articuno
Now got AC at 2.370sec :)
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

pok
New poster
Posts: 25
Joined: Sun Nov 09, 2008 11:04 pm

Re: 10107 - What is the Median?

Post by pok » Sun Dec 21, 2008 12:30 am

why TLE ?????
i used mergesort .. but also get TLE...
what can i do for that..???????

Code: Select all

removed after AC..
:)
Last edited by pok on Sun Dec 21, 2008 9:02 pm, edited 1 time in total.

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

Re: 10107 - What is the Median?

Post by mf » Sun Dec 21, 2008 1:07 am

You shouldn't sort at every step. There are better algorithms to solve this problem.

First, if you're lazy, you could have used insertion sort, which would run in time O(n) at each step - which is better than an O(n log n) quicksort/mergesort.

Second, you could use some data structures other than an array to represent the sequence of numbers. For example, a pair of heaps (a max-heap and a min-heap to keep the upper and lower halves of numbers), or a binary tree. Both of them allow to do each step in O(log n) time.

pok
New poster
Posts: 25
Joined: Sun Nov 09, 2008 11:04 pm

Re: 10107 - What is the Median?

Post by pok » Sun Dec 21, 2008 9:06 pm

thanks mf..
but i just removed mergesort & simply sort datas..
i didn't use data structure..& now my code is AC..
take care..
God bless you..

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10107 - What is the Median?

Post by Obaida » Tue Feb 10, 2009 9:09 am

I think insertion sort is good for this problem..
i got acc using insertion sort & here is status:
10107 829 6938330 2009-02-10 07:00:21 0.180
No trick just an easy problem. :D
try_try_try_try_&&&_try@try.com
This may be the address of success.

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

10107 - What is the Median?

Post by sazzadcsedu » Tue Apr 14, 2009 11:12 pm

if u have problem with TLE
DON'T USE QUICK SORT/MERGE SORT ,BECAUSE THIS PROBLEM REQUIRES O(lgN) ALGORITHM FOR SORTING IN EACH
STEP.QUICKSORT REQUIRE O(NlgN) in every step.As u have to insert n number of data, quicksort complexity becomes(n^2lgn) .which is not possible for n=10000. SO U CAN USE INSERTION SORT WHICH RUN O(lgN) IN THIS PROBLEM BECAUSE THE PREVIOUS ARRAY IS SORTED.AND USE BINARY SEARCH TO FIND THE POSITION OF CURRENT ITEM IN THE ARRAY,LINEAR SEARCH CAN'T PASS TLE.
MY RUNNING TIME 0.050(321).SO U CAN FOLLOW THIS APPROACH.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

avatar
New poster
Posts: 8
Joined: Wed Nov 16, 2011 6:44 pm

Re: 10107 - What is the Median?

Post by avatar » Sat Nov 26, 2011 4:02 pm

oh..............
at last after thousands of TLE i got AC........!!!!!!!!
for the friends those who are suffering as i was ......... :evil:
don't go for bubble sort for each input , rather select appropriate position for
the input and do the simple calculation for finding the medians......................... :lol:


best of luck....................

memi
New poster
Posts: 1
Joined: Tue Apr 09, 2013 12:28 am

10107 - What is the Median?

Post by memi » Tue Apr 09, 2013 1:01 am

i get TLE ,,,any help plz :cry:

Code: Select all

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	long long temp=0 , i=0 , Temp=0 , k=0, j, tmp=0;
	vector<long long>v;
	while(true)
	{
		cin>>temp;
		i=0;
		v.push_back(temp);
		if(v.size()==1)
			cout<<temp<<endl;
		else
		{
			sort(v.begin() , v.end());

			//for (j = 1; j < v.size(); j++) 
			//{
				//k = j;
				//while (k > 0 && v[k - 1] > v[k]) 
				//{
				//	tmp = v[k];
				//	v[k] = v[k - 1];
				//	v[k - 1] = tmp;
				//	k--;
				//}
			//}

			if(v.size()%2==0)
			{
				i=(v.size()-2)/2;
				cout<<(v[i]+v[i+1])/2<<endl;
			}
			else
			{
				i=(v.size()-1)/2;
				cout<<v[i]<<endl;
			}
		}
	}
	return 0;
}

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

Re: 10107 - What is the Median?

Post by brianfry713 » Tue Apr 09, 2013 3:47 am

Your code never terminates, instead try something like:
while(cin>>temp) {
Check input and AC output for thousands of problems on uDebug!

RoniphpBB
New poster
Posts: 10
Joined: Sat Feb 09, 2013 11:22 am

Re: 10107 - What is the Median?

Post by RoniphpBB » Wed May 29, 2013 2:48 am

U
I got AC
Last edited by RoniphpBB on Sat Jun 15, 2013 11:13 pm, edited 1 time in total.

Post Reply

Return to “Volume 101 (10100-10199)”