11495 - Bubbles and Buckets

[tajbir2000]

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

[tajbir2000]

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]

Well.. There is a O(N*logN) algorithm..
See the following thread..

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

[kangroo]

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]

Use modified Merge sort
See 10810

[luizizmad]

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]

Don't use a package