Page **1** of **1**

### 11714 - Blind Sorting

Posted: **Tue Oct 27, 2009 8:57 pm**

by **LucasSchm**

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

### Re: 11714 Blind Sorting

Posted: **Tue Oct 27, 2009 10:20 pm**

by **Bruno**

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

)

### Re: 11714 Blind Sorting

Posted: **Tue Oct 27, 2009 10:47 pm**

by **LucasSchm**

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.

### Re: 11714 Blind Sorting

Posted: **Wed Oct 28, 2009 10:26 pm**

by **Bruno**

Got it

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

### Re: 11714 Blind Sorting

Posted: **Wed Oct 28, 2009 11:36 pm**

by **LucasSchm**

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.

### Re: 11714 Blind Sorting

Posted: **Thu Oct 29, 2009 2:51 am**

by **Bruno**

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

### Re: 11714 Blind Sorting

Posted: **Thu Oct 29, 2009 6:51 am**

by **Igor9669**

10 digit prime is- 2147483647!!!

### Re: 11714 Blind Sorting

Posted: **Thu Oct 29, 2009 5:37 pm**

by **Bruno**

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)

### Re: 11714 Blind Sorting

Posted: **Thu Oct 29, 2009 6:24 pm**

by **arifcsecu**

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

### Re: 11714 Blind Sorting

Posted: **Thu Oct 29, 2009 7:45 pm**

by **LucasSchm**

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.").

### Re: 11714 Blind Sorting

Posted: **Thu Oct 29, 2009 11:51 pm**

by **Taman**

I think acc codes should be removed ASAP. . .

### Re: 11714 Blind Sorting

Posted: **Fri Oct 30, 2009 12:51 am**

by **LucasSchm**

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

### Re: 11714 Blind Sorting

Posted: **Sat Oct 31, 2009 12:51 pm**

by **raincole**

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?

### Re: 11714 Blind Sorting

Posted: **Sat Oct 31, 2009 4:28 pm**

by **arifcsecu**

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

### Re: 11714 Blind Sorting

Posted: **Sun Feb 21, 2010 9:58 am**

by **naseef_07cuet**

I think we shouldn't reveal the formulas directly....plz ....