exG - topas2008

[polska]

Boas pessoal, estive a tentar resolver os últimos problemas de várias edições do Topas e parei neste:

http://img40.imageshack.us/img40/4595/semttulobjv.png

Exemplo

Input

11 18 8 17 18 14

8 18 18 9 18 18

11 18 18 18 18 18

13 12 18 18 15 18

Output

4 3 1 2

É um problema muito fácil de entender, e a primeira coisa que pensei foi ordenar os valores de cada jogador por ordem crescente.. Assim tenho logo tudo ordenado pela pior cor e é mais fácil comparar jogador com jogador.. Mas depois complica, porque por exemplo, comparo os primeiros valores e sei que o 4º jogador ganha, mas a seguir tenho que voltar a comparar porque o 2º classificado também pode ser descoberto a partir da primeira pior cor, mas como excluo o 4º jogador das comparações? e depois começam a vir resultados iguais e tenho que passar para a segunda pior cor.. Alguém me pode dar umas luzes de um algoritmo eficiente para este problema?

[HappyHippyHippo]

necessitas de 5 bits para guardar o número 20, logo podes guardar 6 valores num int de 32 bits

se ordenares os valores por alguma ordem pré determinada, podes ter algo deste género:

exemplo por ordem crescente
A - valores da pior pontuação
B - valores da segunda pior pontuação 
... por ai a diante

jogador1 = 00AAAAABBBBBCCCCCDDDDDEEEEEFFFFF
jogador2 = 00AAAAABBBBBCCCCCDDDDDEEEEEFFFFF

vencedor = quem tiver o maior valor

espero que percebar as dicas minimalista que dei

Edited October 14, 2012 at 03:25 PM by HappyHippyHippo

[pmg]

Brute force FTW 🙂

Substitui a pontuação do jogador classificado por -1?

comparo os primeiros valores e sei que o 4º jogador ganha

A seguir metes -1 em todas as colunas do 4º jogador e determinas o ganhante com as novas pontuações.

[polska]

necessitas de 5 bits para guardar o número 20, logo podes guardar 6 valores num int de 32 bits

se ordenares os valores por alguma ordem pré determinada, podes ter algo deste género:

exemplo por ordem crescente
A - valores da pior pontuação
B - valores da segunda pior pontuação
... por ai a diante

jogador1 = 00AAAAABBBBBCCCCCDDDDDEEEEEFFFFF
jogador2 = 00AAAAABBBBBCCCCCDDDDDEEEEEFFFFF

vencedor = quem tiver o maior valor

espero que percebar as dicas minimalista que dei

eu percebi a ideia, mas como guardo os 6 valores num int?

Brute force FTW 🙂

Substitui a pontuação do jogador classificado por -1?

A seguir metes -1 em todas as colunas do 4º jogador e determinas o ganhante com as novas pontuações.

Pensei nessa solução, colocar toda a linha de um jogador já determinado a -1 ou 0 .. Mas depois comecei a pensar naqueles casos em que existem muitas repetições de resultados e assim, e pensei que se calhar brute force não funcionasse, mas não fiz cálculos (preguiçoso... !!!)... 😄

[Warrior]

necessitas de 5 bits para guardar o número 20, logo podes guardar 6 valores num int de 32 bits

Lembra-te que ninguém te disse que eram só números até 20 e só 6 números.

Isto é um problema de ordenação, se conheces algoritmos de ordenação basta aplicares um. Eu juntava o útil ao agradável. Estás a programar isto em que linguagem, C ou C++? Aproveita para aprender a fazer funções de comparação para o quicksort.

[polska]

Lembra-te que ninguém te disse que eram só números até 20 e só 6 números.

Isto é um problema de ordenação, se conheces algoritmos de ordenação basta aplicares um. Eu juntava o útil ao agradável. Estás a programar isto em que linguagem, C ou C++? Aproveita para aprender a fazer funções de comparação para o quicksort.

Em C .

Que tipo de comparações falas? Tipo ao ordenar fazer logo comparações de resultados entre jogadores?

[HappyHippyHippo]

Lembra-te que ninguém te disse que eram só números até 20 e só 6 números.

sim . não diz que é só até 20, mas diz que é só 6

PS :

#include <stdio.h>
#include <stdlib.h>

#define PLAYER_COUNT 4
#define PLAYER_SCORE_COUNT 6

