Page 1 of 1

### 11495 - Bubbles and Buckets

Posted: Sat Oct 25, 2008 10:30 pm
i have got tle using bubble sort
is there any different logic to solve this problem???

### Re: 11495 - Bubbles and Buckets using bubble sort tle

Posted: Sun Oct 26, 2008 6:12 pm
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

Posted: Mon Oct 27, 2008 9:54 am
Well.. There is a O(N*logN) algorithm..

http://acm.uva.es/board/viewtopic.php?t=7473

### 11495 - Bubbles and Buckets , TLE

Posted: Tue Oct 28, 2008 7:41 am
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 !!

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;
}
``````
thanks again!!
waiting for help !!

### Re: 11495 - Bubbles and Buckets using bubble sort tle

Posted: Wed Feb 10, 2010 6:22 pm
Use modified Merge sort
See 10810

### Re: 11495 - Bubbles and Buckets using bubble sort tle

Posted: Sat Oct 05, 2013 9:25 pm
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.File;
import java.io.IOException;
import java.util.StringTokenizer;

/**
*
* @author LuisMiguel
*/
public class Main {

/**
* @param args the command line arguments
*/
public static void main(String[] args) throws IOException {
if( archivo.exists() ) in = new BufferedReader( new FileReader( archivo ) );

/*INICIO DEL CĂ“DIGO DEL PROBLEMA*/
StringTokenizer ts;

{
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;
}
}
``````

### Re: 11495 - Bubbles and Buckets using bubble sort tle

Posted: Tue Oct 08, 2013 9:58 pm
Don't use a package