11714 - Blind Sorting

[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

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

[LucasSchm]

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]

Got it

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

[LucasSchm]

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]

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]

10 digit prime is- 2147483647!!!

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

[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

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

[Taman]

I think acc codes should be removed ASAP. . .

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

[raincole]

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]

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

[naseef_07cuet]

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