11714 - Blind Sorting

All about problems in Volume 117. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11714 - Blind Sorting

Post by LucasSchm » 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

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

Re: 11714 Blind Sorting

Post by Bruno » Tue Oct 27, 2009 10:20 pm

Haha! You posted 5 minutes before me :oops:

Sorry for my post :oops: I will delete it!

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

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

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

Re: 11714 Blind Sorting

Post by LucasSchm » Tue Oct 27, 2009 10:47 pm

Bruno wrote:Haha! You posted 5 minutes before me :oops:

Sorry for my post :oops: I will delete it!

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

About your WA, did you tested with 1? (just trying to guess :roll: )
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

Post by Bruno » Wed Oct 28, 2009 10:26 pm

Got it :D

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

Post by LucasSchm » Wed Oct 28, 2009 11:36 pm

Bruno wrote:Got it :D

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

Post by Bruno » Thu Oct 29, 2009 2:51 am

I understood it now :D

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

Post by Igor9669 » Thu Oct 29, 2009 6:51 am

10 digit prime is- 2147483647!!!

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

Re: 11714 Blind Sorting

Post by Bruno » 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) :D

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

Re: 11714 Blind Sorting

Post by arifcsecu » 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
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

Post by LucasSchm » 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.").

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

Re: 11714 Blind Sorting

Post by Taman » Thu Oct 29, 2009 11:51 pm

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

Post by LucasSchm » 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...

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

Re: 11714 Blind Sorting

Post by raincole » 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?

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

Re: 11714 Blind Sorting

Post by arifcsecu » 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
Try to catch fish rather than asking for some fishes.

naseef_07cuet
Learning poster
Posts: 62
Joined: Sat Nov 21, 2009 10:17 pm
Location: CUET,Chittagong,Bangladesh

Re: 11714 Blind Sorting

Post by naseef_07cuet » Sun Feb 21, 2010 9:58 am

I think we shouldn't reveal the formulas directly....plz ....:(
If you have determination, you can do anything you want....:)

Post Reply

Return to “Volume 117 (11700-11799)”