#define SCORE_SIZE 5
#define SCORE_MAX (~0U >> (32 - SCORE_SIZE))
#define SCORE_POS(pos) ((32 / SCORE_SIZE) - pos - 1)
#define SCORE_BITPOS(pos) ((SCORE_POS(pos) * SCORE_SIZE) + 1)
#define SCORE_GET(score, pos) ((score >> SCORE_BITPOS(pos)) & SCORE_MAX)
#define SCORE_SET(score, pos, value) ((value << SCORE_BITPOS(pos)) | \
                                     (score & ~(SCORE_MAX << SCORE_BITPOS(pos))))
#define SCORE_INJECT(score, pos, value) ((score >> SCORE_BITPOS(pos) << SCORE_BITPOS(pos + 1)) | \
                                        (value << SCORE_BITPOS(pos))) | \
                                        (score & (~0U >> (32 - SCORE_BITPOS(pos))))

int input[PLAYER_COUNT][PLAYER_SCORE_COUNT] =
       {{11,18, 8,17,18,14},
        { 8,18,18, 9,18,18},
        {11,18,18,18,18,18},
        {13,12,18,18,15,18}};

int main()
{
unsigned int scores[PLAYER_COUNT];
int i, j, k;

// leitura do input com ordenação
for (i = 0; i < PLAYER_COUNT; i++)
{
	scores[i] = 0;
	for (j = 0; j < PLAYER_SCORE_COUNT; j++)
	{
		k = 5;
		while (SCORE_GET(scores[i], k) > input[i][j])
		{
			k--;
		}
		scores[i] = SCORE_INJECT(scores[i], k, input[i][j]);
	}
}

// agora é só ordenar o array scores e quem tiver o maior valor é o vencedor

return 0;
}

Edited October 14, 2012 at 06:03 PM by HappyHippyHippo

[pmg]

Isto é um problema de ordenação

Oops ... ignora o meu post anterior (o que sugeria meter a pontuação a -1). O Warrior tem razão.

Hint: mete o número de ordem do jogador como fazendo parte de cada linha.

Ao ordenares tudo (sem ter em conta o número de ordem), não perdes essa informação e podes usá-la para apresentar o resultado.

[polska]

#include <stdio.h>
#include <stdlib.h>

#define PLAYER_COUNT 4
#define PLAYER_SCORE_COUNT 6

#define SCORE_SIZE 5
#define SCORE_MAX (~0U >> (32 - SCORE_SIZE))
#define SCORE_POS(pos) ((32 / SCORE_SIZE) - pos - 1)
#define SCORE_BITPOS(pos) ((SCORE_POS(pos) * SCORE_SIZE) + 1)
#define SCORE_GET(score, pos) ((score >> SCORE_BITPOS(pos)) & SCORE_MAX)
#define SCORE_SET(score, pos, value) ((value << SCORE_BITPOS(pos)) | \
								  (score & ~(SCORE_MAX << SCORE_BITPOS(pos))))
#define SCORE_INJECT(score, pos, value) ((score >> SCORE_BITPOS(pos) << SCORE_BITPOS(pos + 1)) | \
									 (value << SCORE_BITPOS(pos))) | \
									 (score & (~0U >> (32 - SCORE_BITPOS(pos))))

int input[PLAYER_COUNT][PLAYER_SCORE_COUNT] =
	{{11,18, 8,17,18,14},
	 { 8,18,18, 9,18,18},
	 {11,18,18,18,18,18},
	 {13,12,18,18,15,18}};

int main()
{
unsigned int scores[PLAYER_COUNT];
int i, j, k;

// leitura do input com ordenação
for (i = 0; i < PLAYER_COUNT; i++)
{
	scores[i] = 0;
	for (j = 0; j < PLAYER_SCORE_COUNT; j++)
	{
		k = 5;
		while (SCORE_GET(scores[i], k) > input[i][j])
		{
			k--;
		}
		scores[i] = SCORE_INJECT(scores[i], k, input[i][j]);
	}
}

// agora é só ordenar o array scores e quem tiver o maior valor é o vencedor

return 0;
}

Happy podes me explicar como funcionam os define GET e INJECT? É que depois chamam outros defines e eu não consigo perceber como é que se esta a converter o score para outro inteiro e se vai somando no array final... Já agora, ao dizeres-me que preciso de 5 bits para o numero 20, e se acontecesse de haver scores que ocupem mais bits, tipo 84.. Não há esse problema?

Sinto-me muito burro ao tentar entender o que fizeste xD

Oops ... ignora o meu post anterior (o que sugeria meter a pontuação a -1). O Warrior tem razão.

Hint: mete o número de ordem do jogador como fazendo parte de cada linha.

