ONI 2012 - Qualificação - C - Ajudando os Concorrentes

[Warrior]

http://www.dcc.fc.up.pt/oni/problemas/2012/qualificacao/probC.html

Discussão, as vossas soluções, dúvidas e ajudas!

[xtrm0]

Como e que era suposto fazer para os 100p? Fiz a forca bruta para os 60 pontos:

C(60%):

#include <iostream>
#include <vector>
#include <utility>
#define DIST(a, b) (((a.first-b.first) > 0 ? (a.first-b.first) : (b.first-a.first)) + ((a.second-b.second) > 0 ? (a.second-b.second) : (b.second-a.second)))
using namespace std;
typedef pair<int, int> crd;
int V, N, P;
vector <crd> mesas;
crd volun[3];
vector <int> pedidos;
int dis=1000000000;

void bfs(int num, int best) {
if (num==P) {
	dis = std::min(dis,best);
}
if (best>=dis) return;
crd lst;
for (int i=0; i<V; i++) {
	lst = volun[i];
	volun[i] = mesas[pedidos[num]];
	bfs(num+1, best + DIST(lst, volun[i]));
	volun[i] = lst;
}
return;
}

int main() {
crd tmp;
int tmpi;
cin >> V >> N;
for (int i=0; i<N; i++) {
	cin >> tmp.first >> tmp.second;
	mesas.push_back(tmp);
}
cin >> P;
for (int i=0; i<P; i++) {
	cin >> tmpi;
	tmpi--;
	pedidos.push_back(tmpi);
}
if (V==1) {
	dis = mesas[pedidos[0]].first-1 + mesas[pedidos[0]].second-1;
	for (int i=1; i<P; i++) {
		dis+= DIST(mesas[pedidos[i-1]], mesas[pedidos[i]]);
	}
	cout << dis << endl;
} else {
	volun[0].first=1; volun[0].second=1; volun[1].first=1; volun[1].second=1; volun[2].first=1; volun[2].first=1;
	bfs(0,0);
	cout << dis << endl;
}
}

Cumprimentos,

Xtrm0

[pedrosorio]

Problema C - 2012

Discussão, as vossas soluções, dúvidas e ajudas!

Podes colocar o enunciado nós tópicos para o pessoal que não participa saber o contexto?

[Warrior]

Podes colocar o enunciado nós tópicos para o pessoal que não participa saber o contexto?

Ups. Coloquei em todos menos neste!

EDIT: o forum está com um bug qualquer que não me deixa postar links :o

EDIT2: Já consegui, por algum motivo tive de retirar o http...

[Localhost]

neste fiz dfs, acho que dá 60 pontos se não me tiver escapado nada. Ainda nem pensei bem sobre o problema porque fiz o mesmo nas ultimas 2h de concurso xD

[xtrm0]

Eu tambem tinha feito com dfs, mas depois comecei a pensar em optimizar e mudei para bfs.

Basicamente a minha ideia era a seguinte:

Imaginemos que os tres voluntario A,B,C estao em tres posicoes e que houve um pedido para a mesa k.

Se algum dos voluntarios continuar a ser o mais proximo depois de se movimentar, de todas as mesas que era o mais proximo antes de se movimentar, entao esse movimento devera ser feito.

Só que depois nao consegui provar a afirmacao anterior, e por isso contentei-me com os 60p. Fiz bem, ou era essa a solucao?

[Localhost]

agora que pensei um pouco nisso, se repararmos existem muitos estados repetidos. Se estiveres num determinado pedido no dfs vais atender aos outros pedidos e isso já te dá basicamente a solução para o sub problema ou seja, isto é um problema básico de memoization (?) = dp...

alguém pode dizer se isto que disse está correto..? not sure.

xtrm: isso é greedy, não te resolve o problema porque um passo mal dado pode causar-te perda de tempo nos pedidos seguintes. not sure again 😉

[xtrm0]

Como e que construias a array de memoization? Se vais procurar o subproblema seguinte, entao as posicoes dos voluntarias ja sao diferentes(acho eu).

[Warrior]

agora que pensei um pouco nisso, se repararmos existem muitos estados repetidos. Se estiveres num determinado pedido no dfs vais atender aos outros pedidos e isso já te dá basicamente a solução para o sub problema ou seja, isto é um problema básico de memoization (?) = dp...

alguém pode dizer se isto que disse está correto..? not sure.

xtrm: isso é greedy, não te resolve o problema porque um passo mal dado pode causar-te perda de tempo nos pedidos seguintes. not sure again 😉

Isso está na direcção certa. Estou a gostar da vossa discussão pelo que não vou intervir mais 😉.

Não sei se tens razão em relação ao comentário à idea do xtrm porque não percebi bem o que ele quis dizer com "mais próximo antes de se movimentar", etc.

[xtrm0]

imagina que havia os concorrentes 1,2,...,10.

E os voluntarios A,B,C.

Se os concorrentes mais proximos do voluntario A fossem (1,2,3) e fosse pedido que alguem se movesse para o 4, entao haveria duas situacoes:

Se os concorrentes mais proximos de A depois de se movimentar contivessem (1,2,3), entao A movimentava-se para aí, caso contrário testava-se as 3 possibilidades. (quem diz A, diz B ou C).

Se houverem varios concorrentes a satisfazer a condicao da alinea anterior, entao move-se aquele com menor distancia.

Era isto?

[Warrior]

imagina que havia os concorrentes 1,2,...,10.

E os voluntarios A,B,C.

Se os concorrentes mais proximos do voluntario A fossem (1,2,3) e fosse pedido que alguem se movesse para o 4, entao haveria duas situacoes:

Se os concorrentes mais proximos de A depois de se movimentar contivessem (1,2,3), entao A movimentava-se para aí, caso contrário testava-se as 3 possibilidades. (quem diz A, diz B ou C).

Se houverem varios concorrentes a satisfazer a condicao da alinea anterior, entao move-se aquele com menor distancia.

Era isto?

Não, isso é uma heurística que não funciona para todos os casos.

[xtrm0]

Entao como e que é?

[Warrior]

agora que pensei um pouco nisso, se repararmos existem muitos estados repetidos.

Qual é o estado? Um exemplo de uma possível repetição?

[gangsterveggies]

Eu resolvi com DP bottom-up. Neste problema não podia haver nenhum "procedimento" (heurística como disse o Warrior 😄 ) concreto, simplesmente porque era possível ter qualquer situação, dependendo das posições dos pedidos. Era preciso "testar tudo". A ideia era saber como podíamos testar só o que "vale a pena". Solução bottom-up torna-se uma solução evidente (pelo menos foi o que eu vi...). É preciso perceber como definir estados e como é que se permuta de estado para um estado novo.

[Localhost]

Eu resolvi com DP bottom-up. Neste problema não podia haver nenhum "procedimento" (heurística como disse o Warrior 😄 ) concreto, simplesmente porque era possível ter qualquer situação, dependendo das posições dos pedidos. Era preciso "testar tudo". A ideia era saber como podíamos testar só o que "vale a pena". Solução bottom-up torna-se uma solução evidente (pelo menos foi o que eu vi...). É preciso perceber como definir estados e como é que se permuta de estado para um estado novo.

You're coding like a f*cking master ((: haha

[gangsterveggies]

You're coding like a f*cking master ((: haha

Só por curiosidade e não querendo ser off-topic, quais fizeste?

[Localhost]

A e C só.. não tenho treinado nada e pensei que ia correr pior mas sinceramente ainda me estou a sentir mais bem preparado do que o ano passado ou então os problemas eram mais fáceis porque consegui codar o C em 20 minutos numa aula de ap. inf. e consegui chegar pelo menos à ideia (ainda não sei se tá msm bem implementada do A) muito facilmente..

[gangsterveggies]

A e C só.. não tenho treinado nada e pensei que ia correr pior mas sinceramente ainda me estou a sentir mais bem preparado do que o ano passado ou então os problemas eram mais fáceis porque consegui codar o C em 20 minutos numa aula de ap. inf. e consegui chegar pelo menos à ideia (ainda não sei se tá msm bem implementada do A) muito facilmente..

Tens tempo ainda até à final. Eu do C tenho umas quantas histórias engraçadas que hei de te contar na final  😄

[djthyrax]

Assim de repente, olhando para o número de concorrentes, os voluntários estão no máximo em 31 posições (os 30 concorrentes e o ponto inicial). Depois de ler as posições todas dos concorrentes, para cada posição, fazia uma lista com as outras posições ordenadas pela distância a percorrer (menor primeiro), uma lista com a distância entre pares de posições. A partir daí, seguir a lista de pedidos e escolher qual somar a distância mínima de 1 dos voluntários e actualizar a sua posição. Este seria o meu raciocinio inicial.

[Warrior]

Assim de repente, olhando para o número de concorrentes, os voluntários estão no máximo em 31 posições (os 30 concorrentes e o ponto inicial). Depois de ler as posições todas dos concorrentes, para cada posição, fazia uma lista com as outras posições ordenadas pela distância a percorrer (menor primeiro), uma lista com a distância entre pares de posições. A partir daí, seguir a lista de pedidos e escolher qual somar a distância mínima de 1 dos voluntários e actualizar a sua posição. Este seria o meu raciocinio inicial.

Greedy não passa porque nem sempre é melhor mover o voluntário mais perto.

Um caso trivial que muitas abordagens greedy falham é imaginar que tens dois voluntários e três posições, A, B e C, em que A e B são próximas e C é longe delas. Inicialmente, os voluntários encontram-se em A e C.

Existe uma sequência de pedidos alternados entre A e B. A partir de um certo número de pedidos alternados, é melhor enviar o voluntário de C para lá para eles nunca mais se terem de mexer. Mas abaixo desse limite, então é melhor continuar a alternar o voluntário entre A e B, dada a distância para C ser grande.

Este exemplo ilustra bem a necessidade de ter sempre todos os pedidos em consideração na altura de mover um voluntário e que qualquer solução que tenha em consideração só as posições dos voluntários e o próximo pedido não conseguirá atingir um bom resultado.

Já agora, cheguei a implementar esta solução e a testar com casos aleatórios e muito raramente se obtém a solução correcta, nem é necessário elaborar casos muito específicos para ela falhar.