Jump to content

Discussão de Problemas do Google Code Jam 2009


zecapistolas

Recommended Posts

Eu bem que tentei participar, mas não consegui fazer nenhum  ? .... Foi a minha primeira participação numa "olimpíada de informática".... Já tive a ver a resolução do Problema C de dois ou três indivíduos, e ainda não percebi muito bem, como chegaram à solução....

Fica aqui o código que estou a analisar (algumas cenas já alteradas por mim):

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

#include <string>
using std::string;

#include <sstream>
using std::stringstream;

/**
* Transforma uma String num valor Inteiro
*/
unsigned int string_to_int(const string& s)
{	
    stringstream ss(s);
    int i = 0;
    ss >> i;
    return i;
}

string target = "welcome to code jam";
int cnt[1000][100];

int main (int argc, char *argv[]) 
{    
    // Le o numero de frases que se irão seguir
    string s;
    getline(cin, s);
    unsigned int N = string_to_int(s);

for (unsigned int i = 0; i < N; i++)
{
	cnt[0][0] = 1;		
	// Le o resto das frases sequencialmente
	string str;
	getline(cin, str);

	for (unsigned int j = 1; j < str.size()+1; j++) {
	    for (unsigned int t = 0; t < target.size()+1; t++)
	    {
		    cnt[j][t] = cnt[j-1][t];
		    if( (t>0) && (str[j-1] == target[t-1]) ) {
			    cnt[j][t] += cnt[j-1][t-1];
			    cnt[j][t] %= 10000;
		    }
	    }
	}
	cout << "Case #" << i+1 << ": ";
	printf("%04d\n", cnt[str.size()][target.size()]);
}
}

O que me come o cerebro é os dois for's encadeados, ainda não percebi muito bem como é que com aquilo se consegue chegar à solução....  ?

PS: Alguém que queira deixar aqui algumas dicas, para os novatos (como eu), faça o favor....

cumps  😉

Link to comment
Share on other sites

O Warrior pediu para que a discussão dos problemas fosse feita na secção de Algoritmia.

Essa solução usa programação dinâmica. Durante a prova, eu fiz de forma parecida mas menos eficiente (mas corre em ~0.15 secs). Vê o contest analysis da google. Com a explicação que eles deram mais esse código, deves conseguir perceber.

Se tiveres dúvidas, pergunta 😉

edit: o contest analysis pode ser acedido ao entrar no practice da qualificação e abaixo da selecção dos problemas tem uma opção "Contest Analysis". Acho que a explicação que lá tem é boa, por isso, penso que não vale a pena escrever outra 😛

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

Eu gosto tanto do meu código para o A... eh eh eh... eu sei que é brutalmente lento... mas tendo em conta o tempo que demorou a programar, eu diria que valeu bem a pena. 😉

require 'set'

array = STDIN.gets.split
L = array[0].to_i
D = array[1].to_i
N = array[2].to_i
caso = 1
set = Set.new

D.times do 
  set << STDIN.gets.split("\n")[0]
end

