• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

zecapistolas

Discussão de Problemas do Google Code Jam 2009

32 mensagens neste tópico

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....  :hmm:

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

cumps  ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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 :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A solução que eles propõem é O(m*n) sendo n o tamanho do texto e m o tamanho da string que procuras, neste caso m=19, a solução é linear no tamanho do texto.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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  :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

  • Uma coisa que não percebi no Problema C, o porque do módulo por 10000?

Está no enunciado do problema, já que o número pode ser muito grande, para não criar mais complicações pedem-te apenas os 4 últimos algarismos.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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  :thumbsup:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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 :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros 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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu tentei fazer B durante a prova como o pedrosorio disse mas deu-me WA não faço ideia porquê..

Se alguém descobrir agradeço.

Tentei algumas variações disto, o que ali está no cout é um cálculo de f(t), mas também tentei usando simplesmente o valor de t e a expressão da recta..

#include <iostream>
#include <cmath>

#define EPS 10e-9

using namespace std;

double module(double x, double y, double z) {
  return sqrt(x*x+y*y+z*z);
}

int main() {
  int t;
  int n;
  double px=0, py=0, pz=0, vx=0, vy=0, vz=0;
  double tx, ty, tz;
  cin >> t;
  for (int k=1;k<=t;k++) {
    cin >> n;
    px=0, py=0, pz=0, vx=0, vy=0, vz=0;
    for (int i=0;i<n;i++) {
      cin >> tx >> ty >> tz;
      px+=tx; py+=ty; pz+=tz;
      cin >> tx >> ty >> tz;
      vx+=tx; vy+=ty; vz+=tz;
    }    
    
    //cout << px << " " << py << " " << pz << " " << vx << " " << vy << " " << vz << endl;

    px/=n; py/=n; pz/=n;
    //vx/=n; vy/=n; vz/=n;

    //cout << px << " " << py << " " << pz << " " << vx << " " << vy << " " << vz << endl;

    if (vx<=EPS && vy<=EPS && vz<=EPS)
      cout << "Case #" << k << ": " << module(px, py, pz) << " 0.0" << endl;
    else {
      double fsq = vx*vx+vy*vy+vz*vz;
      double fl = 2*px*vx+2*py*vy+2*pz*vz;
      double fc = px*px+py*py+pz*pz;
      double td = 2*fsq;
      double cd = fl;
      double t=-cd/td;
      
      //cout << fsq << " " << fl << " " << td << " " << cd << " " << t << endl;
      
      if (t<=0)
cout << "Case #" << k << ": " << module(px, py, pz) << " 0.0" << endl;
      else
cout << "Case #" << k << ": " << sqrt((fsq*t*t+fl*t+fc)<EPS?0:(fsq*t*t+fl*t+fc)) << " " << t << endl;

    }
  }
  return 0;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

px/=n; py/=n; pz/=n;

Para que t=-cd/td, os px têm que ser os somatórios das posições e não as coordenadas do centro de massa.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Os somatórios das posições?

P representa o centro de massa e V a velocidade, não percebo como é que não é suposto dividir, sem dividir não garantes que o P pertença à recta.

A minha ideia era simplesmente encontrar o centro de massa em t=0 e o vector velocidade, e depois encontrar a distância à origem.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Os somatórios das posições?

P representa o centro de massa e V a velocidade, não percebo como é que não é suposto dividir, sem dividir não garantes que o P pertença à recta.

A minha ideia era simplesmente encontrar o centro de massa em t=0 e o vector velocidade, e depois encontrar a distância à origem.

Eu percebi que tinhas feito como eu disse (derivada em ordem a t, etc.) e a forma como calculas o t estaria correcto se os P fossem as coordenadas do centro de massa * N.

Claro que para calcular a distância ao centro de massa como estás a fazer terias que dividir por N depois.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora