Jump to content
Warrior

TIUP 2011

Recommended Posts

pedrosorio

Eu estou a participar sozinho, just for fun, porque já estou no 5º ano (LoneCoder). Os Lutadores do Foo (pcaldeira, Tharis e Rafael Schimassek) também estão a participar pelo técnico novamente e espero que continuem nos próximos anos, a ver se levamos uma equipa às finais mundiais :cheesygrin:


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
mogers

Eu já me reformei disso, só talvez no codejam, for fun :)

espero que continuem nos próximos anos, a ver se levamos uma equipa às finais mundiais :)

Ficaria bastante contente :) No entanto, esse objectivo requer bastantes sacrifícios, vamos a ver se têm força de vontade suficiente :)

É uma seca ter ficado em 3º no swerc quando os 2 primeiros foram às mundiais  :cheesygrin:


"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.

Share this post


Link to post
Share on other sites
skiller10

Isto é só para universitários, certo?


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
mogers

Sim, mas se te apetecer treinar, também podes resolver os problemas pela net e participar contra os universitários. Só não contas para a classificação geral.


"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.

Share this post


Link to post
Share on other sites
skiller10

Quando vai ser? Se poderes deixar link para inscrição agradecia :cheesygrin:


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
Tharis

Eu e o Schima participámos ontem. O pcaldeira tinha teste durante a prova e não pôde aparecer. A participação de ontem só deu para ver que estamos muito enferrujados. Não lemos bem o problema B. Depois, submissões erradas por definirmos o array com 100 posições em vez de 100000. Anyway, foi bom voltar. :cheesygrin:

Share this post


Link to post
Share on other sites
skiller10

Não vou conseguir, devo estar em estágio nessa altura :s

De qualquer maneira vou tentar resolver os problemas, obrigado :cheesygrin:


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
mogers

ja agora, qual é o link para a prova de ontem? assumo k haja um pos-prova.. só espero que não tenha sido uma perda de tempo com problemas impossíveis como era habitual  😡


"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.

Share this post


Link to post
Share on other sites
pedrosorio

ja agora, qual é o link para a prova de ontem? assumo k haja um pos-prova.. só espero que não tenha sido uma perda de tempo com problemas impossíveis como era habitual  😡

http://mooshak.di.fc.ul.pt/~mooshak/


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
Warrior

Eu e o Schima participámos ontem. O pcaldeira tinha teste durante a prova e não pôde aparecer. A participação de ontem só deu para ver que estamos muito enferrujados. Não lemos bem o problema B. Depois, submissões erradas por definirmos o array com 100 posições em vez de 100000. Anyway, foi bom voltar. :cheesygrin:

Também tive 2 RTEs por causa disso..

Participei sozinho mais uma vez. Acho muito mau colocarem problemas repetidos como o B nas TIUPs, já para não falar no estilo do A e do E..

Por vezes dá vontade escrever o "Manifesto dos participantes em concursos de programação" a explicar porque motivo participamos e que género de problemas queremos ver.

Um problema com enunciado enorme a definir uma linguagem, sinceramente, tenho mais coisas para fazer do que parsing de strings.

Share this post


Link to post
Share on other sites
mogers

Obrigado Pedro :cheesygrin:

Um problema com enunciado enorme a definir uma linguagem, sinceramente, tenho mais coisas para fazer do que parsing de strings.

Se bem me lembro, nas últimas mundiais havia um problema desse género :x


"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.

Share this post


Link to post
Share on other sites
mogers

estive a resolver os problemas. eu até acho piada ao estilo do prob A, mas o E é absurdo...parece o enunciado do projecto pequeno de uma cadeira de programação lol.

é pena terem copiado problemas. eu gostei do D, embora também tenha a impressão que não é original


"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.

Share this post


Link to post
Share on other sites
fran.aubry

Eu fiz dois dos problemas da Tiup, o C e o D. O D não o vi antes em concursos mas Knapsack em sequências daquelas (super-increasing sequences) é usado para certos algoritmos de criptografia. Fiz o problema inspirado numa bolsa sobre teoria de números que estou a fazer. O C é que não é tão original assim pois existe um exercicio no Cormen a pedir aquilo. Mas baixei bastante os limites para ter um problema muito fácil.

Eu tentei evitar que metessem o E. Até porque mo deram para resolver e eu disse que não o faria. Penso que não tinha nada a ver com o objectivo do concurso. Foi criado um problema alternativo de ordenação topológica mas depois não o quiseram meter, não entendi porquê. Também achei mau repetirem o problema B, é mau pois favorece equipas que já o conheçam e não trás nada de novo.

Share this post


Link to post
Share on other sites
mogers

O C fez-me lembrar o problema A do swerc 2009. É diferente, embora tenha resolvido da mesma maneira.