N.times do 
  pattern = STDIN.gets.split("\n")[0]
  pattern.gsub!("(", "[")
  pattern.gsub!(")", "]")
  results = 0
  
  set.each do |word|
    if word.match(/#{pattern}/).to_s == word
      results +=1
    end
  end
  
  puts "Case #" + caso.to_s + ": " + results.to_s
  caso +=1
end

Fiz exactamente o que disseram na analysis do problema como alternativa, transformar ( em [ e usar as built-in funções de match de regular expressions.

Link to comment
Share on other sites

Btw, A solução para o C da Contest Analysis está bem explicada e tal, mas ontem o pcaldeira estava a falar-me de soluções quadráticas e lineares. Suponho que ele estava era a referir-se à memória não?, pois a solução que o google propõe e que eu acabei de implementar é quadrática no tempo...

Ou existe solução linear no tempo para o C?

Link to comment
Share on other sites

Btw, A solução para o C da Contest Analysis está bem explicada e tal, mas ontem o pcaldeira estava a falar-me de soluções quadráticas e lineares. Suponho que ele estava era a referir-se à memória não?, pois a solução que o google propõe e que eu acabei de implementar é quadrática no tempo...

Ou existe solução linear no tempo para o C?

Como o pedrosorio disse, a string que estás a procurar é sempre a mesma, logo a solução é n*19, ou seja, linear. A solução quadrática de que eu falei é quadrática no tamanho do texto.

Link to comment
Share on other sites

Como o pedrosorio disse, a string que estás a procurar é sempre a mesma, logo a solução é n*19, ou seja, linear. A solução quadrática de que eu falei é quadrática no tamanho do texto.

Oh, que parvoíce, ainda ontem tinha chegado a essa conclusão... sim tens razão...

De qualquer modo, quanto à memória, depois de ver a solução do google implementei em O(n*m) também, mas acho que já vi a usarem menos memória... O(n) pareceu-me...

Link to comment
Share on other sites

Oh, que parvoíce, ainda ontem tinha chegado a essa conclusão... sim tens razão...

De qualquer modo, quanto à memória, depois de ver a solução do google implementei em O(n*m) também, mas acho que já vi a usarem menos memória... O(n) pareceu-me...

Novamente, m é constante, portanto n*m=19*n, que é linear.

Mas podes fazer com memória constante, se leres o texto char a char. A ideia é que ao processares um novo char que coincide com o char na posição i da string welcome, não precisas de saber onde estão, no texto, os chars da posição i-1 da string welcome, só precisas de saber quantos são. Podes, então, manter apenas um array count[20] em que count[i ] te diz quantas formas de fazer a substring (0,i) existem até agora, e usas só essa memória independentemente do tamanho do texto.

Link to comment
Share on other sites

Foi exactamente essa a minha solução, posso deixar aqui o meu código.

#include <iostream>
#include <string>
#include <cstdio>

#define MAX_P 20
#define MOD 10000
using namespace std;

string p = "welcome to code jam";

int v[MAX_P];

int main() {
  int n;
  string str;
  
  scanf("%d\n", &n); 
  
  for (int t=1;t<=n;t++) {
    getline(cin, str);
    memset(v, 0, sizeof(v));

    for (size_t i=0;i<str.length();i++)
      for (size_t j=0;j<p.length();j++)
if (str[i]==p[j]) {
  if (j==0)
    v[0]=(v[0]+1)%MOD;
  else
    v[j]=(v[j]+v[j-1])%MOD;
}
    printf("Case #%d: %04d\n", t, v[p.length()-1]);
  }
  return 0;
}
Link to comment
Share on other sites

Estou com duas dúvidas:

  • Uma coisa que não percebi no Problema C, o porque do módulo por 10000?
  • Outra coisa, todas as soluções que tirei, nenhuma lê o ficheiro que o Google disponibiliza para fazer o teste e depois reportar o output, apenas lêem uma linha e tem que ser colocada na consola à páta.... Porque?!

cumps  🙂

Link to comment
Share on other sites

  • Outra coisa, todas as soluções que tirei, nenhuma lê o ficheiro que o Google disponibiliza para fazer o teste e depois reportar o output, apenas lêem uma linha e tem que ser colocada na consola à páta.... Porque?!

Fica muito mais simples de testar o programa: na linha de comandos podes definir um ficheiro como a entrada do standard input e outro ficheiro que vai conter o que imprimes para o standard output. Executa

nome_executavel < ficheiro_input.txt > ficheiro_output.txt

Assim, podes testar o programa com multiplos ficheiros sem teres de o recompilar ou mudar o conteúdo desses ficheiros.

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

Fica muito mais simples de testar o programa: na linha de comandos podes definir um ficheiro como a entrada do standard input e outro ficheiro que vai conter o que imprimes para o standard output.

Não sabia, obrigado pela explicação.... Foi como disse no inicio da minha participação neste tópico, ainda estou muito verdinho nisto das olimpíadas de programação....  ?

cumps  👍

Link to comment
Share on other sites

Ronda 1C:

Problema A - O menor número tem como base o número de símbolos diferentes, excepto se houver apenas 1 símbolo (nesse caso a base é 2). Como não começa em 0, o primeiro símbolo vale 1, o segundo vale 0, o terceiro vale 2 e por aí fora.

Problema B - Temos que minimizar a distância do centro de massa à origem, em t. A distância à origem é dada por:

sqrt(Xc² + Yc² + Zc²)    (eq1)

maximizar isto ou Xc² + Yc² + Zc² é a mesma coisa.

Por sua vez, Xc = somatório(Xi(t)) / N = somatório(Xi + Vxi * t) / N = (Somatório(Xi) + t * Somatório(Vxi)) / N

Denotando os somatórios (que podem ser calculados à partida para cada caso) por X e Vx temos:

Xc = (X + Vx * t) / N, fórmulas idênticas são encontradas para Yc e Zc

Para minimizar f(t) = Xc² + Yc² + Zc² temos que achar um zero da derivada em ordem a t, e garantir que é mínimo.

d Xc² / dt = 2 * (X + Vx * t) * (Vx) / N² = (2 / N²)  * ( X * Vx + t * Vx²)

f ' (t) = (2/N²) * (X * Vx + t * Vx² + Y * Vy + t * Vy² + Z * Vz + t * Vz²) = 0

t  = - (X*Vx + Y*Vy + Z*Vz) / (Vx² + Vy² + Vz²)

Visto que existe apenas um zero e pelo enunciado do problema, tem que existir um mínimo da distância então temos 2 casos possíveis:

- t>0, pode ser um máximo ou mínimo local, usar eq1 para calcular a distância (com o t calculado e em t=0), o que for menor é a solução

- t<0, se fosse um máximo local, então a distância era decrescente a partir daí, e o mínimo era +infinito (impossível) logo o mínimo para t>=0 é em t=0.

Falhei o large input porque acho que me esqueci de verificar para t>0 se era um mínimo =/  ---> Fui verificar agora, foi mesmo isso, duh

Problema C: Função recursiva à bruta (para o small), provavelmente é programação dinâmica, senhor pcaldeira, explique a solução sff =P

Não respondo a dúvidas por mensagem.

Link to comment
Share on other sites

Posso tentar explicar a DP para o C, mas pode haver forma mais simples porque da maneira que implementei tinha muitos corner cases..

Tentando exemplificar, se tivermos 10 presos, o truque é reparar que soltar os presos 4 e 5 ou o 5 e 4, temos na mesma que achar a solução mínima para os presos [1, 3] e [6, 10] independentemente da ordem entre o 4 e o 5.

Assim, podemos manter uma matriz m[a][ b ] = ao número minimo de moedas para soltar os presos de "a" a "b".

A nossa resposta é obviamente m[0][q-1] (q = numero de presos a soltar), falta-nos portanto construir a matriz.

Os casos bases são simples, m[a][a] será igual ao custo de soltar o preso "a", assumindo que os outros presos estão soltos, assim m[a][a] será igual a v[a+1]-v[a-1]-2, sendo v[p] a cela do preso p.

Temos que ter cuidado com os cantos.

Para construir o resto da matriz, m[ i ][ j ] é o minimo entre todos os p, tal que v[j]-v[i-1]-2 + m[ i ][p-1] + m[p+1][ j ].

Em termos teóricos é relativamente simples, temos que tentar muito cuidado ao implementar por causa dos indices e por causa dos dois extremos.

Julgo que deve haver uma maneira de os ignorar adicionando umas barreiras em torno de v e de m, mas não pensei nisso durante a prova..

Não sei se foi esta a solução do pcaldeira, mas eu resolvi assim.

Link to comment
Share on other sites

Eu estou a resolver agora os problemas da 1C. Para o B era preciso uma solução tão complicada?

Eu já não tenho fisica há muito tempo, mas eu creio que a velocidade do centro de massa era igual à média das velocidades. Logo  (x,y,z) = (x0,y0,z0) + v_cm * t

Como aquilo é uma recta, nós só queremos o ponto da recta mais próximo de 0,0 (com t não negativo).

Vou experimentar implementar.

edit: nunca fiz isto a 3 dimensões... não sei se será assim tão simples 🙂

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

Fiz como o Warrior disse, mas evitei os cantos pondo um preso na posição 0 e outro na posição num_prisioneiros+1. O código ficou pequeno:

#include <cstdio>
#include <climits>
#include <algorithm>
#define MAX 105

using namespace std;

int ncases, npris, ncells, cells[MAX], memo[MAX][MAX];

int gocomp(int a, int b)
{
if(memo[a][b]) return memo[a][b];
if(a>b) return 0;

int mincost=INT_MAX;
for(int i=a; i<=b; i++)
	mincost=min(mincost, cells[b+1]-cells[a-1]-2 + gocomp(a, i-1) + gocomp(i+1, b));

memo[a][b]=mincost;
return mincost;
}

int main()
{
scanf("%d", &ncases);
for(int i=0; i<ncases; i++)
{
	memset(memo, 0, sizeof(memo));
	scanf("%d %d", &npris, &ncells);
	cells[0]=0;
	cells[ncells+1]=npris+1;
	for(int j=0; j<ncells; j++)
		scanf("%d", &cells[j+1]);

	printf("Case #%d: %d\n", i+1, gocomp(1, ncells));
}
return 0;
}

O A era fácil, o B tentei derivar, mas não tinha papel à mão e não me dei bem com o Grapher... E fiz a prova toda num editor foleirote, à beira da janela para conseguir net dos vizinhos :x Tenho que me habituar a isto e arranjar umas ferramentas melhores para a próxima ronda.

Link to comment
Share on other sites

Eu estou a resolver agora os problemas da 1C. Para o B era preciso uma solução tão complicada?

Eu já não tenho fisica há muito tempo, mas eu creio que a velocidade do centro de massa era igual à média das velocidades. Logo  (x,y,z) = (x0,y0,z0) + v_cm * t

Como aquilo é uma recta, nós só queremos o ponto da recta mais próximo de 0,0 (com t não negativo).

Vou experimentar implementar.

Usando o facto de que a velocidade do centro de massa é a média das velocidades obténs isso (que é equivalente às minhas "brincadeiras" com os somatórios). Para achar o ponto mais próximo de (0,0,0) não conheço nenhuma técnica que não envolva achar a derivada da distância.

Não respondo a dúvidas por mensagem.

Link to comment
Share on other sites

Eu sabia fazer isso a 2d, mas a 3d não sabia se era só generalizar a ideia. Acabei por ir a http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html e verifiquei que é só uma generalização de 2d. Aqui fica a solução:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;

#define CP	const Point

struct Point {
double x , y , z ;
Point( double xx = 0 , double yy = 0, double zz = 0 ) { x = xx , y = yy, z = zz; }

Point operator + ( CP & a )	const	{ return Point( x+a.x , y+a.y, z+a.z ); }
Point operator - ( CP & a )	const	{ return Point( x-a.x , y-a.y, z-a.z ); }
Point operator * ( double n )	const	{ return Point( x * n , y * n, z * n ); }
Point operator / ( double n )	const	{ return Point( x / n , y / n, z / n ); }	
double operator * ( CP & a )	const	{ return x * a.x + y * a.y + z * a.z; 	 } 					// dot
Point operator ^ ( CP & a )	const	{ return Point( y*a.z - a.y*z , z*a.x - a.z*x , x*a.y - a.x*y ); 	 } 	// cross
};

double distancia( CP & a , CP & b ) 	{ return sqrt( (b-a)*(b-a) );		}	// distancia entre dois pontos
double distancia(CP & a) 		{ return sqrt( a*a ); 			}	// norma de vector
double cross( CP & A, CP &B, CP &C)	{ return  distancia((C-A) ^ (C-B));	}	// produto vectorial de AC com BC

// Distancia de AB a C. Se isSegment é true, AB é um segmento de recta
double linePointDist( CP & A, CP & B , CP & C, bool isSegment = false){
if(isSegment){						// verifica se C pertence a AB.
	double dotp = (C-A)*(A-B);			// senao pertencer, retorna distancia 		
	if(dotp > 0) return distancia( A , C );
	dotp = (C-B)*(B-A);
	if(dotp > 0) return distancia( B , C );		// a um dos extremos	
}
return fabs( cross( A , B , C ) / distancia( B , A ) );
}

void solve() {
int N, i , x,y,z;
Point X, V, origem;
cin >> N;
for (i = 0 ; i < N ; i++) {
	cin >> x >> y >> z;
	X = X + Point(x,y,z);
	cin >> x >> y >> z;
	V = V + Point(x,y,z);
}
X = X / N;
V = V / N;
Point X2 = X + V;

double norma = distancia(X2-X) ;	
double t = norma > 0 ? - ( (X-origem) * (X2-X) / (norma*norma)) : 0;
double d = distancia(X);	
if ( t <= 0. )
	t = 0;
else
	d = min( d , linePointDist( X , X2 , origem, false) );
printf("%.8f %.8f\n", d , t);
}

int main() {
int C , nc;	
scanf("%d\n", &C);
for ( nc = 1 ; nc <= C ; nc++) {
	cout << "Case #" << nc << ": ";
	solve();
}	
return 0;
}

Pus a minha solução do A em http://codepad.org/i3cOUFoA Vou ver o C agora.

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.