i have got tle using bubble sort
is there any different logic to solve this problem???
11495 - Bubbles and Buckets
Moderator: Board moderators
-
- New poster
- Posts: 19
- Joined: Fri Sep 05, 2008 6:39 pm
- Location: bangladesh
- Contact:
-
- New poster
- Posts: 19
- Joined: Fri Sep 05, 2008 6:39 pm
- Location: bangladesh
- Contact:
Re: 11495 - Bubbles and Buckets using bubble sort tle
here is my code
Code: Select all
#include<stdio.h>
int main(){
int cas,i,j,count,temp,a[100005];
while(scanf("%d",&cas)&&cas){
count=0;
for(i=0;i<cas;i++)scanf("%d",&a[i]);
for(i=0;i<cas-1;i++){
for(j=i+1;j<cas;j++){
if(a[i]>a[j]){
temp=a[i];
a[i]=a[j];
a[j]=temp;
count++;
}
}
}
if(count%2==0)printf("Carlos\n");
else printf("Marcelo\n");
}
return 0;
}
Re: 11495 - Bubbles and Buckets using bubble sort tle
Well.. There is a O(N*logN) algorithm..
See the following thread..
http://acm.uva.es/board/viewtopic.php?t=7473
See the following thread..
http://acm.uva.es/board/viewtopic.php?t=7473
11495 - Bubbles and Buckets , TLE
Hi,
I tried to use binary tree and count the number of swaps needed but getting TLE......
below is my code...anyone pls help me !!
thanks in advance !!
thanks again!!
waiting for help !!
I tried to use binary tree and count the number of swaps needed but getting TLE......
below is my code...anyone pls help me !!
thanks in advance !!
Code: Select all
#include <iostream>
using namespace std;
struct node
{
int val;
struct node *left;
struct node *right;
};
long long cnt;
struct node *root;
void right_subtree ( struct node *p )
{
struct node *q;
q = p -> right;
if ( q == NULL ) return;
else
{
cnt ++;
if ( q -> left != NULL )
right_subtree( q -> left );
if ( q -> right != NULL )
right_subtree( q -> right );
}
return;
}
struct node *addtree ( struct node *p , int x )
{
struct node* q;
if ( p == NULL )
{
p = new node();
p -> val = x;
p -> left = p -> right = NULL;
}
else if ( x < p -> val )
{
cnt ++;
right_subtree(p);
p -> left = addtree ( p -> left , x );
}
else
p -> right = addtree ( p -> right , x );
return p;
}
int main ()
{
int n;
while ( scanf ( "%d" , &n ) == 1 && n )
{
root = NULL;
cnt = 0;
for ( int i = 0 ; i < n ; i ++ )
{
int x;
scanf ( "%d" , &x );
root = addtree ( root , x );
}
//printf ( "%lld\n" , cnt );
if ( cnt%2 ) printf ( "Marcelo\n" );
else printf ( "Carlos\n" );
}
return 0;
}
waiting for help !!
Re: 11495 - Bubbles and Buckets using bubble sort tle
Use modified Merge sort
See 10810
See 10810
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)
Beliefs are not facts, believe what you need to believe;)
Re: 11495 - Bubbles and Buckets using bubble sort tle
Hi everyone, can anyone help me? im gettin run time error and i don't see where, when i run it on my pc it runs without any problem, here's my JAVA code.
Code: Select all
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package bubbles.and.buckets;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
*
* @author LuisMiguel
*/
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) throws IOException {
BufferedReader in;
File archivo = new File("entrada.txt");
if( archivo.exists() ) in = new BufferedReader( new FileReader( archivo ) );
else in = new BufferedReader( new InputStreamReader( System.in ) );
/*INICIO DEL CÓDIGO DEL PROBLEMA*/
String cad;
StringTokenizer ts;
while( (cad = in.readLine() ) != null )
{
ts = new StringTokenizer(cad);
if(cad.equals("0")){
break;
}
else{
int cuantos = Integer.parseInt(ts.nextToken());
int[] arreglo = new int[cuantos];
for(int i=0;i<cuantos;i++){
arreglo[i]=Integer.parseInt(ts.nextToken());
}
long inversiones = mergeSort(arreglo, 0, arreglo.length-1);
if((inversiones%2) == 0){
System.out.println("Carlos");
}
else{
System.out.println("Marcelo");
}
}
}
}
public static long mergeSort(int[] a, int p, int r)
{
long countInversion = 0;
if(p < r)
{
int q = (p + r)/2;
countInversion = mergeSort(a, p, q);
countInversion += mergeSort(a, q+1, r);
countInversion += merge(a, p, q, r);
}
return countInversion;
}
public static long merge(int[] a, int p, int q, int r)
{
long countingInversion = 0;
int n1 = q-p+1;
int n2 = r-q;
int[] temp1 = new int[n1+1];
int[] temp2 = new int[n2+1];
for(int i=0; i<n1; i++) temp1[i] = a[p+i];
for(int i=0; i<n2; i++) temp2[i] = a[q+1+i];
temp1[n1] = Integer.MAX_VALUE;
temp2[n2] = Integer.MAX_VALUE;
int i = 0, j = 0;
for(int k=p; k<=r; k++)
{
if(temp1[i] <= temp2[j])
{
a[k] = temp1[i];
i++;
}
else
{
a[k] = temp2[j];
j++;
countingInversion=countingInversion+(n1-i);
}
}
return countingInversion;
}
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 11495 - Bubbles and Buckets using bubble sort tle
Don't use a package
Check input and AC output for thousands of problems on uDebug!