Page 1 of 1

### 11714 - Blind Sorting

Posted: Tue Oct 27, 2009 8:57 pm
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
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
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
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
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
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
10 digit prime is- 2147483647!!!

### Re: 11714 Blind Sorting

Posted: Thu Oct 29, 2009 5:37 pm
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
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
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
I think acc codes should be removed ASAP. . .

### Re: 11714 Blind Sorting

Posted: Fri Oct 30, 2009 12:51 am
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
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
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
I think we shouldn't reveal the formulas directly....plz ....