Já agora, quais são os limites originais? eu fiz em algo semelhante a O(N * log 1000). Já agora, a resposta bate sempre um dos Y dos wells do input, né? Tenho ideia que é mas não tenho a certeza. Se for, penso que posso livrar-me do factor "log"

Não sei bem se já vi algum problema igual ao D, mas penso que já vi algo do género, daí que tenha feito logo sem pensar mt.

O pos-prova foi engraçado pa desenferrujar, ultimamente já não programo nem vejo código para além das dúvidas que colocam no forum.

edit: o problema de não ter bases sólidas de matemática/teoria dos números é muitas vezes assumir alguma intuição em coisas como o C e D.


"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.

Share this post


Link to post
Share on other sites
Warrior

Já tinha resolvido um problema igual ao C na UVA num estágio das ONI, a resposta é a mediana caso o número de pontos seja ímpar ou qualquer ponto entre os dois centrais caso seja par, logo sim, pode sempre ser igual ao X de um dos wells.

A única coisa que fiz foi ordenar e somar as diferenças ao X do ponto médio.

Consegues resolvê-lo sem ordenar?

Share this post


Link to post
Share on other sites
mogers

Yah, pesquisa ternária nos YY [0,1000] e depois o check das distâncias. Hmm pois, suspeitava que houvesse algo desse género, eu preferi fazer logo com algo que sabia do que pensar muito 👎

#define MAX 100100
int y[MAX], N, x;

int check(int yyy) {
int i, d = 0 ;
for (i = 0 ;  i< N ; i++)
	d += abs(y[i] - yyy);
return d;
}
int solve() {
int a , b  ,c1,c2, d1,d2;
a = 0 , b = 1000;
while ( a+2 < b ) {
	c1 = (a*2+b) / 3 , c2 = (a+b*2)/3;
	d1 = check(c1);
	d2 = check(c2);
	if ( d1 > d2 )		a = c1;
	else			b = c2;
}
return min(min(check(a), check(a+1)), check(a+2));
}
int main() {
int i ;
scanf("%d", &N);
for (i = 0 ; i < N ; i++)
	scanf("%d %d", &x, y+i);

printf("%d\n", solve());
return 0;
}


"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.

Share this post


Link to post
Share on other sites
fran.aubry

Nos limites originais só se sabe que os pontos são inteiros e que só uma solução O(n) passa. É possível cálcular o k-ésimo elemento de um array em O(n)  (ver Cormen - Order Statistics) e portanto em particular também a mediana (que era o que era pedido).

Pois a função da soma dos módulos é unimodal e portanto pesquisa ternária também funciona.

Share this post


Link to post
Share on other sites
MetaBrain

Eu fiz dois dos problemas da Tiup, o C e o D. O D não o vi antes em concursos mas Knapsack em sequências daquelas (super-increasing sequences) é usado para certos algoritmos de criptografia. Fiz o problema inspirado numa bolsa sobre teoria de números que estou a fazer. O C é que não é tão original assim pois existe um exercicio no Cormen a pedir aquilo. Mas baixei bastante os limites para ter um problema muito fácil.

O C e o D eram bastante interessantes :P

O C não nos lembramos da mediana, tentamos a média e depois uma pesquisa para fora da média até ter um valor máximo e ter a certeza que o mínimo que encontramos até ai é mesmo o mínimo (a função da distância total face deve fazer uma espécie de 'vale' na zona da média)

Para o D tentei Knapsack, mas não dava... Só no fim é que percebi porque estava a ter RTE, estava a fazer nextInt para ler a capacidade quando tinha de ser long... E depois vi que um array com o tamanho do capacidade invalida logo o algoritmo porque assim o array tinha de ser maior que 2^32-1, o que não daria.

Era só ordenar e fazer greedy naquilo afinal :cheesygrin:

Eu tentei evitar que metessem o E. Até porque mo deram para resolver e eu disse que não o faria. Penso que não tinha nada a ver com o objectivo do concurso. Foi criado um problema alternativo de ordenação topológica mas depois não o quiseram meter, não entendi porquê. Também achei mau repetirem o problema B, é mau pois favorece equipas que já o conheçam e não trás nada de novo.

O B tinha feito uma semana antes no UVa. Mal olhei para o enunciado vi que era igual, só mudaram o título... Foi basicamente escrever o Union-Find e passou logo em 3 minutos. Como já o tinha feito recentemente, foi basicamente copy-paste mental...  acho que é injusto para quem já conhecesse o problema.

Sim, o E era horroroso  :wallbash:

Em relação aos problemas que fizestes, vais manda-los para o UVa Online Judge? Era engraçado  :cheesygrin:

E os Javascript vão continuar a participar este ano?

Daniel dos Caparica Chaputa

Share this post


Link to post
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.