vbmaster

Acabei de mandar a seguinte mensagem ao professor do IST que está encarregue das TIUPs: Ao que ele respondeu:

Esquece, vou para os os balneários mais cedo, os primeiros 1000 já resolveram 1 completo e outro small, e eu só resolvi o A completo. Estive 1 hora a olhar para B mas nem consigo perceber as soluções dadas por exemplo para o 1 1000 nem para o 50 700. Fica novamente para o ano. 😄

Também ainda não foi desta que passei e duvido que passe amanhã. Quanto a hoje já era de esperar que resolver um completo não bastasse (costuma ser assim todos os anos, no 1A passa-se com 1 dependendo do tempo, no 1B só se passa com 2). Resolvi o primeiro completo mas podia ter demorado menos. Quis fazer em Ruby e o problema disso foi que perdi muito tempo a ver documentação. Já o C tive 1 hora para o fazer e quando acabou o concurso estava praticamente todo feito mas só resolvia alguns inputs. Aliás, não resolveu o small input porque fiquei sem perceber bem o que se queria numa certa parte... Eles queriam que testássemos todos os subsets possíveis do set {2...n} e retornassemos o numero de primos puros desse set em relação a n, mas o N neste caso é o n do conjunto global, ou é o n do subset? Por exemplo, se eles nos dessem o valor 5, isso dava um set global de {2,3,4,5}, podiamos escolher o subset {2,4} e testar se 5 era puro dentro desse subset, era isso?

Btw, o site da stats foi actualizado com estatísticas da qualificação: http://www.go-hero.net/jam/10/regions/Portugal

Pois, eu devia fazer como tu nesse C... fazer a primeira solução que me vinha a cabeça e que dá pontos... conseguia fazer isso para o A e se nao fosse parvo para o C também (já estive a ver a tua solução recursiva nesse último com memoization). Nesse problema estava à procura de algo mais directo enquanto podia ter pontos com a primeira solução que me passou pela cabeça... A ver como corre esta tarde. Estou a contar com uma competição mais lixada...

4 minutes to go... Se os problemas forem chatos vou mas é dormir :x...

Vi há uns dias o Notebook que a ex-equipa do IST HammerHappy usava para os concursos e sobre o problema de box stacking tem lá depois a seguinte nota: http://img4.imageshack.us/img4/801/screenshotip.png Entretanto, boa sorte para quem participar hoje na TIUP, já sei que o Warrior vai ter teste, por isso não vai haver FEUP mas espero contar com os Lutadores do Foo. 😛

E pronto, foi uma boa primeira qualificação. Ontem à noite era véspera de teste de Modelação mas não resisti a ir lá ler os problems e fiquei logo agarrado ao A e não saí de lá enquanto não o resolvi. Só que na altura o código que tinha feito ainda tinha demorado um bocado no Large, mas a coisa dava para transformar em O(1) e foi o que fiz já hoje (mas não resubmeti claro). O C estiver a ver esta tarde, lá fiz um código que explorava o facto de a dada altura haver um padrão na fila que se repetiria ad eternum. Fiz o código fixe que passou o small, no entanto para o large só depois de ter sacado o input é que me lembrei dos long longs. Ainda alterei a tempo do final da contagem temporal, mas depois meti o exemplo a correr assim: ./a.out in > out Omg, e lá estava eu á espera que aquilo printasse, quando afinal o large era resolvido em 0.02 segs pelo meu código. Enfim, mas passei, nice... 👍 Dentro de duas semanas estou cá, e desta vez não me apanham, vou logo à de sexta... P.S.: sou o miguelpais lá, podem adicionar (eu tenho uns 12 users do p@p lá só que acho que as relações não são recíprocas)

Btw, o problema E não foi tailor made porque já existem mais equipas com matemáticos aqui no IST (os não sei quê do Martelo), que também resolveram esse... ---- Sim, eu sei que a TIUP tem limites leves, nem me estava a vangloriar do desenrascanso do N^3... São estas cenas que provam na MIUP quem é que percebe mesmo do assunto.

Não sei se é pelo facto de agora suportarem cada vez mais linguagens alternativas, o que pode levar a que tenham um time limit fixo independente da linguagem, mas a solução O(N^3) passou nas calmas e foi feita por nós em uns 10 minutos ou menos. Btw, a nossa equipa (Mess) teve uma alteração, saíu o quickfire e entrou o triton, matenho-me eu e o joao guerreiro. 👍 P.S.: qual era o nome da vossa equipa?

Entendeste muito bem... aprendeste alguma coisa sobre como forjar os pacotes usando o programa que faz isso por ti? Não me interpretes mal, acho os teus posts porreiros, mas neste caso em particular não sei se reparas que estás apenas a disponibilizar a solução e não o conhecimento.

E o que é que aprendeste sobre isso e sobre o ARP usando o programa?

Complexidade alta é a exponencial... mesmo que tenhas algo O(n^100) não é considerado complexidade alta embora possa demorar bastante tempo a computar... Mas certo, descobrir que a factorização é P prova que todos os outros problemas são P (se bem que há uma carrada de categorias NP e pode não significar exactamente isto), mas o algoritmo para encontrar as soluções para os outros problemas ainda teria de ser produzido e provavelmente esses algoritmos não teriam nada a ver com o da factorização, logo não ajudaria nada o facto de se ter encontrado a factorização em P.

Não, a culpa é dos canais de televisão, jornais e mídia em geral... Sempre que vêm estas pandemias mais vale nem abrir a televisão, é-se mais feliz.

Isso é tudo muito giro... é preciso entender-se muita coisa e não sei que mais, mas no fundo pegas no programa e (possívelmente) está feito. Mais interessante que isso é saber como é que as caches do ARP são manipuladas... mas suponho que o caim não seja open source.