You are not logged in. Please login at www.codechef.com to post your questions!

×

TSORT: Getting wa

So, I used a quick sort to implement the problem in Java. It works fine for the given input set but gives wrong answer. Can someone help me please???

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;

public class Main {

    public static int partition(int arr[], int left, int right){
        int pivot=arr[(left+right)/2];
        int i=left;
        int j=right;
        int temp;
        while(i<=j){
            while(arr[i]<pivot)i++;
            while(arr[j]>pivot)j--;
            if(i<=j){
                temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
                i++;
                j--;}}
        return i;}

    public static void QuickSort(int arr[], int left, int right){
        int index=partition(arr,left,right);
        if(left<index-1)QuickSort(arr,left,index-1);
        if(index<right)QuickSort(arr,index,right);}

    public static void main(String[] args) throws IOException {
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintStream ps = new PrintStream(System.out);
        StringBuilder sb = new StringBuilder("");
        int t=Integer.parseInt(f.readLine());
        int [] turbo=new int[t];
        for(int i=0;i<t;i++)turbo[i]=Integer.parseInt(f.readLine());
        QuickSort(turbo,0,t-1);
        for(int i=0;i<t;i++){
            if(i==t-1)sb.append(turbo[i]).append("\n");
                else{
                if(turbo[i]!=turbo[i+1])
                sb.append(turbo[i]).append("\n");}}
         ps.println(sb);}
}

asked 31 May '12, 12:46

avengee's gravatar image

2★avengee
31114
accept rate: 0%

edited 10 Jul '12, 15:05

admin's gravatar image

0★admin ♦♦
19.8k350498541


You Picked the question in the wrong way. The question is straight forward -You just have to sort the given data-set in ascending order.

But after analyzing your code ,i think you misunderstood that only one copy of the repeated members is to be printed .

No ,that's not the case .

And here is the proof ,For the test case

10
5
3
5
6
7
1
9
7
3
2

your code was generating the following output

1
2
3
5
6
7
9

Clearly you were avoiding the printing of repeated members.

In order to fix it :

Just comment the three lines in printing steps as shown :

        QuickSort(turbo,0,t-1);
        for(int i=0;i<t;i++){
            //if(i==t-1)sb.append(turbo[i]).append("\n");//No need of it
              //  else{
                //if(turbo[i]!=turbo[i+1])//Wrong Answer due to this
                sb.append(turbo[i]).append("\n");
               // }
               }
         ps.println(sb);}
}
link

answered 31 May '12, 16:46

ritesh_gupta's gravatar image

5★ritesh_gupta ♦
3.7k42549
accept rate: 27%

edited 31 May '12, 17:09

2

@avengee - "print given numbers in non decreasing order.". u considered it as strictly non decreasing order I guess. @ritesh_gupta is correct , that's the only bug ,your quick sort looks absolutely fine .

(31 May '12, 17:01) stackoverflow2★

@ritesh_gupta: Thank you so much for the help. I didn't submit yet because I have a small question.

So, in non-decreasing order an element can be either equal or greater than the previous element?

My question is with the example input and output set in the problem statement:

Example

Input: 5 5 3 6 7 1 Output: 1 3 5 6 7

This example has avoided repeated numbers. What is it? Or am I still mistaken about the definition of non-descending numbers?

(31 May '12, 19:09) avengee2★

@avengee: first number is not from the sequence, it is the sequence length ;-)

(31 May '12, 19:11) betlista ♦♦3★

@avengee :Read the problem statement once again,especially "Input t – the number of numbers in list, then t lines follow [t <= 10^6].Each line contains one integer: N [0 <= N <= 10^6]".

So the First line 5 means there are 5 elements in the data set and these 5 elements are 5 3 6 7 1 .So our task is to sort the numbers 5 3 6 7 1

(01 Jun '12, 01:48) ritesh_gupta ♦5★

Thanks all:). I'm a new coder and sometimes I get so confused:). Thank you again for taking your valuable time to help me out for this simple question:).

(02 Jun '12, 08:11) avengee2★

pleasure:)

(02 Jun '12, 16:29) ritesh_gupta ♦5★
showing 5 of 6 show all

Try the input

4
1
1
2
2

the correct answer is

1
1
2
2

you propably misunderstood non decreasing order, read more on wikipedia.

Two hints to you:

  1. you don't need to implement sort in Java, there are Collections.sort() and Arrays.sort() methods
  2. quick sort in worst case has complexity O(n^2), so someone can challenge your solution in contests where it is possible to challenge (hack) solution.
link

answered 31 May '12, 13:41

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

edited 31 May '12, 13:54

@belista: Thank you for your valuable tips. As I previously stated in the comment for above post, I'm confused with the example. Any help is greatly appreciated:).

(31 May '12, 19:15) avengee2★

I replied in ritesh_gupta's answer.

Above or below is relative, answers are ordered by decreasing number of up votes and despite of that I answered first and ritesh_gupta copied answer 3 hours later he got more up votes...

(31 May '12, 19:22) betlista ♦♦3★

Anyways, thank you again:)

(02 Jun '12, 08:11) avengee2★

include <stdio.h>

int v[1000001]={0};

int main()

{

int n,i,a;

scanf("%d",&n);

for (i=0;i<n; i++){ scanf("%d",&a); v[a]++; }

for (n=0;n<=1000000; n++) for (i=0;i<v[n];i++) printf("%dn",n);

return 0;

}

i am getting wrong answer on this code. please someone help.

link

answered 10 May '13, 10:54

mayank199317's gravatar image

2★mayank199317
3626
accept rate: 0%

edited 10 May '13, 10:54

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,314
×1,070
×19

question asked: 31 May '12, 12:46

question was seen: 2,100 times

last updated: 10 May '13, 10:54