## 11714 - Blind Sorting

Moderator: Board moderators

LucasSchm
New poster
Posts: 17
Joined: Mon May 18, 2009 10:00 pm

### 11714 - Blind Sorting

I would like some critical test cases, as i can't see why my solution is wrong (been getting WA).

My code:

Code: Select all

``````#include <stdio.h>
#include <math.h>

long long potenciasDois[50];

void CalculaPotencias() {
long long i;
long long x;

x = 1;
potenciasDois[0] = 0;
for (i=1; i < 40; i++) {
potenciasDois[i] = x;
x = x*2;
}

return ;
}

int PotenciaVef(long long numero) {
int i;

i = 0;
while (potenciasDois[i] < numero) {
i++;
}

if (potenciasDois[i] == numero) {
return i;
}

return 0;
}

int main (void) {
long long numero;
long long n;

CalculaPotencias();
while (scanf("%lld", &numero) != EOF) {

n = numero - 1 + floor(log2(numero));

if (numero % 2 == 0) {
if (PotenciaVef(numero)) {
n--;
}
}

printf("%lld\n", n);
}

return 0;
}``````
My own input:

Code: Select all

``````2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
7427466391
17179869184
512
1024
2048
4096
4097
``````
My output:

Code: Select all

``````1
3
4
6
7
8
9
11
12
13
14
15
16
17
18
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
7427466422
17179869216
519
1032
2057
4106
4108
``````

Bruno
New poster
Posts: 22
Joined: Thu Oct 01, 2009 9:03 pm

### Re: 11714 Blind Sorting

Haha! You posted 5 minutes before me

Sorry for my post I will delete it!

On my post I was asking for tips to do this, because I didnt understand it very well

About your WA, did you tested with 1? (just trying to guess )

LucasSchm
New poster
Posts: 17
Joined: Mon May 18, 2009 10:00 pm

### Re: 11714 Blind Sorting

Bruno wrote:Haha! You posted 5 minutes before me

Sorry for my post I will delete it!

On my post I was asking for tips to do this, because I didnt understand it very well

About your WA, did you tested with 1? (just trying to guess )
The problem says, " n will be less than any 10 digit prime number and not less than the smallest prime.", so n will be >= 2.

About the problem, i will try to explain. Given n numbers, it wants to know how many questions i must do to be sure of the largest and second largest number.

Supose n = 4, so i have A, B, C, D, which i know nothing about them. Then, instead of compare A to everyone, B to everyone and so on, a better approach is to build a "tree". Ask if A is larger than B and if C is larger than D. Now that i know the larger between AB and CD, with only one more question i can know the larger of all of them. So untill now i made 3 quesitons, but i still need to know the second larger. What if A were the second larger? or B? or C? or D? When/How is the worst case? Now it's up to you.

Bruno
New poster
Posts: 22
Joined: Thu Oct 01, 2009 9:03 pm

### Re: 11714 Blind Sorting

Got it

But why do you check if the number is even and check if PotenciaVef is true?

LucasSchm
New poster
Posts: 17
Joined: Mon May 18, 2009 10:00 pm

### Re: 11714 Blind Sorting

Bruno wrote:Got it

But why do you check if the number is even and check if PotenciaVef is true?
Because if it's odd then for sure it isn't a 2^x. It's just an "optimization" to not call the function PotenciaVef (Power[of 2]Verify).

But if you are asking if there is something special about them (numbers of 2^x) or not... do manually the cases from 2 to 10.

Bruno
New poster
Posts: 22
Joined: Thu Oct 01, 2009 9:03 pm

### Re: 11714 Blind Sorting

I understood it now

Implemented it and got accepted! Comparing with your code I only see one difference: Instead of long long I used unsigned int, and calculated only the first 31 power of two numbers (2 ... 2147483648, I hope there is a 10 digit prime before 2147483648!!!)

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11714 Blind Sorting

10 digit prime is- 2147483647!!!

Bruno
New poster
Posts: 22
Joined: Thu Oct 01, 2009 9:03 pm

### Re: 11714 Blind Sorting

Thanks Igor!

After analyzing a bit more, here is a tip, you dont need to check if its power of 2! (You will need to change something with the formula)

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

### Re: 11714 Blind Sorting

This is a faily easy problem if u consider a binary tree for finding the largest number
and the second largest number can also compute with the complesity of binary time

formula is
largest=n-1
second largest = lg2(n-1)
then sum the above two numbers
Try to catch fish rather than asking for some fishes.

LucasSchm
New poster
Posts: 17
Joined: Mon May 18, 2009 10:00 pm

### Re: 11714 Blind Sorting

So i took this ACC code (thanks, bruno):

Code: Select all

``````#include <iostream>
#include <math.h>
using namespace std;

main(void)
{
unsigned int n;
while (cin >> n)
{
--n;
cout << n+(unsigned int)log2(n) << endl;
}
return 0;
}
``````
Note that this does what arifsecu suggested. But then i looked at it and couldn't see a single difference from my code. So, as Igor said, 2147483647 is the first 10-digit prime, so why not to test my code against this ACC to see where is the mistake? Thats exactly what i did, a loop from 2 to 2147483647 testing every single one of them. Below follows the code fo this.

Code: Select all

``````/* consider the auxiliary functions from my first post */

int main (void) {
long long numero, i;
long long n, aux;

CalculaPotencias();
i = 2;
while (i <= 2147483647) {
n = aux = i;

n = i - 1 + floor(log2(i));

if (i % 2 == 0) {
if (PotenciaVef(i)) {
n--;
}
}

aux--;
aux = aux +(long long)log2(aux);
if (aux != n) {
printf("%lld %lld\n", i, aux);
}

i++;
}

return 0;
}
``````
Well, you would expect at least one printf from that IF, but surprise, not a single one. So, how can it be right and wrong at the same time?

I even considerated as stop condition a negative number, as the problem isn't clear if it ends when it reaches EOF or a negative number ("There will be a non-negative integer, n in each of the line of input where n is as described above. n will be less than any 10 digit prime number and not less than the smallest prime.").

Taman
New poster
Posts: 32
Joined: Sun Oct 11, 2009 8:59 pm
Location: Southeast University

### Re: 11714 Blind Sorting

I think acc codes should be removed ASAP. . .

LucasSchm
New poster
Posts: 17
Joined: Mon May 18, 2009 10:00 pm

### Re: 11714 Blind Sorting

I think acc codes should be removed ASAP. . .
I know about the rule of removing ACC code, but i would like to know why i keep getting WA with my code, even thought it outputs exactly the same. Maybe other people are having the same trouble...

raincole
New poster
Posts: 6
Joined: Wed Sep 23, 2009 4:42 pm

### Re: 11714 Blind Sorting

arifcsecu wrote:This is a faily easy problem if u consider a binary tree for finding the largest number
and the second largest number can also compute with the complesity of binary time

formula is
largest=n-1
second largest = lg2(n-1)
then sum the above two numbers
How to prove that it's minimum?

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

### Re: 11714 Blind Sorting

try to build to Binary tree(Decision tree) for finding largest element
then search the binary tree for finding second largest element

Hope you understand the matter
Try to catch fish rather than asking for some fishes.

naseef_07cuet
Learning poster
Posts: 62
Joined: Sat Nov 21, 2009 10:17 pm