## 11495 - Bubbles and Buckets

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

Moderator: Board moderators

tajbir2000
New poster
Posts: 19
Joined: Fri Sep 05, 2008 6:39 pm
Location: bangladesh
Contact:

### 11495 - Bubbles and Buckets

i have got tle using bubble sort
is there any different logic to solve this problem???

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

``````

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### 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

kangroo
New poster
Posts: 13
Joined: Fri Sep 12, 2008 9:12 am

### 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 !!

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 !!

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

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

Use modified Merge sort
See 10810
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

luizizmad
New poster
Posts: 1
Joined: Sat Oct 05, 2013 9:20 pm

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

brianfry713
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!