10107 - What is the Median?

[deadangelx]

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]

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

[Articuno]

You are using wrong format specifier. Change the data type to long long. That will do. Good luck

[abid_iut]

Yhankx for ur help Articuno
But TLE
is there any other problem I should sort out
pls help

[Articuno]

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.

[abid_iut]

Thankx Articuno
Now got AC at 2.370sec

[pok]

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

Code: Select all

removed after AC..

[mf]

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]

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]

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.

[sazzadcsedu]

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.

[avatar]

oh..............
at last after thousands of TLE i got AC........!!!!!!!!
for the friends those who are suffering as i was .........
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.........................


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

[memi]

i get TLE ,,,any help plz

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]

Your code never terminates, instead try something like:
while(cin>>temp) {

[RoniphpBB]

U
I got AC