Ao ordenares tudo (sem ter em conta o número de ordem), não perdes essa informação e podes usá-la para apresentar o resultado.

Vou fazer as duas soluções, a de ordenação penso já ter entendido bem, é só implementar 😉

[Warrior]

Se quiseres usar a função "qsort", pesquisa por "C custom qsort function".

[HappyHippyHippo]

Happy podes me explicar como funcionam os define GET e INJECT?

antes do mais tens de perceber como estão codificadas os resultados num inteiro de 32 bits

como referi no post anterior, o que está a acontecer é, que existe 6 posições para guardar os resultados de cada cor, cada um com 5 bits.

estas posição encontram se dispostas desta maneira:

resultado1 : -XXXXX--------------------------
resultado2 : ------XXXXX---------------------
resultado3 : -----------XXXXX----------------
resultado4 : ----------------XXXXX------------
resultado5 : ---------------------XXXXX------
resultado6 : --------------------------XXXXX-

então a única coisa que o GET faz é fazer um right shift do número de bits necessários para que a posição pedida fique nos bits menos significativos, aplicando depois a máscara de 5 bits a 1 para que selecione a posição correcta. visualmente é:

posicao 4 : ----------------XXXXX------------
depois do right shift
posicao 4 : 000000000000----------------XXXXX
aplicar a máscara
posicao 4 : 0000000000000000000000000000XXXXX

e desta forma obtens somente o número guardado na posição N

o inject é mais complicado, porque a sua intensão é inserir numa posição específica mas deixando as posição á direita intactas e mover as posições é esquerda uma posição nessa direcção. isto serve para inserir os valores de uma forma ordenada.

imagina que estou a ler o input com os valores {4, 2, 1, 3, 6, 5}, isto daria visualmente:

inicialmente      : --------------------------------
inserir 4 (pos 5) : --------------------------00004-
inserir 2 (pos 4) : ---------------------0000200004-
inserir 1 (pos 3) : ----------------000010000200004-
inserir 3 (pos 4) : -----------00001000020000300004-
inserir 6 (pos 5) : ------0000100002000030000400006-
inserir 5 (pos 5) : -000010000200003000040000500006-

agora explicar todo o código da macro é complicado, mas por alto será a conbinação dos bits resultantes do bitwise or destes três componentes :

- seleccionar a parte da esquerda da posição a inserir e mover-la uma posição para esse lado

((score >> SCORE_BITPOS(pos) << SCORE_BITPOS(pos + 1))

- escrever o valor a inserir na posição escolhida

(value << SCORE_BITPOS(pos)))

- selecionar as posições da direita

(score & (~0U >> (32 - SCORE_BITPOS(pos))))

como vês, não tem nada que saber 😄

Já agora, ao dizeres-me que preciso de 5 bits para o numero 20, e se acontecesse de haver scores que ocupem mais bits, tipo 84.. Não há esse problema?

claro, em 5 bits só consegues guardar um valor até 31, mas nada indica que no enunciado que tal acontece, assim como os valores apresentados são claramente inferiores a 31 (a 20 até)

Sinto-me muito burro ao tentar entender o que fizeste xD

pratica que vais lá

como te disse, o valor final (o inteiro) será um valor ponderado dos resultados.

imagina, se o resultado seria um número de 0 a 9 (um dígito). se tiveres {x1,x2 ... x6} e {y1,y2 ... y6} ambos ordenados por ordem crescente, então:

se x1 > y1 então :

x1*10^5 + x2*10^4 + ... + x6 > y1*10^5 + y2*10^4 + ... + y6

isto porque o seguinte será sempre verdade :

y2*10^4 + y3*10^3 + ... + y6 < 10^5 (porque y(n) nunca é maior que 9)

com valores:

x = {1, 2, 3, 4, 5, 6}, y = {1, 1, 3, 4, 5, 6}

então

x = 1*10^5 + 2*10^4 + ... + 6 = 123456

y = 1*10^5 + 1*10^4 + ... + 6 = 113456

o mesmo se aplica neste caso (exercício) porque os valores estão codificados em ordens de grandeza diferentes (5 bits para cada)

Edited October 14, 2012 at 08:52 PM by HappyHippyHippo

[polska]

Jesus!! Não tem nada que saber não 😄 , eu ainda vou levar algum tempo a perceber isto, mas vou chegar lá xDD ! Tenho que entender bem os bitwises, que me dá dor de cabeça quando tento perceber cada um..

Anyway, obrigado pela resposta @Happy 👍

Edited October 15, 2012 at 07:59 PM by polska