tag:blogger.com,1999:blog-26970597894814436052024-02-19T08:09:40.067-03:00Diário de AprendizadoUnknownnoreply@blogger.comBlogger147125tag:blogger.com,1999:blog-2697059789481443605.post-36742053008689387972014-03-17T15:56:00.001-03:002014-03-17T15:56:16.570-03:00Blog Novo!Resolvi mudar o meu blog, levá-lo um pouco mais a sério, e dispor de um pouco mais de recursos.<br />
<br />
O novo endereço do meu blog é este:<br />
<a href="http://crbonilha.com/">http://crbonilha.com</a><br />
<br />
Layout novo, host novo e até domínio novo!<br />
<br />
Os posts que eu julgava mais interessantes foram e alguns ainda serão transferidos para lá.<br />
Não farei mais nenhum post aqui, apenas lá.<br />
<br />
Considerem este blog aposentado.<br />
Não vou excluí-lo, porém, pois há bastante conteúdo bacana aqui ainda.<br />
<br />
Vejo vocês lá.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2697059789481443605.post-11550626954554648152014-02-28T00:18:00.000-03:002014-09-26T21:38:21.249-03:00Contest Delta - Editorial (Continuação)No contest Delta, três exercícios se destacaram pela dificuldade, e eu resolvi fazer um post separado para falar sobre eles, pois as suas soluções são um pouco mais complexas. A primeira parte do editorial pode ser encontrada aqui: <a href="http://crbonilha.blogspot.com.br/2014/02/contest-delta-editorial.html" target="_blank">[link]</a>.<br />
<br />
<b>[An English version can be found here:]</b><br />
<a href="http://crbonilha.hostei.com/contest-delta-editorial-pt2/?lang=en" target="_blank">http://crbonilha.hostei.com/contest-delta-editorial-pt2/?lang=en</a><br />
<br />
Os exercícios em questão eram:<br />
Fibonacci de Novo! <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1531" target="_blank">[link]</a>;<br />
Contagem de Substrings <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1530" target="_blank">[link]</a>;<br />
Cordas Emaranhadas <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1528" target="_blank">[link]</a>;<br />
<br />
Todos foram escritos pela mesma pessoa, Gabriel Dalalio, e boa parte do que eu vou disponibilizar aqui foi ele quem me passou, para que eu fizesse esse editorial.<br />
<br />
Clique no link abaixo para ver o editorial.<br />
<br />
<a name='more'></a><br />
<br />
<b><span style="font-size: large;">Fibonacci de Novo!</span></b> <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1531" target="_blank">[link]</a><br />
Com um nome atrativo, esse exercício chamou a atenção de muitos maratonistas na hora do contest, que se frustraram ao perceber que a solução era mais complexa do que esperavam.<br />
<br />
Uma abordagem ingênua seria resolver o exercício pela fórmula proposta: Fib( Fib(N) )%M, resultando em Overflow devido ao valor elevado de Fib(N), sem falar do tempo posterior necessário para calcular Fib( Fib(N) ).<br />
<br />
Uma observação que pode ser feita em relação aos número de Fibonacci módulo M, é que eles entram em uma espécie de ciclo, conhecido como Pisano Period <a href="http://en.wikipedia.org/wiki/Pisano_period">[link]</a>.<br />
Por exemplo, seja M = 4, a sequência de Fibonacci comum, e em módulo M, ficam assim:<br />
<br />
<span style="font-family: Courier New, Courier, monospace;"> 0 1 2 3 4 5 6 7 8 9 10 11 12</span><br />
<span style="font-family: Courier New, Courier, monospace;">Fibonacci Comum: 0 1 1 2 3 5 8 13 21 34 55 89 144</span><br />
<span style="font-family: Courier New, Courier, monospace;">Fibonacci Mód 4: 0 1 1 2 3 1 0 1 1 2 3 1 0</span><br />
<span style="font-family: Courier New, Courier, monospace;">Pisano Period : [________________][_____________________][...</span><br />
<br />
O ciclo varia de acordo com o valor M. No caso acima, o ciclo tem tamanho 6.<br />
<br />
Isso significa que, seja C o tamanho do ciclo, temos:<br />
Fib(K)%M = Fib(K%C)%M<br />
<br />
Para se descobrir o tamanho do ciclo, a forma iterativa é suficiente. Basta gerar os valores de fibonacci até que se encontre um valor X > 1 onde Fib(X)%M = Fib(X+1)%M = 1, e então C = X-1.<br />
No exemplo acima, X = 7, e C = 6.<br />
<br />
Com isso, conseguimos reduzir nossa fórmula inicial para: Fib( Fib(N)%C )%M.<br />
<br />
Para finalizar, basta calcular os dois valores de Fibonacci. Aqui o método iterativo e recursivo são muito lentos, precisamos de um método mais rápido. Há dois métodos que custam tempo O(lg N):<br />
Fast Doubling: <a href="http://nayuki.eigenstate.org/page/fast-fibonacci-algorithms" target="_blank">[link]</a>, <a href="http://vinayakgarg.wordpress.com/2012/11/07/fastest-way-to-compute-fibonacci-number/" target="_blank">[link]</a><br />
Exponenciação de Matriz: <a href="http://marathoncode.blogspot.com.br/2012/09/relacao-de-recorrencia-com.html" target="_blank">[link]</a><br />
<br />
<b><span style="font-size: large;">Quantas Substrings?</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1530" target="_blank">[link]</a><br />
<div>
Este exercício requer uma maneira mais sofisticada de se contar o número de substrings sendo formadas. O número total de substrings dentro de uma string S de tamanho N é igual a N*(N+1)/2, porém muitas delas aparecem mais de uma vez.<br />
<br />
Além disso, o exercício pede que o número de strings diferentes seja contado diversas vezes, e não só ao final com uma string S fixa. Precisamos então de uma estrutura que nos auxilie no processo.<br />
<br />
Há três estruturas candidatas:<br />
Árvore de Sufixos; Vetor de Sufixos; e Autômato de Sufixos.<br />
<br />
Com um pouco de experiência com alguma delas, é possível descobrir o número de substrings diferentes em tempo linear.<br />
<br />
O Gabriel Dalalio disponibilizou seu Trabalho de Conclusão de Curso, que fala justamente sobre Strings, e faz menção a este exercício em questão. O material está muito bom, segue o link:<br />
<a href="https://www.dropbox.com/s/yeg5eo6fthwla0h/TC103_2013.pdf?dl=0">https://www.dropbox.com/s/yeg5eo6fthwla0h/TC103_2013.pdf?dl=0</a></div>
<br />
<b><span style="font-size: large;">Cordas Emaranhas</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1528" target="_blank">[link]</a><br />
O enunciado pede: a sequência é alternante ou não?<br />
<br />
O problema é que há sequências que são "alternantes disfarçadas", tal como no próprio exemplo dado no enunciado, onde <span style="font-family: Courier New, Courier, monospace;">"+-++*+"</span>, que não é alternante, tem um resultado idêntico à sequência <span style="font-family: Courier New, Courier, monospace;">"+*-*"</span>, que é alternante.<br />
<br />
Identificar tais "alternantes disfarçadas" requer muita observação e identificação de alguns padrões. Vou citar aqui 4 padrões que, após aplicadas na sequência, revelam de fato se ela é alternante ou não. Recomendo que peguem um pedaço de papel e uma caneta para que possam compreender melhor todos os padrões citados a seguir:<br />
<br />
1 - A subsequência <span style="font-family: Courier New, Courier, monospace;">"+-"</span> não afeta o resultado de forma alguma. Note que as crianças 1 e 2 trocam de lugar duas vezes, e a posição das cordas volta ao estado que estava antes dessa subsequência. Note que a subsequência <span style="font-family: Courier New, Courier, monospace;">"-+"</span> é semelhante.<br />
Quando essas subsequências aparecem, simplesmente remova tais movimentos.<br />
Exemplo: <span style="font-family: Courier New, Courier, monospace;">"++-" -> "+"</span><br />
<br />
2 - A subsequência <span style="font-family: Courier New, Courier, monospace;">"**"</span> não afeta o resultado de forma alguma. Note que as crianças girarão no sentido horário duas vezes, porém a posição das cordas não muda.<br />
Quando essa subsequência aparecer, simplemente remova tais movimentos.<br />
Exemplo:<span style="font-family: Courier New, Courier, monospace;"> "+**++" -> "+++"</span><br />
<br />
3 - Se o primeiro movimento da sequência completa é um <span style="font-family: Courier New, Courier, monospace;">"*"</span>, então todos os movimentos de troca não afetarão o resultado de forma alguma, até que outro movimento <span style="font-family: Courier New, Courier, monospace;">"*"</span> seja realizado. Note que o movimento <span style="font-family: Courier New, Courier, monospace;">"*"</span> gira as crianças de tal modo que, quando elas trocam de lugar, a posição das cordas não se altera.<br />
Quando a sequência iniciar com <span style="font-family: Courier New, Courier, monospace;">"*"</span>, remova todos os movimentos da primeira posição até a segunda aparição do <span style="font-family: Courier New, Courier, monospace;">"*"</span>, inclusive.<br />
Exemplo: <span style="font-family: Courier New, Courier, monospace;">"*++++--++*++" -> "++"</span><br />
<br />
4 - A subsequência <span style="font-family: Courier New, Courier, monospace;">"+*+"</span> tem um resultado idêntico à subsequência <span style="font-family: Courier New, Courier, monospace;">"*-*"</span>. Este pode ser o padrão mais difícil de se visualizar, e inicialmente é difícil enxergar o objetivo desta troca, mas ela é importante para que, em seguida, novos padrões sejam identificados.<br />
A subsequência <span style="font-family: Courier New, Courier, monospace;">"-*-"</span>, de modo semelhante, tem resultado idêntico a subsequência <span style="font-family: Courier New, Courier, monospace;">"*+*"</span>.<br />
Quando umas das subsequências citadas aparecer, substitua-a pela sequência alternativa.<br />
Exemplo: <span style="font-family: Courier New, Courier, monospace;">"+*+--" -> "*-*--"</span><br />
<br />
Mas, porquê fazer todas essas remoções e substituições?<br />
Como eu citei, a aplicação destes padrões revela as sequências "alternantes disfarçadas". Se a sequência não era alternante, a sequência resultante da aplicação dos padrões será ou uma sequência vazia, ou a sequência <span style="font-family: Courier New, Courier, monospace;">"*"</span>. Caso contrário, a sequência é alternante.<br />
<br />
Da onde veio toda essa história?<br />
Trata-se de um teoria sofisticada estudada a anos, e você pode ler mais a respeito aqui:<br />
<a href="http://www.mathteacherscircle.org/assets/session-materials/JTantonRationalTangles.pdf">http://www.mathteacherscircle.org/assets/session-materials/JTantonRationalTangles.pdf</a><br />
<br />
<br />
Espero que eu tenha sido claro o suficiente.<br />
Caso haja alguma dúvida, sugestão ou falha minha, deixem um comentário abaixo.<br />
Agradecimentos ao Gabriel Dalalio, por ter me explicado praticamente tudo o que escrevi aqui.<br />
<br />
Até mais :)Unknownnoreply@blogger.com3tag:blogger.com,1999:blog-2697059789481443605.post-3667866788552612702014-02-22T18:05:00.001-03:002014-02-25T23:06:39.472-03:00Contest Delta - Editorial (English Version)Hey, today occurred tha second open contest at URI, the Contest Delta, where I wrote 5 from the 13 problems available at the contest. I thank Ricardo Oliveira for reviewing my problems. The other problems were written by Neilor Tonin, Lucas Negri, Márcio Oshiro and Gabriel Dalalio.<br />
<br />
<b>[Se você fala Português, venha aqui:]</b><br />
<a href="http://crbonilha.blogspot.com/2014/02/contest-delta-editorial.html">http://crbonilha.blogspot.com/2014/02/contest-delta-editorial.html</a><br />
<br />
Congratulations to the winners of the contest:<br />
1st place: Fernando Fonseca<br />
2nd place: Igor Wolff<br />
3rd place: Márcio Barbosa<br />
<br />
The winners got the following shirt:<br />
<a href="https://www.dropbox.com/s/t973nyp3cl98khz/1901876_621867837882912_1664611302_n.png">https://www.dropbox.com/s/t973nyp3cl98khz/1901876_621867837882912_1664611302_n.png</a><br />
Cool, no?<br />
<br />
I wrote less than half of the problems in this contest, so my editorial will be incomplete for an undetermined time. After the contest ends, I will try to make the other problems, and then I will share my solution here, but I don't know how long it is going to take.<br />
Click at the link below to see the editorial.<br />
<br />
<a name='more'></a><br />
<span style="font-size: large;"><b>The Guilty</b></span> - <a href="http://www.urionlinejudge.com.br/judge/en/problems/view/1521">[link]</a><br />
This exercise is quite simple: a student would always say another's student number, or his own number. To find out who will end up turning himself, it is enough to follow the given tips starting by the K-th student, until some student turns himself.<br />
<br />
Here is the Pseudocode:<br />
<blockquote class="tr_bq">
while n[k] != k<br />
k = n[k];<br />
print k;</blockquote>
<b><span style="font-size: large;">Linear Parking Lot</span></b> - <a href="http://www.urionlinejudge.com.br/judge/en/problems/view/1523">[link]</a><br />
Doesn't the parking lot remember any particular data structure? What about stack? It is only possible to park the car at the top of the stack, and to remove the car that is at the top of the stack.<br />
<br />
To solve the exercise, it is enough to simulate the order at which the cars enter and leave the parking lot, verifying if the stack rules are respected.<br />
One solution would be to fill an <i>arrive</i> array with the index <i>i</i> of the car that arrives at time <i>t</i>, in other words, <i>arrive</i>[<i>t</i>] = <i>i</i>. In a similar way, fill a <i>leave</i> array. If there is no car that arrives and/or leaves at the time <i>t</i>, <i>arrive</i>[<i>t</i>] = <i>leave</i>[<i>t</i>] = 0.<br />
<br />
The pseudocode would look like this:<br />
<blockquote class="tr_bq">
for i from 1 until greatest_t<br />
if leave[i] != 0<br />
if !stack.empty AND stack.top = leave[i]<br />
stack.pop;<br />
else<br />
print "Nao";<br />
end loop;</blockquote>
<blockquote class="tr_bq">
if arrive[i] != 0<br />
if stack.size < k<br />
stack.push(arrive[i]);<br />
else<br />
print "Nao";<br />
end loop;</blockquote>
<br />
<b><span style="font-size: large;">Gruntz</span></b> - <a href="http://www.urionlinejudge.com.br/judge/en/problems/view/1525">[link]</a><br />
There are two ways to approach this problem, and more two to implement.<br />
- One of them is to position the character in all of the borders of the map and verify if he can get to the middle.<br />
- The other is to position the character in the middle of map, and verify if he can go to any of the borders (he will walk at the opposite direction of the arrows).<br />
<br />
Once chosen one of the two approaches, there are two ways to implement:<br />
- Using a depth-first-search with backtracking, in other words, walking at the direction the arrows point, or walking at the opposite direction the arrows point and spending a value of K. If K is equal to 0, it is only possible to walk at the pre-defined directions. If you ge to the middle (or the borders, depending on your previous choice), then the answer is "Sim".<br />
A piece of the code: <a href="https://github.com/crbonilha/codes/blob/master/contest_delta/gruntz.cpp">https://github.com/crbonilha/codes/blob/master/contest_delta/gruntz.cpp</a><br />
<br />
- It is possible to create a graph where the edges have weight 0 (when they follow the arrows flow) or weight 1 (when they follow the opposite arrows flow). With this graph, it is enough to find the minimum path between the border and the middle (or vice-versa), and verify if this path has cost <= K. For such, the Dijkstra code is a nice choice.<br />
A piece of the code: [soon]<br />
<br />
<b><span style="font-size: large;">Guilds</span></b> - <a href="http://www.urionlinejudge.com.br/judge/en/problems/view/1527">[link]</a><br />
This exercise requires an efficient implemention to:<br />
- Find which Set a player A is in.<br />
- Unite two Sets.<br />
- Find out how many points a Set has.<br />
<br />
The first two operations are classic from a data structure called Disjoint-set. The third operation is easily added once the other two are implemented.<br />
For more details, you can follow this link:<br />
<a href="http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure">http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure</a><br />
<br />
To find out if Rafael was in the guild that won a battle, first you verify if he was at one of the guilds that were fighting, and then verify if his guild won. Here is a pseudocode:<br />
<blockquote class="tr_bq">
guild_a = find(A);<br />
guild_b = find(B); </blockquote>
<blockquote class="tr_bq">
if guild_a = find(1) AND guild_a.points > guild_b.points<br />
counter++;<br />
else if guild_b = find(1) AND guild_b.points > guild_a.points<br />
counter++; </blockquote>
<b><span style="font-size: large;">Abbreviations</span></b> - <a href="http://www.urionlinejudge.com.br/judge/en/problems/view/1519">[link]</a><br />
To solve this exercise it is enough to have some experience with strings manipulation, such as words splitting, and make use of a good data structure to save all the words and the number of times each of them appears at the text.<br />
<br />
With the <i>Map</i> structure it is possible to manage all the words that appears at the text. After you find all the words with more than two characters, it is possible to fill a <i>Vector</i>, along with the number of times the word appear and the number of saved characters.<br />
<br />
With this <i>Vector</i> filled separately for each initial letter, it is possible to sort it according to the number of saved characters, and the one that has the greater value will be printed at the end of the algorithm.<br />
<br />
The greatest challenge is at the implementation, that can be tiring and/or tricky, taking some time from the contest. Exercises like this are better availed if saved to the end of the contest, when all the other exercises are done OR when you don't know how to solve the other exercises (Just my opinion).<br />
<br />
<b>EDIT</b>: There will have no test cases where two different words with the same initial letter would result in the same amount of saved characteres. I assured this didn't happen, but I forgot to make it clear at the problem description.<br />
<br />
<b><span style="font-size: large;">Screws and Nuts</span></b> - <a href="http://www.urionlinejudge.com.br/judge/en/problems/view/1520">[link]</a><br />
There are more than one way to solve this problem, and I am going to describe two.<br />
<br />
1- For each given interval, add all the values that belong to that interval to an array. After that, sort the array, and make a loop that finds the first and the last position where the <i>Num</i> value appears (one alternative would be to use binary search here).<br />
<br />
2- Because the values of each interval are always between 1 and 100, it is possible to maintain an array <i>count</i> that describes how many times each value <i>i</i> appears. After that, we can find out how many values are before <i>Num</i> just by adding thet <i>count</i> array values from 1 to <i>Num</i>-1, in linear time, and find out if <i>Num</i> appeared at least one time in constant time, verifying if <i>count</i>[<i>Num</i>] == 0.<br />
<br />
<b><span style="font-size: large;">Stack Game</span></b> - <a href="http://www.urionlinejudge.com.br/judge/en/problems/view/1522">[link]</a><br />
This exercise can be solved testing all the possible allowed card removes, until at one of them the stacks are finally empty.<br />
<br />
Implement a recursive function that has a base case that all the three stacks are empty, and that calls itself recursively otherwise, indicating which cards were removed.<br />
It is possible to remove cards in 7 different ways: A, B, C, A and B, A and C, B and C, A and B and C.<br />
<br />
Be 0 the position at the top of the stack initially, and N-1 the position of the last card at the stack, the recursive function would be like this:<br />
<a href="https://github.com/crbonilha/codes/blob/master/contest_delta/jogo_das_pilhas.cpp">https://github.com/crbonilha/codes/blob/master/contest_delta/jogo_das_pilhas.cpp</a><br />
<br />
Unite this to a way to prevent that the same state is called million of times.<br />
<br />
<b><span style="font-size: large;">Max, the Mad</span></b> - <a href="http://www.urionlinejudge.com.br/judge/en/problems/view/1529">[link]</a><br />
The search this exercise presents may be a little differente from the usual. Not only you need to get from a vertex A to a vertex B, but you need to buy as little gasoline as possible.<br />
<br />
Leave to buy gas only when you need may be more expensive than buying it previously, or vice-versa. But this kind of situation is hard to forecast.<br />
<br />
Note now that the limits are very small. There are at most 10 cities and 20 roads. If it is hard to think about an optimal strategy, maybe testing all the possibilities is the solution.<br />
<br />
Solution: for each city, go to all the adjacent cities, buying all the possible amount of gasoline that is possible (between 0 and limit-tank, inclusive), and see which of the alternatives gives you the best amount of saved money.<br />
<br />
Here is a piece of code to exemplify:<br />
<a href="https://github.com/crbonilha/codes/blob/master/contest_delta/max_o_louco.cpp">https://github.com/crbonilha/codes/blob/master/contest_delta/max_o_louco.cpp</a><br />
<br />
<b><span style="font-size: large;">Transporting Snacks</span></b> - <a href="http://www.urionlinejudge.com.br/judge/en/problems/view/1526">[link]</a><br />
The challenge here depends on the way you approach to the problem. I will explain a little bit of how I interpreted, that would be to calculate the number of trips between each adjacent position, and try to generalize this value for more than one adjacent position.<br />
<br />
Let's say that he has 15 snacks to be transported, and he can carry 10 stacks per trip. The final distance doesn't matter for now. Be A the initial point, and B a point 100 meters ahead of A.<br />
There are initially 15 snacks at point A, and 0 at point B. Let's say he is going to carry 10 snacks to the point B. Because he eats one snack after each 100 meters, only 9 snacks will get to point B.<br />
We have now 5 snacks at point A, and 9 at point B. Let's say that he wants to come back to point A to get the remaining snacks. For that he takes one of the snacks with him so he can eat after the 100 meters trip, gets the 5 remaining snacks there, and comes back to point B, eating one more snack.<br />
We have now 12 snacks at point B, and 0 at point A.<br />
<br />
Notice now that the amount of necessary eaten snacks to carry all the snacks between two adjacent points is not so hard to forecast. To take L snacks, how many trips is it going to be necessary? And for each trip, how many snacks are eaten?<br />
Tip: trips = ceil(L/C);<br />
eaten_snacks = ?<br />
<br />
All would be fine we could apply this D times, but D may be a very large number.<br />
The second stage is to count what is the distance in what the number of trips is the same, decreasing the number of iterations in D.<br />
<br />
<br />
More exercises may be added here soon.<br />
<br />
Any doubt, suggestion, or correction?<br />
Send me and e-mail, or leave a comment below.<br />
<br />
See you later :)Unknownnoreply@blogger.com5tag:blogger.com,1999:blog-2697059789481443605.post-25652268447060429902014-02-22T18:05:00.000-03:002014-02-28T00:47:17.242-03:00Contest Delta - EditorialOlá, hoje ocorreu o segundo contest aberto do URI, o Contest Delta, onde eu escrevi 5 dos 13 problemas disponíveis na competição. Agradeço ao Ricardo Oliveira por revisar meus problemas. Os outros problemas foram escritos pelo Neilor Tonin, Lucas Negri, Márcio Oshiro e Gabriel Dalalio.<br />
<br />
<b>[For those who only speak English, come here:]</b><br />
<a href="http://crbonilha.blogspot.com/2014/02/contest-delta-editorial-english-version.html">http://crbonilha.blogspot.com/2014/02/contest-delta-editorial-english-version.html</a><br />
<br />
Parabéns aos ganhadores da competição:<br />
1⁰ lugar: Fernando Fonseca<br />
2⁰ lugar: Igor Wolff<br />
3⁰ lugar: Márcio Barbosa<br />
<br />
Os ganhadores levaram pra casa esta camiseta:<br />
<a href="https://www.dropbox.com/s/t973nyp3cl98khz/1901876_621867837882912_1664611302_n.png" target="_blank">https://www.dropbox.com/s/t973nyp3cl98khz/1901876_621867837882912_1664611302_n.png</a><br />
Bacana, não?<br />
<br />
Agora vamos ao que interessa: eu escrevi menos da metade dos exercícios deste contest, portanto o meu editorial estará incompleto por um tempo indeterminado. Após o contest acabar, vou tentar fazer os exercícios, e então eu compartilho com vocês minha solução, mas não sei quanto tempo isso pode levar.<br />
Clique no link abaixo para ver o editorial.<br />
<br />
<a name='more'></a><br />
<b><span style="font-size: large;">O Culpado</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1521" target="_blank">[link]</a><br />
Este exercício é bem simples: um aluno sempre entrega outro, ou entrega a si mesmo. Para descobrir quem acabará se entregando, basta seguir as dicas dadas começando do aluno K, até que um determinado aluno entregue a si mesmo.<br />
<br />
Pseudocódigo:<br />
<blockquote class="tr_bq">
enquanto n[k] != k<br />
k = n[k];<br />
imprima k;</blockquote>
<b><span style="font-size: large;">Estacionamento Linear</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1523" target="_blank">[link]</a><br />
O funcionamento deste estacionamento não vos lembram alguma estrutura de dado em particular? Que tal pilha? Só é possível estacionar o carro no final da pilha, e só é possível remover o carro que está no final da pilha.<br />
<br />
Para resolver o exercício, basta então simular a ordem em que os carros entram e saem do estacionamento, verificando se as limitações da pilha sempre são respeitadas.<br />
Uma solução seria preencher um vetor <i>chegada</i> com o indice <i>i</i> do carro que chega no tempo <i>t</i> , ou seja, <i>chegada</i>[<i>t</i>] = <i>i</i>. De forma semelhante, preencher um vetor <i>saida</i>. Se nenhum carro chega e/ou sai no tempo <i>t</i>, <i>chegada</i>[<i>t</i>] = <i>saida</i>[<i>t</i>] = 0.<br />
O pseudocódigo ficaria então assim:<br />
<blockquote class="tr_bq">
para i de 1 até maior_t<br />
se saida[i] != 0<br />
se !pilha.vazia E pilha.topo = saida[i]<br />
pilha.pop;<br />
senao<br />
imprima "Nao";<br />
encerra laço; </blockquote>
<blockquote class="tr_bq">
se chegada[i] != 0<br />
se pilha.tamanho < k<br />
pilha.push(chegada[i]);<br />
senao<br />
imprima "Nao";<br />
encerra laço;</blockquote>
<br />
<b><span style="font-size: large;">Gruntz</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1525" target="_blank">[link]</a><br />
Há duas maneiras de se encarar este problema, e mais duas maneiras de implementar.<br />
- Uma delas é posicionar o personagem em todas as bordas existentes e verificar se ele consegue chegar até o centro.<br />
- A outra é posicionar o personagem no centro, e verificar se ele consegue chegar até alguma das bordas (ele andará no sentido contrário das setas).<br />
<br />
Uma vez escolhida uma das duas maneiras, há duas formas de se implementar:<br />
- Utilizando uma busca em profundidade com backtracking, ou seja, andando nas direções que as setas apontam, ou andando na direção contrária e gastando um valor de K. Se K já for igual a 0, só é possível andar nas direções pré-definidas. Se você alcançar o centro (ou a borda, dependendo da sua escolha anterior), então a resposta é "Sim".<br />
Trecho de código: <a href="https://github.com/crbonilha/codes/blob/master/contest_delta/gruntz.cpp" target="_blank">https://github.com/crbonilha/codes/blob/master/contest_delta/gruntz.cpp</a><br />
<br />
- É possível montar um grafo onde as arestas podem conter peso 0 (quando seguem o fluxo das setas) ou peso 1 (quando seguem o fluxo contrário da seta). Com este grafo, basta encontrar o caminho mínimo entre a borda e o centro (ou vice-versa), e verificar se este caminho mínimo tem custo <= K. Para tal, a implementação do algoritmo de Dijkstra é suficiente.<br />
Trecho de código: [em breve]<br />
<br />
<b><span style="font-size: large;">Guildas</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1527" target="_blank">[link]</a><br />
Este exercício requer uma implementação eficiente para:<br />
- Descobrir a qual Set pertence um jogador A.<br />
- Unir dois Sets.<br />
- Descobrir o número de pontos de cada Set.<br />
<br />
As duas primeiras operações são operações clássicas de uma estrutura chamada Disjoint-set (Conjuntos Disjuntos). A terceira operação é facilmente adicionada uma vez que haja as duas primeiras.<br />
Um post mais detalhado pode ser encontrado aqui:<br />
<a href="http://marathoncode.blogspot.com.br/2013/01/conjuntos-disjuntos.html" target="_blank">http://marathoncode.blogspot.com.br/2013/01/conjuntos-disjuntos.html</a><br />
<br />
Para descobrir se Rafael estava na guilda que ganhou a batalha, antes verifique se ele pertencia a uma das guildas que estava batalhando, e então verifique se a guilda dele venceu. Eis um pseudocódigo:<br />
<blockquote class="tr_bq">
guilda_a = find(A);<br />
guilda_b = find(B); </blockquote>
<blockquote class="tr_bq">
se guilda_a = find(1) E guilda_a.pontos > guilda_b.pontos<br />
contador++;<br />
senão se guilda_b = find(1) E guilda_b.pontos > guilda_a.pontos<br />
contador++; </blockquote>
<b><span style="font-size: large;">Abreviações</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1519" target="_blank">[link]</a><br />
Para resolver este exercício basta ter alguma experiência com manipulação de strings, tal como a separação de palavras, e fazer uso de uma boa estrutura para guardar todas as palavras e o número de vezes em que ela aparece no texto.<br />
<br />
Com a estrutura <i>Map</i> é possível manter controle sobre todas as palavras que aparecem no texto. Após coletar todas as palavras com mais de dois caracteres, é possível jogá-las dentro de um <i>Vector</i>, junto com o número de aparições e o número de caracteres economizados.<br />
<br />
Com este <i>Vector</i> preenchido separadamente para cada letra inicial, é possível ordená-lo de acordo com o número de caracteres economizados, e aquele que tiver o maior número de economia será impresso ao final da execução do algoritmo.<br />
<br />
O maior desafio está na implementação, que pode ser um pouco trabalhosa, custando um bom tempo da competição. Exercícios como este são melhores aproveitados se guardados para o final da competição, quando todos os outros exercícios já foram resolvidos OU quando não se sabe resolver os outros exercícios.<br />
<br />
<b>EDIT</b>: Nunca haverá casos onde a abreviação de duas palavras de mesma letra inicial resulte no mesmo total de caracteres economizados. Eu me assegurei que isso não acontecesse, mas esqueci de deixar claro no enunciado.<br />
<br />
<b><span style="font-size: large;">Parafusos e Porcas</span></b> - <span id="goog_1978459917"></span><span id="goog_1978459918"></span><a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1520" target="_blank">[link]</a><br />
Há mais de uma maneira de se aproximar a este problema, e eu vou descrever duas.<br />
<br />
1- Para cada intervalo dado, adicione todos os valores pertencentes a tal intervalo dentro de um vetor de inteiros. Após isso, ordene o vetor, e faça um laço encontrar a primeira e a última aparição do valor <i>Num</i> (uma alternativa também é usar uma busca binária aqui).<br />
Uma sugestão de melhoria também seria implementar o Insertion Sort quando os valores estão sendo inseridos no vetor. Que tal praticar?<br />
<br />
2- Como os valores de cada intervalo estão sempre entre 1 e 100, é possível manter um vetor <i>count</i> que descreva quantas vezes cada valor <i>i</i> aparece. Após isso, podemos saber quantos valores estão antes de <i>Num</i> apenas somando as posições de 1 até <i>Num</i>-1 em <i>count</i> em tempo linear, e saber se <i>Num</i> apareceu ou não em tempo constante, verificando se <i>count</i>[<i>Num</i>] == 0.<br />
<br />
<b><span style="font-size: large;">Jogo das Pilhas</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1522" target="_blank">[link]</a><br />
Este exercício pode ser resolvido testando todas as possibilidades permitidas de remoção de cartas, até que em uma delas a mesa esteja vazia.<br />
<br />
Implemente uma função recursiva que tenha como caso base as três pilhas estarem vazias, e que chame a si mesma recursivamente caso contrário, indicando quais cartas foram removidas.<br />
É possível remover cartas de 7 formas diferentes: A, B, C, A e B, A e C, B e C, A e B e C.<br />
<br />
Seja 0 a posição do topo da pilha inicialmente, e N-1 a posição da última carta, a função recursiva ficaria assim:<br />
<a href="https://github.com/crbonilha/codes/blob/master/contest_delta/jogo_das_pilhas.cpp" target="_blank">https://github.com/crbonilha/codes/blob/master/contest_delta/jogo_das_pilhas.cpp</a><br />
<br />
Una isso a uma maneira de prevenir que o mesmo estado seja consultado milhões de vezes.<br />
<br />
<b><span style="font-size: large;">Max, o Louco</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1529" target="_blank">[link]</a><br />
Trata-se de uma busca um pouco diferente do que pode-se estar acostumado. Não só é preciso encontrar um caminho entre um vértice A até um vértice B, mas você precisa comprar gasolina de modo estratégico.<br />
<br />
Deixar para comprar gasolina apenas quando se precisa pode sair mais caro do que comprar com antecedência, ou vice-versa. Mas esse tipo de coisa é difícil de prever.<br />
<br />
Note agora que os limites estão bem baixos. Há no máximo 10 cidades e 20 estradas. Se está difícil pensar numa estratégia de previsão, talvez testar todas as possibilidades seja a saída.<br />
<br />
Solução: para cada cidade, experimente ir até as cidades adjacentes, comprando todas as quantias de gasolina que for possível (entre 0 e limite-tanque_atual, inclusive), e veja qual das alternativas lhe leva até o destino gastando menos dinheiro.<br />
<br />
Eis um trecho do código para exemplo:<br />
<a href="https://github.com/crbonilha/codes/blob/master/contest_delta/max_o_louco.cpp" target="_blank">https://github.com/crbonilha/codes/blob/master/contest_delta/max_o_louco.cpp</a><br />
<br />
<b><span style="font-size: large;">Transportando Lanches</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1526" target="_blank">[link]</a><br />
O desafio aqui depende da forma como você interpreta o problema. Vou explicar um pouco a forma que eu interpretei, que seria calcular o número de viagens entre cada posição adjacente, e tentar generalizar esse valor para mais de uma posição adjacente.<br />
<br />
Digamos que ele tem 15 lanches para serem transportados, e possa carregar 10 lanches por vez. A distância final por enquanto não importa. Seja A o ponto inicial, e B um ponto adjacente ao ponto A.<br />
Há inicialmente 15 lanches no ponto A, e 0 no ponto B. Digamos que sejam levados 10 lanches até o ponto B. Como o transportador come um lanche a cada posição adjacente, só 9 lanches chegarão até o ponto B.<br />
Temos agora 5 lanches no ponto A, e 9 no ponto B. Digamos que ele queira voltar ao ponto A para pegar os lanches restantes. Para isso deve levar no bolso um lanche para que possa comer, pegar os 5 lanches lá, e voltar para o ponto B, comendo mais um lanche.<br />
Temos agora 12 lanches no ponto B, e 0 no ponto A.<br />
<br />
Notem agora que a quantidade de lanches comidos para levar toda a encomenda entre dois pontos adjacentes não é tão difícil de prever. Para levar L lanches, será preciso quantas viagens? E a cada viagem, quantos lanches são comidos?<br />
Dica: viagens = teto(L/C);<br />
lanches_comidos = ?<br />
<br />
Tudo estaria bem se pudéssemos aplicar esse cálculo D vezes, porém D pode ser um número muito alto.<br />
O segundo passo é contar qual a distância pela qual o número de viagens é a mesma, diminuindo o número de iterações D.<br />
<br />
<b>EDIT:</b><br />
Para ver a segunda parte do editorial, com os exercícios Fibonacci de Novo!, Quantas Substrings?, e Cordas Emaranhadas, clique no link abaixo:<br />
<a href="http://crbonilha.blogspot.com/2014/02/contest-delta-editorial-continuacao.html" target="_blank">http://crbonilha.blogspot.com/2014/02/contest-delta-editorial-continuacao.html</a><br />
<br />
<br />
Mais exercícios podem ser adicionados aqui em breve.<br />
<br />
Alguma dúvida, sugestão, ou correção?<br />
Me envie um e-mail, ou deixe um comentário abaixo.<br />
<br />
Até mais :)Unknownnoreply@blogger.com21tag:blogger.com,1999:blog-2697059789481443605.post-82143421997623396372014-02-19T01:05:00.000-03:002014-02-19T01:05:00.245-03:00Contest DeltaSaudações.<br />
<br />
Esse sábado vai rolar o segundo contest aberto do URI, onde eu escrevi 6 dos 13 exercícios inéditos que estarão disponíveis :)<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiWjH-gEXpTvSur-NKdT5Y80jfccROzAxhFmxfrjf-mShiOHoHRxzUSeLdlVGfThCCdeIOljsi1XFyQQ6gSXaHcIePyJoxasbJ8J_eOTDDkvZ_NHiaDSpp2DNSoevPTT5GOadkLJuJs2jpC/s1600/1800423_619614634774899_956615507_n.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiWjH-gEXpTvSur-NKdT5Y80jfccROzAxhFmxfrjf-mShiOHoHRxzUSeLdlVGfThCCdeIOljsi1XFyQQ6gSXaHcIePyJoxasbJ8J_eOTDDkvZ_NHiaDSpp2DNSoevPTT5GOadkLJuJs2jpC/s1600/1800423_619614634774899_956615507_n.png" height="285" width="400" /></a></div>
<br /><span id="goog_1906748506"></span>
Dia: 22/02/2014<br />
Horário: das 14:00 até as 18:00 (para diferentes fuso horários: <a href="http://timeanddate.com/s/2j9k">http://timeanddate.com/s/2j9k</a>)<br />
Se inscrevam em: <a href="http://www.urionlinejudge.com.br/judge/login">http://www.urionlinejudge.com.br/judge/login</a>, na aba Contests.<br />
<br />
Vou tentar disponibilizar um editorial sobre os exercícios, mas como não sou o único escritor deste contest, talvez eu não consiga resolver todos os exercícios.<br />
<br />
Participem, e até mais.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2697059789481443605.post-61779029876419397782014-02-05T18:48:00.003-02:002014-02-26T18:29:27.553-03:00Contest Bonilha - Editorial (English version)Hi programmers! I had the honor of writing the exercises for the first open to the public contest at URI, entitled "Contest Bonilha". I thank the opportunity to the portal staff, specially to the support given by Neilor and Jean, and also to the programmer Ricardo Oliveira, who revised all the exercises and eventually corrected the exercise and/or the files of some of them.<br />
<br />
<b>Se você quer ver a versão em Português do editorial, <a href="http://crbonilha.blogspot.com.br/2014/02/contest-bonilha-editorial.html">venha aqui</a>.</b><br />
<br />
Congratulations to the best placed programmers:<br />
Marcos Kawakami<br />
dilsonguim<br />
Hasan0540<br />
<br />
For those who couldn't participate, the exercises are already available at the URI site.<br />
<br />
I am going to write a small editorial with some resolution tips for the exercises. I advise you to read the editorial only after thoroughly tries of solving the problems, and I ask you to correct me if I say something non-sense.<br />
<br />
Click at the link below to see the editorial.<br />
<a name='more'></a><br />
<br />
<b><span style="font-size: large;">Hello Galaxy</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1515">[link]</a><br />
How to find out the year that some planet sent the message?<br />
R: Subtracting the travel time from the arrival year.<br />
<br />
So, the first planet to send the message is the one who has the minimum value at arrivalTime - travelTime.<br />
<br />
<b><span style="font-size: large;">Contest</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1514">[link]</a><br />
The characteristics may seem confuse, but the solution to the exercise doesn't hide any secret: it is enough to check each of the characteristics and print the result.<br />
<br />
1 - Nobody solved all the problems.<br />
If there is at least one line with only 1's, this characteristic is false, because such line correspond to a contestant that solved all the problems.<br />
<br />
2 - Every problem was solved by at least one person.<br />
If there is at least one column with only 0's, this characteristic is false, because such columns correspond to a problem that wasn't solved by anyone.<br />
<br />
The other two are very similar.<br />
<br />
<b><span style="font-size: large;">Image</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1516">[link]</a><br />
It is enough to repeat each line A/N times, and each column B/M times. For example, if N = 3 and A = 12, it is enough to repeat each line 4 times, because 3 lines repeated 4 times is equal to 12 lines (3 * 4 = 12).<br />
<br />
The problem falls to the repetition implementation. There are several ways to implement it, so I will leave this piece of code of how I did it:<br />
<a href="https://github.com/crbonilha/codes/blob/master/imagem.cpp">https://github.com/crbonilha/codes/blob/master/imagem.cpp</a><br />
<br />
<span style="font-size: large;"><b>Tiles</b></span> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1512">[link]</a><br />
The goal of this exercise was to present the Set Union concept, more specifically the Inclusion-Exclusion theory.<br />
<br />
Let's see, a fast way of finding how many tiles are going to be painted is the following:<br />
total = floor(N/A) + floor(N/B)<br />
<br />
But it is not hard to notice that some tiles may be counted more than once, as shows the image below.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZmNc0XwB-kIijHC_X0mopQS5L2sMtHcIAuGhE9cTwkL4HmlvlOE-4kjBEuxgAVhG53ptTpufFoc55VcwomhnNzbO7_5ULClQWF1HjjS_T99ca025ymbCkaUsY87GEVpn2AikAMfuYOMmD/s1600/azulejos.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZmNc0XwB-kIijHC_X0mopQS5L2sMtHcIAuGhE9cTwkL4HmlvlOE-4kjBEuxgAVhG53ptTpufFoc55VcwomhnNzbO7_5ULClQWF1HjjS_T99ca025ymbCkaUsY87GEVpn2AikAMfuYOMmD/s1600/azulejos.png" height="192" width="320" /></a></div>
<br />
total = floor(6/2) + floor(6/3)<br />
total = 3 + 2 = 5<br />
However, we can count only 4 painted tiles.<br />
<br />
There goes the Inclusion-Exclusion theory: we have two sets, and when we add them we are adding repeated elements. To fix it, we must subtract the intersection of such sets.<br />
Notice, a number is multiple of A and B if and only if is multiple by LCM(A, B) (google least common multiple).<br />
<br />
<b>Solution</b>: A + B - (A U B)<br />
<br />
<b><span style="font-size: large;">Apples</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1517">[link]</a><br />
At the transition between the time t and the time t+1, you have two choices: move or stay where you are. The problem is to decide which of these choices is going to raise the maximum number of apples.<br />
<br />
There is no exit unless to test all the options, and nothing better to do it than the reuse of information: Dynamic Programming.<br />
<br />
If this concept is new to you, it may be a good opportunity to learn it. Dynamic Programming is about reusing informations that, during the algorithm, may be calculated more than once.<br />
<br />
The first step is to divide the problem in <b>states</b>. Imagine that you are at the position [x, y] at time t. This is a state: [x, y, t].<br />
<br />
Once you find out what is the best way of collecting apples from this state, save such information and reuse it every time that during the algorithm you find yourself at the same state.<br />
<br />
<b>The solution is</b>: Total(x, y, t) = max(Total(new_x, new_y, t+1), for all [new_x, new_y] that correspond to a square adjacent to [x, y], or [x, y] itself).<br />
Add 1 every time that there is an apple at the position [x, y], at time t.<br />
<br />
For more details, search for Dynamic Programming.<br />
<b><br class="Apple-interchange-newline" />EDIT:</b><br />
The solution I mentioned was the one I thought when I wrote the exercise, but talking with some programmers I found out a second way of solving this exercise, with a lesser complexity.<br />
<br />
Be x, y and t the information about a first apple, and nx, ny and nt the information about a second apple, it is possible to get from [x, y] to the position [nx, ny] in nt-t seconds? (Think about a mathematical formula).<br />
If yes, we can capture both apples. If not, we can capture one of them, but not both.<br />
<br />
Making use of Dynamic Programming, we can reuse informations and test all possibilities.<br />
<br />
<b style="font-size: x-large;">Horse</b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1513">[link]</a><br />
This exercise divides into two problems: finding out the shortest path between each of the pieces, considering the particularity of the horse jump; and finding the best capture sequence to be followed.<br />
<br />
The shortest path can be solved using a Breadth First Search (BFS) from each of the pieces to the others. At the end, we will have a graph with K+1 vertices, all interconnected with edges that correspond to the shortests paths between them.<br />
<br />
The second part involves, as in the previous exercise, the checking of all the possible paths.<br />
<br />
We can start capturing any of the K pawns. After, we can capture any of the K-1 remaining pawns. After, K-2 pawns. Until we have captured all the pawns and we have to return to the initial position.<br />
At the end we will have the following complexity: K! (K * K-1 * ... * 2 * 1).<br />
<br />
As the maximum value of K is 15, we have a complexity of 15!, which is way too high.<br />
<br />
To decrease this we can use a technique known as bitmask. It is a way of translating which pawns you have already captured to an integer number, in other words, a <b>state</b>.<br />
Such state can be used to reuse information, and then we have our complexity decreased.<br />
<br />
For more details, search for Bitmask, Dynamic Programming and Hamiltonian Cycle.<br />
<br />
<span style="font-size: large;"><b>Turtles</b></span> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1518">[link]</a><br />
Here we have a variation of the previous exercise. We have to capture turtles this time, but they are always moving, and it is almost impossible to reuse information here. Fortunately, the number of turtles is small, and 3! is not a scary complexity.<br />
<br />
See, we can capture the turtles in the following orders: 1->2->3; 1->3->2; 2->1->3; 2->3->1; 3->1->2; 3->2->1. At total 6 orders (3!).<br />
<br />
The challenge is at finding how many seconds it takes to reach a moving target. There are at least two solutions: simulate the race, and see how many seconds it takes; try some values and use the concept of binary search to add precision to the choice.<br />
<br />
For the second given soluction, here is a definition given by the programmer Ricardo Oliveira:<br />
<blockquote class="tr_bq">
Be t the minimum necessary time to reach a turtle initially at (Tx, Ty) (and, after t seconds, at (Tx+t, Ty) (or (Tx, Ty+t), according to the direction)) from the position (Rx, Ry).</blockquote>
<blockquote class="tr_bq">
Be t' > t. It is valid to notice that, as Rafael can move faster than the turtle, Rafael can get to (Tx+t', Ty) *before* the turtle and wait for her at this position. Furthermore, if t' < t, the turtle will get to (Tx+t', Ty) before Rafael, and therefore not be captured.</blockquote>
<blockquote class="tr_bq">
So, the value of t is the minimum value of t' such that Rafael can get to the position (Tx+t', Ty) before (or at the same time) as the turtle. Soon, it is possible to find such value with a binary search: for each analysed number t', checks if Rafael can get before or at the same time at (Tx+t', Ty) as the turtle, and the interval is refreshed accordingly.</blockquote>
<blockquote class="tr_bq">
Obviously, the turtle takes t' seconds to go from (Tx, Ty) to (Tx+t', Ty). The problem falls to defining the amount of required time so Rafael can go from (Rx, Ry) to (Tx+t', Ty). One analysis of Rafael's movements, and mainly the fact that he takes 2 seconds to go from (Rx, Ry) to, for example, (Rx+2, Ry+2), *independently of the path he follows*, allows us to conclude that Rafael can always take a greedy path, that takes min(dx, dy) + ceil(abs(dx-dy)/2) seconds, where dx = (Tx+t' - Rx) and dy = (Ty - Ry).</blockquote>
<br />
<br />
So that is it. If you had some different solution and wants to share, or if you still have some question, leave your commentary below, or send me an e-mail.<br />
<br />
I hope you have enjoyed the contest. See you later.Unknownnoreply@blogger.com11tag:blogger.com,1999:blog-2697059789481443605.post-77075037371512250042014-02-05T00:47:00.000-02:002014-02-26T18:29:17.010-03:00Contest Bonilha - EditorialOlá maratonistas! Tive a honra de escrever os exercícios para o primeiro contest aberto ao público do URI, entitulado "Contest Bonilha". Agradeço a oportunidade ao pessoal do portal, em especial ao apoio do Neilor e do Jean, e também ao maratonista Ricardo Oliveira, por revisar todos os exercícios e eventualmente corrigir o enunciado e/ou os arquivos de alguns deles.<br />
<br />
<b>For those who only speak English, <a href="http://crbonilha.blogspot.com.br/2014/02/contest-bonilha-editorial-english.html">come here</a>.</b><br />
<br />
Parabéns aos melhores colocados do contest:<br />
Marcos Kawakami<br />
dilsonguim<br />
Hasan0540<br />
<br />
Pra quem não pode acompanhar, os exercícios já estão disponíveis no portal.<br />
<br />
Vou escrever um pequeno editorial com algumas dicas de resolução dos exercícios. Aconselho que leia o editorial apenas após tentar exaustivamente resolvê-los, e peço que me corrijam caso eu fale alguma bobagem.<br />
<br />
Clique no link abaixo para ver o editorial.<br />
<a name='more'></a><br />
<br />
<b><span style="font-size: large;">Hello Galaxy</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1515">[link]</a><br />
Como descobrir quando algum planeta enviou a mensagem?<br />
R: Subtraindo o tempo de viagem do ano de chegada.<br />
<br />
Portanto o primeiro planeta a enviar é aquele que tem o menor valor em tempoChegada - tempoViagem.<br />
<br />
<b><span style="font-size: large;">Competição</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1514">[link]</a><br />
O enunciado pode parecer confuso, porém a solução para o exercício não esconde nenhum segredo: basta checar cada uma das características e imprimir o resultado.<br />
<br />
1 - Ninguém resolveu todos os problemas.<br />
Se houver ao menos uma linha apenas com valores 1, esta características é falsa, pois tal linha corresponde a um competidor que resolveu todos os problemas.<br />
<br />
2 - Todo problema foi resolvido por pelo menos uma pessoa.<br />
Se houver ao menos uma coluna apenas com valores 0, esta característica é falsa, pois tal coluna corresponde a um problema que não foi resolvido por ninguém.<br />
<br />
Os outros dois são bem semelhantes.<br />
<br />
<b><span style="font-size: large;">Imagem</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1516">[link]</a><br />
Basta repetir cada linha A/N vezes, e cada coluna B/M vezes. Por exemplo, se N = 3 e A = 12, basta repetir cada linha 4 vezes, pois 3 linhas repetidas 4 vezes é igual a 12 linhas (3 * 4 = 12).<br />
<br />
O problema recai então na implementação da repetição. Há diversas maneiras de se implementar isso, então vou deixar o trecho do código sobre como eu implementei:<br />
<a href="https://github.com/crbonilha/codes/blob/master/imagem.cpp">https://github.com/crbonilha/codes/blob/master/imagem.cpp</a><br />
<br />
<b><span style="font-size: large;">Azulejos</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1512">[link]</a><br />
O objetivo deste exercício era apresentar o conceito de União de Conjuntos, mais especificamente a teoria da Inclusão-Exclusão.<br />
<br />
Vejamos, uma forma rápida de descobrir quantos azulejos serão pintados é a seguinte fórmula:<br />
total = piso(N/A) + piso(N/B)<br />
<br />
Mas não é difícil notar que alguns azulejos podem estar sendo contados mais de uma vez, como na imagem abaixo.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZmNc0XwB-kIijHC_X0mopQS5L2sMtHcIAuGhE9cTwkL4HmlvlOE-4kjBEuxgAVhG53ptTpufFoc55VcwomhnNzbO7_5ULClQWF1HjjS_T99ca025ymbCkaUsY87GEVpn2AikAMfuYOMmD/s1600/azulejos.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZmNc0XwB-kIijHC_X0mopQS5L2sMtHcIAuGhE9cTwkL4HmlvlOE-4kjBEuxgAVhG53ptTpufFoc55VcwomhnNzbO7_5ULClQWF1HjjS_T99ca025ymbCkaUsY87GEVpn2AikAMfuYOMmD/s1600/azulejos.png" height="192" width="320" /></a></div>
<br />
total = piso(6/2) + piso(6/3)<br />
total = 3 + 2 = 5<br />
Porém, podemos contar apenas 4 azulejos pintados.<br />
<br />
Aí entra a teoria da Inclusão-Exclusão: temos dois conjuntos, e ao somá-los estamos somando elementos repetidos. Para concertar isso, devemos subtrair a intersecção de tais conjuntos.<br />
Note, um número é múltiplo de A e de B se e somente se é múltiplo de MMC(A, B) (google mínimo múltiplo comum).<br />
<br />
<b>Solução:</b> A + B - (A U B)<br />
<br />
<b><span style="font-size: large;">Maçãs</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1517">[link]</a><br />
Na transição entre o tempo t e o tempo t+1, você pode fazer duas coisas: se mover ou ficar onde está. O problema está em decidir qual dessas escolhas vai lhe render o maior número possível de maçãs.<br />
<br />
Não há saída a não ser testar todas as opções, e nada melhor para fazer isso do que o reaproveitamento de cálculos: Programação Dinâmica.<br />
<br />
Se esse conceito é novo para você, pode ser uma boa oportunidade de aprendê-lo. Programação Dinâmica se trata de reaproveitar cálculos que, no decorrer do algoritmo, podem ser executados mais de uma vez.<br />
<br />
O primeiro passo é dividir o problema em etapas, ou <b>estados</b>. Imagine que você está na posição [x, y] no tempo t. Este é um estado: [x, y, t].<br />
<br />
Uma vez que você descobrir qual a melhor maneira de coletar maçãs a partir deste estado, salve tal solução e a utilize sempre que no decorrer do algoritmo você se encontre no mesmo estado.<br />
<br />
<b>A solução é</b>: Total(x, y, t) = max(Total(novo_x, novo_y, t+1), para todo [novo_x, novo_y] que corresponde a uma quadrado ajdacente a [x, y], ou mesmo [x, y]).<br />
Some 1 sempre que houver uma maçã na posição [x, y], no tempo t.<br />
<br />
Para mais detalhes pesquisem por Programação Dinâmica.<br />
<br />
<b>EDIT:</b><br />
A solução que eu citei foi a que eu imaginei quando escrevi o exercício, mas conversando com alguns maratonistas descobri uma segunda forma de resolver tal exercício, com uma complexidade menor.<br />
<br />
Seja x, y e t informações correspondentes a uma maçã em particular, e nx, ny e nt as informações correspondentes a uma segunda maçã em particular, é possível chegar da posição [x, y] até a posição [nx, ny] em nt-t segundos? (Pense numa fórmula matemática).<br />
Se sim, podemos capturar ambas as maçãs. Se não, podemos capturar uma das duas, mas não ambas.<br />
<br />
Utilizando-se Programação Dinâmica, podemos reaproveitar alguns cálculos e testar todas as possibilidades.<br />
<br />
<b style="font-size: x-large;">Cavalo</b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1513">[link]</a><br />
Este exercício se divide em dois problemas: descobrir o caminho mínimo entre cada uma das peças, considerando a particularidade do salto do cavalo; e descobrir qual a melhor sequência de captura de peões a ser seguida.<br />
<br />
O caminho mínimo pode ser resolvido utilizando uma Busca em Largura (BFS) a partir de cada uma das peças até as demais. Ao final de tais cálculos, teremos um grafo com K+1 vértices, todos interligados com arestas que correspondem ao caminho mínimo entre cada uma das peças.<br />
<br />
A segunda parte envolve, como no exercício anterior, a checagem de todos os possíveis de caminhos.<br />
<br />
Podemos começar capturando qualquer um dos K peões. Em seguida, poderemos capturar qualquer um dos K-1 peões restantes. Em seguida, K-2 peões. Até que tenhamos capturados todos os peões e precisemos retornar à posição inicial.<br />
Ao final teremos a seguinte complexidade: K! (K * K-1 * ... * 2 * 1).<br />
<br />
Como o maior valor de K é 15, temos uma complexidade de 15!, que é um valor muito alto.<br />
<br />
Para amenizar isso podemos utilizar uma técnica conhecida como bitmask. Trata-se de uma forma de traduzir quais peões você já capturou em um número inteiro, ou seja, um <b>estado</b>.<br />
Tal estado pode ser utilizado para reaproveitar cálculos, e temos então nossa complexidade reduzida.<br />
<br />
Para mais detalhes pesquisem por Bitmask, Programação Dinâmica e Ciclo Hamiltoniano.<br />
<br />
<b><span style="font-size: large;">Tartarugas</span></b> - <a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1518">[link]</a><br />
Eis uma variação do exercício anterior. Temos que capturar desta vez tartarugas, porém as mesmas se movem, e é quase impossível reaproveitar cálculos aqui. Por sorte o número de tartarugas é baixo, e 3! não é uma complexidade assustadora.<br />
<br />
Veja, podemos capturar as tartarugas nas seguintes ordens: 1->2->3; 1->3->2; 2->1->3; 2->3->1; 3->1->2; 3->2->1. Totalizando 6 ordens (3!).<br />
<br />
O desafio está em descobrir quantos segundos leva-se para alcançar um alvo em movimento. Há duas soluções: simular a corrida, e ver quantos segundos leva; chutar valores e utilizar o conceito de busca binária para adicionar precisão à escolha.<br />
<br />
Quanto à segunda solução citada, eis uma explicação dada pelo maratonista Ricardo Oliveira:<br />
<blockquote class="tr_bq">
Seja t o menor tempo necessário para se alcançar uma tartaruga inicialmente em
(Tx, Ty) (e, após t segundos, em (Tx+t, Ty) (ou (Tx,Ty+t), de acordo com a
direção)) a partir do ponto (Rx, Ry). </blockquote>
<blockquote class="tr_bq">
Seja t' > t. É válido notar que, como Rafael pode ser mais rápido que a
tartaruga, Rafael pode chegar em (Tx+t', Ty) *antes* da tartaruga e esperar por
ela neste ponto. Além disso, se t' < t, a tartaruga irá chegar em (Tx+t', Ty)
antes de Rafael, e portanto não será alcançada. </blockquote>
<blockquote class="tr_bq">
Assim, o valor de t é o menor valor de t' tal que Rafael pode chegar em (Tx+t',
Ty) antes (ou no mesmo tempo) da tartaruga. Logo, é possível encontrar tal valor
com uma busca binária: para cada número t' analisado, verifica-se se Rafael pode
chegar antes ou ao mesmo tempo em (Tx+t',Ty) que a tartaruga, e o intervalo é
atualizado de acordo. </blockquote>
<blockquote class="tr_bq">
Obviamente a tartaruga leva t' segundos para ir de (Tx,Ty) para (Tx+t', Ty).
O problema se limita então a definir quanto tempo Rafael leva para ir de
(Rx,Ry) para (Tx+t', Ty). Uma análise dos movimentos de Rafael, e principalmente
o fato de ele leva 2 segundos para ir de (Rx,Ry) para, por exemplo, (Rx+2,Ry+2),
*independentemente do caminho que ele seguir*, nos permite concluir que Rafael
pode sempre seguir um caminho guloso, que leva min(dx, dy) + teto(abs(dx-dy)/2)
segundos, onde dx = (Tx+t' - Rx) e dy = (Ty - Ry).</blockquote>
<br />
<br />
Então é isso. Se você teve uma solução diferente e quiser compartilhar, ou ainda estiver com alguma dúvida, deixe aqui embaixo seu comentário, ou me envie um e-mail.<br />
<br />
Espero que tenham gostado do contest. Até mais.Unknownnoreply@blogger.com8tag:blogger.com,1999:blog-2697059789481443605.post-68102597952404294782013-11-15T20:06:00.002-02:002013-11-15T20:10:00.293-02:00Inverting HuffmanPra quem não sabe, semana passada, 9 de novembro, aconteceu a fase final da maratona de programação em toda a américa latina, antecedendo apenas a fase mundial que acontecerá [em breve], e o campeão foi o time Ñtemtempabobagi, da USP.<br />
Mais informações aqui: <a href="http://maratona.ime.usp.br/resultados13/">http://maratona.ime.usp.br/resultados13/</a><br />
<br />
Nesse post vou falar sobre o exercício I da fase final, Inverting Huffman, o qual, curiosamente, ninguém resolveu.<br />
<br />
Vocês podem baixar o PDF dele e submeter o código para teste neste link:<br />
<a href="https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=615&page=show_problem&problem=4544">https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=615&page=show_problem&problem=4544</a><br />
<br />
A codificação de Huffman trata-se de uma forma de re-codificar os caracteres de um texto, de modo que o comprimento do código de cada caractere seja proporcional ao seu número de ocorrências no texto. Por exemplo, na palavra "Abacate", a letra 'a' receberia um código curto, pois aparece várias vezes, enquanto todas as outras letras, que aparecem apenas uma vez, iriam receber um código longo.<br />
Mais informações: <a href="http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/huffman.html">http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/huffman.html</a><br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjgCIahtRoVey5prM52DP4sR7zEjs1oOnwKo9orJvGj0ehJ_vmI797pImBqYx29OlPeuYbZsPAfhFLU4hVIC43xoHPoxdh2TyMlk7EnCJHoAUppHLEnIVQ_8FXUrVS4KlUsaQvBRxWXeLR9/s1600/huffman_a.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="165" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjgCIahtRoVey5prM52DP4sR7zEjs1oOnwKo9orJvGj0ehJ_vmI797pImBqYx29OlPeuYbZsPAfhFLU4hVIC43xoHPoxdh2TyMlk7EnCJHoAUppHLEnIVQ_8FXUrVS4KlUsaQvBRxWXeLR9/s400/huffman_a.png" width="400" /></a></div>
<div style="text-align: center;">
Figura A</div>
<br />
Ok, mas o que pedia o exercício I da maratona? Para se codificar um texto?<br />
<br />
Quase. O exercício trata-se de uma variação bem criativa da codificação de Huffman, na qual, em vez de lhe passar a frequência das letras para que se monte a árvore, passa-lhe a árvore para que se descubra a frequência das letras.<br />
<br />
O único requisito para se resolver o exercício é ter um conhecimento de como a árvore é montada, para que seja possível atribuir valores consistentes nos nós, de tal modo que a árvore pudesse ser montada pelo algoritmo de Huffman.<br />
<br />
Ok, como ele funciona? No enunciado do exercício há uma explicação do funcionamento do algoritmo de Huffman junto com uma sequência de passos, mas eu vou citar aqui algumas considerações.<br />
<br />
- Entenda por "valor" a frequência de ocorrência do caractere no texto. O valor de 'a' acima seria 3.<br />
<br />
- Todos os caracteres são folhas, por mais que no exercício não nos preocupemos em si com os caracteres, mas sim com o seu valor e seu nível.<br />
<br />
- Os nós que não são folhas são nós criados no decorrer do algoritmo, de tal modo que o seu valor é consequência do valor de ambos os filhos.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgnBbE0R_iJ7dgpSUiYh0UIG438RFz3YV_CTBX__rQDvbtVZtuv5pvFWomq0rMdvWkMo0AiXcNqWhLD0TkhvQP9aq_7zWm89nw4di7LUkJoEUQS1-ms2cpcvzjeZKMwCl5arpWTjoGSvF2e/s1600/huffman_b.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="290" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgnBbE0R_iJ7dgpSUiYh0UIG438RFz3YV_CTBX__rQDvbtVZtuv5pvFWomq0rMdvWkMo0AiXcNqWhLD0TkhvQP9aq_7zWm89nw4di7LUkJoEUQS1-ms2cpcvzjeZKMwCl5arpWTjoGSvF2e/s320/huffman_b.png" width="320" /></a></div>
<div style="text-align: center;">
Figura B</div>
<br />
- Na nossa lista, sempre haverá no mínimo um par de nós no nível mais abaixo da árvore, a não ser que estejamos no último nó (Figura B).<br />
<br />
Vamos ao exercício: Como atribuir consistentemente um valor a um nó folha, de modo que a árvore seja montada da forma especificada? Basta simular o funcionamento do algoritmo!<br />
<br />
Lembre-se que se deseja o menor valor possível paraa soma de todos os nós.<br />
<br />
Digamos que a entrada do exercício seja:<br />
4<br />
1 2 3 3<br />
<br />
A estrutura da árvore ficará assim:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhPjsgTloWYwOx5wnAMp4vSTNPV_ZPgmxXkzd_ikV7XovbBMZNMjV9KaUNRv9FjWfKzzjg8rKOBdICIx8j6EVN2sh5gnDKavnj6r_eGIi8j8fbTGzqSIzoLd-J3Kf_w4uFjaflNyNN7yL5J/s1600/huffman_c.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="190" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhPjsgTloWYwOx5wnAMp4vSTNPV_ZPgmxXkzd_ikV7XovbBMZNMjV9KaUNRv9FjWfKzzjg8rKOBdICIx8j6EVN2sh5gnDKavnj6r_eGIi8j8fbTGzqSIzoLd-J3Kf_w4uFjaflNyNN7yL5J/s320/huffman_c.png" width="320" /></a></div>
<div style="text-align: center;">
Figura C</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
O algoritmo de Huffman cria uma lista com os valores de cada nó, e escolhe os dois com os menores valores para criar um nó pai e construir a árvore. </div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
Está vendo aqueles dois nós no nível 3? Se eles estão lá embaixo, devem ter sido escolhidos primeiro na execução do tal algoritmo de Huffman, e, consequentemente, o valor de seus nós deve ser baixo, bem baixo. Que tal 1?</div>
<div style="text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj_AspnXFhcWDvHCJUjwfReZqb4wuOJCaKEHAJUQTOQv3uSbwdwORcxm_wb_sxooUdlhYAAbGUjmULGZ5JuceVtj5x6UAmxZTdykpscaedzNzZisSqItAlbJ9dopMg06DXyZUUjCPxAD_Z1/s1600/huffman_d.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="190" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj_AspnXFhcWDvHCJUjwfReZqb4wuOJCaKEHAJUQTOQv3uSbwdwORcxm_wb_sxooUdlhYAAbGUjmULGZ5JuceVtj5x6UAmxZTdykpscaedzNzZisSqItAlbJ9dopMg06DXyZUUjCPxAD_Z1/s320/huffman_d.png" width="320" /></a></div>
<div style="text-align: center;">
Figura D</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
O algoritmo de Huffman agora monta-lhes o nó pai, sendo o valor a soma dos nós filhos.</div>
<div style="text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh4JMuodqUzDbntYI1-TsknQwK7Q5R13lPSyClh-QNL3j-SNA-LpenSjxPm1OHH_UabeiJi139xB1UsuOSc2jRR1pkQmJJULu5hwE4G0xR4jJNhR4_n5amkx24fXoZLwfn3ZA1sjpZsE9x-/s1600/huffman_e.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="192" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh4JMuodqUzDbntYI1-TsknQwK7Q5R13lPSyClh-QNL3j-SNA-LpenSjxPm1OHH_UabeiJi139xB1UsuOSc2jRR1pkQmJJULu5hwE4G0xR4jJNhR4_n5amkx24fXoZLwfn3ZA1sjpZsE9x-/s320/huffman_e.png" width="320" /></a></div>
<div style="text-align: center;">
Figura E</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
Os nós folhas são removidos da lista, e o nó pai adicionado. O algoritmo agora irá escolher os dois nós com o menor valor da lista, e continuar sua execução.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
Atente a essa situação da árvore: Que valor poderia ser atribuído ao nó sinalizado de forma que pudéssemos conduzir o algoritmo de Huffman a montar a árvore como planejamos?</div>
<div style="text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjzW6rUNdJxzWxz7MoICJlxSb9Kh1_E6RyTDslnuuLcudwDIcl7JTBt3nOEqHE5CCSyjsebj9lvi-G06WAI119ce2UxU5F1eQi5tbB745aK5xx7KONOnjhDzLvEAK3wCbS7pAIhwKqqGvgh/s1600/huffman_f.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjzW6rUNdJxzWxz7MoICJlxSb9Kh1_E6RyTDslnuuLcudwDIcl7JTBt3nOEqHE5CCSyjsebj9lvi-G06WAI119ce2UxU5F1eQi5tbB745aK5xx7KONOnjhDzLvEAK3wCbS7pAIhwKqqGvgh/s1600/huffman_f.png" /></a></div>
<div style="text-align: center;">
Figura F</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
Se atribuíssimos um valor muito baixo, talvez o algoritmo não tivesse se comportado conforme planejávamos até aquele momento. Por exemplo, se atribuíssemos o valor 2, o algoritmo, no passo anterior, não teria escolhido os nós de valor 3 e 5, mas sim os nós com valor 2 e 3, mudando a estrutura da árvore que esperávamos.</div>
<div style="text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdXiznhSjIU30pz_KIYhABUmV6s_sVnKlBGor99QS3hs4j34bigUxrkNxFKtNkdmyuu_Q5q7MyvmUqT55lglWH2dm8ZE8x5ZVQqRLCEAXv2XCotgc9HO4MY7mo4PMYG3roPlsNXnalyaTo/s1600/huffman_g.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjdXiznhSjIU30pz_KIYhABUmV6s_sVnKlBGor99QS3hs4j34bigUxrkNxFKtNkdmyuu_Q5q7MyvmUqT55lglWH2dm8ZE8x5ZVQqRLCEAXv2XCotgc9HO4MY7mo4PMYG3roPlsNXnalyaTo/s1600/huffman_g.png" /></a></div>
<div style="text-align: center;">
Figura G</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
Qual seria o menor valor que eu poderia colocar ali então?</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
O resto eu deixo com vocês.</div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2697059789481443605.post-69248485469891605762013-10-30T01:34:00.000-02:002013-10-30T01:34:09.895-02:00O Famoso Campo MinadoJá ouviu falar desse jogo?<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEinHTkPNPWsz5k7sP0BRPr0aUb0S_8ic3ABH8Pnm-fCDugF6UAXe4whzpBHJuy7h7QHz39a-0h6s6qHPaOIV2OMgC2kv5DdCh4Neea1Q-uDzf3UGM1K4iyvjIIUJ8PPDWrVq3bfvKgAqN10/s1600/CampoMinado1.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="287" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEinHTkPNPWsz5k7sP0BRPr0aUb0S_8ic3ABH8Pnm-fCDugF6UAXe4whzpBHJuy7h7QHz39a-0h6s6qHPaOIV2OMgC2kv5DdCh4Neea1Q-uDzf3UGM1K4iyvjIIUJ8PPDWrVq3bfvKgAqN10/s400/CampoMinado1.jpg" width="400" /></a></div>
<br />
Se você já teve um dia ocioso no nosso amigo Windows, acho que sim.<br />
<br />
Trata-se de um jogo <strike>nerd</strike> desafiante, que envolve observação, lógica e um pouco de sorte, todos os requisitos necessários para ser um bom maratonista.<br />
<br />
Foi pensando nele que resolvi escrever mais um exercício, o qual você pode resolver aqui:<br />
<a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1480">http://www.urionlinejudge.com.br/judge/pt/problems/view/1480</a><br />
<br />
O interessante do Campo Minado é que ele é considerado um jogo da categoria <b>NP-completo</b>, ou seja, em alguns casos de jogo não há como escolher ou verificar se é possível encontrar todas as minas sem se basear em tentativas, sorte, ou os famosos <b>Algoritmos Não Determinísticos</b> (Non Deterministic), os quais podem te render uma boa <b>grana</b> se você desenvolvê-los.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2697059789481443605.post-55773398794013738832013-10-13T11:31:00.001-03:002013-10-30T01:34:20.794-02:00Ajude seu General“Porque recalcular um caminho do
início, se eu já sei metade?”, eis a questão que justifica o
post de hoje.<br />
<br />
<div style="margin-bottom: 0cm;">
Para os interessados, eu escrevi um
<b>exercício</b>, e o mesmo está disponível para ser resolvido no portal
do URI, no seguinte link:</div>
<div style="margin-bottom: 0cm;">
<a href="http://www.urionlinejudge.com.br/judge/pt/problems/view/1479">http://www.urionlinejudge.com.br/judge/pt/problems/view/1479</a></div>
<div style="margin-bottom: 0cm;">
<br /></div>
<div style="margin-bottom: 0cm;">
Ajude seu General foi um exercício
escrito com o propósito de estimular a implementação de formas
mais eficientes de se calcular o famoso caminho mínimo em um grafo,
dado um devido <b>contexto</b>.</div>
<div style="margin-bottom: 0cm;">
<br /></div>
<div align="CENTER" style="margin-bottom: 0cm;">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi9P5IjCB-JK4NVHOFUSG-VCEWnaToGhiLspN-cOgCo1yPxVdXJn3qMyJRds0ZvQZgj2NLOFJOz-4yS_y63Mmbr7b2hwkXz-Vyv4NPxrHQutYfoQHwpAz3hJTrdrJ-zGxVDBwDu5o0nqhEH/s1600/figuraC.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="134" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi9P5IjCB-JK4NVHOFUSG-VCEWnaToGhiLspN-cOgCo1yPxVdXJn3qMyJRds0ZvQZgj2NLOFJOz-4yS_y63Mmbr7b2hwkXz-Vyv4NPxrHQutYfoQHwpAz3hJTrdrJ-zGxVDBwDu5o0nqhEH/s320/figuraC.png" width="320" /></a></div>
<br />
<b>Figura A</b><span id="goog_1577736910"></span></div>
<div style="margin-bottom: 0cm;">
<br />
<div style="margin-bottom: 0cm;">
Todos estamos acostumados com o contexto padrão: Temos um grafo, e nos é requisitado descobrir qual é o caminho mínimo do vértice <b>S</b> até o vértice <b>D</b> (Figura A).</div>
<div style="margin-bottom: 0cm;">
Para isso usamos os nossos velhos amigos DFS, BFS, Bellman-Ford, Dijkstra, entre outros.</div>
<br /></div>
<div style="margin-bottom: 0cm;">
Mas e se o contexto mudar um pouco? E
se o nosso grafo fosse <b>dinâmico</b>? E se as arestas pudessem sumir ou
aparecer? Eis o contexto <b>DSSSP</b> (Dynamic Single Source Shortest Path).</div>
<div style="margin-bottom: 0cm;">
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjIb7hSQkTcBR_2KNGeEBe2QUa_zUGj32cnpj6Ao6uzCMTwUJT8gi-nMjSl4V9Gy4VZC2Oy3jL6XcHirtxgMHO9OObcO8IInawRPFa5JsYyZqLyr-G41sSO-O54w2TIdYXlK_c4oLNEKYxC/s1600/figuraD.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="144" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjIb7hSQkTcBR_2KNGeEBe2QUa_zUGj32cnpj6Ao6uzCMTwUJT8gi-nMjSl4V9Gy4VZC2Oy3jL6XcHirtxgMHO9OObcO8IInawRPFa5JsYyZqLyr-G41sSO-O54w2TIdYXlK_c4oLNEKYxC/s320/figuraD.png" width="320" /></a></div>
<div style="text-align: center;">
<br /></div>
<div style="text-align: center;">
<b>Figura B.1</b></div>
<br /></div>
<div style="margin-bottom: 0cm;">
Conforme ilustrado pela Figura B.1, a
remoção de uma aresta pode <b>inutilizar</b> nosso antigo caminho mínimo,
nos forçando a encontrar outro, assim como a inserção de uma nova
aresta (Figura B.2) pode nos apresentar um <b>novo</b> caminho, nos forçando a aos menos
tentar encontrá-lo.</div>
<div style="margin-bottom: 0cm;">
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjQuf0Z65uFiNF5gLGBkSXE8seDPw_LBrcTMIicZAWO51jtkXOCJlTiK1ly3i21W294ANeghkro-EBxcAXrWxY9aHaSaxkfzL5KrY_pALSpmyKsA6XzPvS9Ai9cDKcsguR6ww0BwhDzPT-y/s1600/figuraE.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="141" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjQuf0Z65uFiNF5gLGBkSXE8seDPw_LBrcTMIicZAWO51jtkXOCJlTiK1ly3i21W294ANeghkro-EBxcAXrWxY9aHaSaxkfzL5KrY_pALSpmyKsA6XzPvS9Ai9cDKcsguR6ww0BwhDzPT-y/s320/figuraE.png" width="320" /></a></div>
<div style="text-align: center;">
<br /></div>
</div>
<div align="CENTER" style="margin-bottom: 0cm;">
<b>Figura B.2</b></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
A primeira vista, não
parece nos restar escolha: devemos <b>recalcular</b> todo nosso grafo,
sempre que uma aresta é inserida ou removida, pois só assim podemos
ter certeza que o nosso caminho mínimo é de fato o caminho mínimo.</div>
<div align="LEFT" style="margin-bottom: 0cm;">
Uma coisa é clara: <b>Tal
solução é cara.</b></div>
<div align="LEFT" style="margin-bottom: 0cm;">
E mais: <b>Muito cara.</b></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiMUzkC_Br0BWccr8pgGfQmc5Rj9b9ZOcb-9OdVS9FEUB_As2-6qLB8lYotGz_bAGMvd2Vcq9Yx4wCMs5xP3ajHnnZigg8ufF3WyNqkPweBEhII0BaPR-ryfhI8oM8v5xNQg6kjX-Bx0bbO/s1600/figuraB.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="143" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiMUzkC_Br0BWccr8pgGfQmc5Rj9b9ZOcb-9OdVS9FEUB_As2-6qLB8lYotGz_bAGMvd2Vcq9Yx4wCMs5xP3ajHnnZigg8ufF3WyNqkPweBEhII0BaPR-ryfhI8oM8v5xNQg6kjX-Bx0bbO/s400/figuraB.png" width="400" /></a></div>
<div style="text-align: center;">
<br /></div>
</div>
<div align="CENTER" style="margin-bottom: 0cm;">
<b>Figura C</b></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
Note que ao remover a
aresta em <b>vermelho</b>, temos que recalcular o caminho mínimo para todos
os vértices, em especial para o vértice <b>D</b>, entre os <b>N</b> vértices do
grafo. Ou seja, custo <b>N</b> (multiplicado pela complexidade do seu
algoritmo preferido).</div>
<div align="LEFT" style="margin-bottom: 0cm;">
Note ainda que tal aresta
<b>não compunha</b> o caminho mínimo (caminho em <b>azul</b>). Poxa, fomos
enganados! Recalculamos todo o nosso grafo, e nem precisávamos!</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
Uma solução mais viável
seria tentar “<b>isolar</b>” um conjunto de vértices que realmente
fossem “<b>afetados</b>” pela inserção/remoção, conforme ilustrado
na Figura D.</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEih4H5HIyzxltGpSwi7tFI8yS__iUcmxE81cAP6Z3hG6PTcqqPgTMfeAd8Jwt-gEsYzcBs-nb_GXHBQqided-W64WMETS-9W75BXBwaaQAy6FhL7-cF5eHIQvqCaBds_vx5QFJDzzcspyxg/s1600/figuraA.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="106" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEih4H5HIyzxltGpSwi7tFI8yS__iUcmxE81cAP6Z3hG6PTcqqPgTMfeAd8Jwt-gEsYzcBs-nb_GXHBQqided-W64WMETS-9W75BXBwaaQAy6FhL7-cF5eHIQvqCaBds_vx5QFJDzzcspyxg/s400/figuraA.png" width="400" /></a></div>
<div style="text-align: center;">
<br /></div>
</div>
<div align="CENTER" style="margin-bottom: 0cm;">
Figura D</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
O fato de não haver uma
aresta direcionada saindo do conjunto <b>B</b> em direção ao conjunto <b>A</b>
torna fácil perceber que há uma imensa diferença entre tais dois
grupos:
</div>
<div align="LEFT" style="margin-bottom: 0cm;">
a) O caminho mínimo para
qualquer que seja o vértice do conjunto <b>A</b> não foi alterado.</div>
<div align="LEFT" style="margin-bottom: 0cm;">
b) O caminho mínimo para
qualquer que seja o vértice do conjunto <b>B</b> pode ou não ter sido
alterado, assim como o caminho mínimo até o vértice <b>D</b>.<br />
Resumindo: Porque recalcular um caminho do início, se eu já sei metade?</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
Isolamos, então, um
conjunto de vértices “<b>afetados</b>” pela remoção de uma aresta, e
um recálculo sobre tal conjunto me parece uma escolha bem prudente.</div>
<div align="LEFT" style="margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
A brecha foi aberta, basta
explorá-la. Para isso recomendo lerem o artigo dos cientistas da
computação Ramalingam e Reps, que descreve um algoritmo que aborda
o tema DSSSP, e resolve o problema descrito com eficácia.</div>
<a href="http://pages.cs.wisc.edu/~ramali/jl-algorithms.html">http://pages.cs.wisc.edu/~ramali/jl-algorithms.html</a>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2697059789481443605.post-59411744464487515212013-09-25T22:29:00.001-03:002014-09-26T21:39:03.908-03:00Soluções da Fase Regional da Maratona 2013Venho aqui divulgar o pdf, escrito por Gabriel Dalalio (ex-maratonista e responsável por colaborar na elaboração dos exercícios desse ano) contendo dicas e resoluções dos exercícios da fase regional de 2013.<br />
<br />
Entre os tópicos de estudo estão: Ad-Hoc (A e E), Árvore de Segmentos (B), Grafos (C e J), Força Bruta (D), Sort ou Permutação (G), Exponenciação de Matriz (H), Programação Dinâmica (I) e Árvore Geradora Mínima (com Lowest Common Antecestor) (J).<br />
<br />
Tudo isso com mais detalhes aqui:<br />
<a href="https://www.dropbox.com/s/q4aa8g0zctzbwnq/solucoes_regional_2013.pdf?dl=0">https://www.dropbox.com/s/q4aa8g0zctzbwnq/solucoes_regional_2013.pdf?dl=0</a><br />
<br />
O pdf está bem organizado e muito bem explicado, portanto se você tem o objetivo de fazer todos os exercícios da prova (tal como eu), não deixe de dar uma olhada.<br />
<br />
Lembrando que todos os exercícios da Fase Regional já estão disponíveis no portal do <a href="http://www.urionlinejudge.com.br/judge/">URI Online Judge</a>.Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-2697059789481443605.post-46475859609300083592013-09-23T17:43:00.001-03:002013-09-25T22:30:20.760-03:00Khan AcademyMaratonas de programação costumam exigir uma boa noção de matemática dos participantes, e por mais que os exercícios relacionados com matemática e geometria envolvam uma pequena fração da prova (geralmente 10%, ou 20% da prova), a resolução de tais exercícios pode decidir o resultado final.<br />
<br />
Uma vez que não haja saída, só nos resta estudar matemática <b>o/</b>.<br />
<br />
Encontrei faz pouco tempo esse ótimo site, <a href="https://www.khanacademy.org/">Khan Academy</a>, com video-aulas que envolvem uma área muito ampla da matemática, tal como álgebra, geometria, trigonometria, cálculo, álgebra linear, e mais alguns tópicos.<br />
<br />
Se você entende bem inglês, aconselho assistir os vídeos originais, explicados pelo criador do site, Sal, neste link:<br />
<a href="https://www.khanacademy.org/">https://www.khanacademy.org</a>/<br />
<br />
Há também o esforço voluntário de alguns brasileiros dublando os vídeos originais. Então se você prefere assistir os vídeos no seu idioma nativo, siga este link:<br />
<a href="http://www.fundacaolemann.org.br/khanportugues/">http://www.fundacaolemann.org.br/khanportugues/</a>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2697059789481443605.post-27410112964398398732013-09-02T14:21:00.000-03:002013-09-24T13:30:34.948-03:00Guerreiros Etruscos Nunca Jogam XadrezExercício: <a href="http://www.urionlinejudge.com.br/judge/problems/view/1308">http://www.urionlinejudge.com.br/judge/problems/view/1308</a><br />
<br />
Com um pouco de observação, notamos que o exercício utiliza o conceito de progressão aritmética.<br />
<br />
<span style="font-family: inherit;">De acordo com a wikipédia, "<span style="background-color: white;"><span style="line-height: 19.1875px;">Uma </span><b style="line-height: 19.1875px;">progressão aritmética</b><span style="line-height: 19.1875px;"> (abreviadamente, </span><b style="line-height: 19.1875px;">P. A.</b><span style="line-height: 19.1875px;">) é uma </span>sequência numérica<span style="line-height: 19.1875px;"> em que cada termo, a partir do segundo, é igual à </span>soma<span style="line-height: 19.1875px;"> do termo anterior com uma </span>constante<span style="line-height: 19.1875px;"> </span><img alt="r." class="tex" src="http://upload.wikimedia.org/math/5/5/0/5502ba4322d9a442426f01433bf092ff.png" style="border: none; line-height: 19.1875px; margin: 0px; vertical-align: middle;" /></span>", sendo 1 a constante r utilizada no exercício.</span><br />
<br />
Note que a primeira linha contém um guerreiro, a segunda linha contém dois guerreiros (primeira linha mais um), na terceira linha temos três guerreiros (segunda linha mais um), e assim por diante.<br />
O exercício ainda nos diz qual é o termo para cada linha: na linha <b>i</b>, temos <b>i</b> guerreiros.<br />
<br />
<b>Ok</b>, mas o que o exercício pede então?<br />
Ele nos pede para responder quantas linhas são necessárias para que se contenham <b>N</b> guerreiros.<br />
<br />
Um simples termo não pode responder tal questão, pois sabemos apenas que a linha <b>i</b> comporta <b>i</b> guerreiros, mas não sabemos quanto à soma das <b>i-1 </b>linhas anteriores.<br />
<br />
<b>Poderíamos</b> sair somando em uma variável auxiliar o valor <b>i</b>, começando com <b>i = 1</b> até que a soma ultrapasse o desejado, e então <b>i</b> seria a resposta.<br />
Porém essa é a solução <b>força</b> <b>bruta</b>, e precisamos de algo mais eficaz, visto que <b>N</b> <= 10¹⁸.<br />
<br />
Se pesquisarmos na internet, encontraremos uma fórmula que nos diz a soma dos n primeiros termos de uma determinada progressão aritmética, que seria a seguinte:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://upload.wikimedia.org/math/1/7/c/17ce9fea1fb81790c7dd8660cff3f8d5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://upload.wikimedia.org/math/1/7/c/17ce9fea1fb81790c7dd8660cff3f8d5.png" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
Onde <b>a</b>i se referencia ao termo <b>i</b> (no nosso caso, quantidade de guerreiros na linha <b>i</b>)<b>.</b><br />
<br />
<b>Por exemplo</b>, se quisermos saber a soma das 5 primeiras linhas de guerreiros, faríamos o seguinte:<br />
<br />
<b>n</b> = 5<br />
<b>a</b>1 = 1 (temos 1 guerreiro na linha 1)<br />
<b>a</b>5 = 5 (temos 5 guerreiros na linha 5)<br />
<br />
<b>S</b>5 = (5 * (1 + 5) ) / 2<br />
<b>S</b>5 = 30 / 2 = 15<br />
<br />
<b>Ok</b>, temos 15 guerreiros nas 5 primeiras linhas, mas o que o exercício pede é justamente o contrário: Visto que eu tenho <b>N</b> guerreiros, quantas linhas foram necessárias?<br />
<br />
<b>Pensem</b>, sabemos o número de guerreiros (<b>Sn</b>), sabemos quantos guerreiros há na linha 1 (<b>a1</b> = 1), só não sabemos quantas linhas são necessárias (<b>n</b>), e quantos guerreiros há na linha <b>n </b>(<b>an</b>).<br />
<br />
Se aplicarmos tudo isso na fórmula... Bom, agora é com vocês.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2697059789481443605.post-37033854720942359112013-08-25T12:47:00.000-03:002013-08-25T12:47:42.438-03:00Abstraindo um problemaOs enunciados dos exercícios escondem o tesouro, e você deve estar atento as pistas (mas apenas as importantes).<br />
<br />
Nesse post vou citar um exemplo de como abstrair um exercício, ou seja, ignorar todas as informações inúteis e saber identificar os pontos chaves que nos levam à resolução. Isso inclui identificar pistas "falsas" ou "desnecessárias".<br />
<br />
O exercício que vou usar como exemplo aqui é o <b>Fechem as portas!</b> (<a href="http://www.urionlinejudge.com.br/judge/problems/view/1371">http://www.urionlinejudge.com.br/judge/problems/view/1371</a>).<br />
<br />
Antes de continuar, leiam o enunciado do exercício, e tirem suas conclusões iniciais.<br />
<blockquote class="tr_bq">
Considerando que todas as portas estão inicialmente fechadas (todos os descendentes fecham as portas antes de descer para o jardim) e que cada descendente entra exatamente uma vez na mansão (a confusão é tão grande que não sabemos em que ordem), quais portas estarão abertas após a entrada de todos os descendentes na mansão?</blockquote>
<b>Pista falsa</b>: "(a confusão é tão grande que não sabemos em que ordem)".<br />
A ordem em que eles entram não faz a menor diferença, visto que todos vão entrar e vão abrir (ou fechar) suas respectivas portas. Veja, se o estado da porta 3 vai ser trocado pelo descendente 1 e 3, nesta ordem, temos um total de duas trocas, e se vai ser trocado pelo descendente 3 e 1, nesta ordem, temos ainda um total de duas trocas, ou seja, a ordem é indiferente, e o total é o mesmo.<br />
<br />
<b>Objetivo</b>: Descobrir quantas portas terminarão abertas.<br />
Solução? Força bruta? Não! Veja, temos um valor máximo de 25milhões de portas e descendentes, um valor extremamente alto para se pensar em força bruta.<br />
<br />
<b>Pensem comigo</b>: uma porta ou está fechada, ou está aberta, e seu estado troca de um para o outro apenas. Se inicia fechada, com uma troca de estados vai para aberta, e com duas volta para fechada. Se continuarmos nesse ritmo, notaremos que um número par de trocas de estados faz com que a porta termine fechada, e um número ímpar de trocas de estados faz com a porta termine aberta.<br />
<br />
<b>A porta número 3</b> vai ter seu estado trocado por dois descendentes. Vimos que a ordem não importa, o que nos importa mesmo é o número de vezes em que ela vai ter seu estado trocado. No caso da porta número 3, duas vezes. Como vimos no parágrafo anterior, quando o estado da porta é trocado um número par de vezes, ela terminará fechada, portanto temos uma resposta: <b>terminará fechada</b>.<br />
<br />
<b>Abstração</b>: Descobrir o número Q de divisores de um valor N, e, com base nesse valor Q, imprimir N ou não.<br />
<br />
<b>Exemplo</b>: Vamos descobrir o número de divisores dos valores de 1 até 10.<br />
<b>N</b> <b>Q</b><br />
1: 1 = 1<br />
2: 1, 2 = 2<br />
3: 1, 3 = 2<br />
4: 1, 2, 4 = 3<br />
5: 1, 5 = 2<br />
6: 1, 2, 3, 6 = 4<br />
7: 1, 7 = 2<br />
8: 1, 2, 4, 8 = 4<br />
9: 1, 3, 9 = 3<br />
<br />
<b>Solução</b>: Os valores <b>N</b> tal que o número <b>Q</b> total de divisores de <b>N</b> é impar <b>-> 1, 4 e 9.</b><br />
<b><br /></b>
<b>Abstraído o problema</b>, resta encontrar uma forma eficaz de descobrir esse valor Q, mas com um pouco de observação, é fácil encontrar o padrão. Vou deixar essa tarefa pra vocês.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2697059789481443605.post-70356479458294286122013-07-28T02:29:00.002-03:002013-07-28T02:29:30.768-03:00A piada mais nerd que já conteiLá estávamos nós, minutos após o término da Maratona Catarinense de Programação, em volta de um coquetel oferecido pela Linx, patrocinadora do evento, aproveitando para recuperar as energias.<br />
Após 4 horas de prova (se não me engano), todos estavam exaustos e famintos, e eis que o coquetel estava sendo devorado em velocidade espantosa pelos maratonistas.<br />
<br />
Ao observar a cena, perguntei a meu amigo: Você sabe que algoritmo eles estão usando para comer nessa velocidade?<br />
Após um aceno de dúvida de meu amigo, respondi:<br />
Um algoritmo guloso!<br />
<br />
=D<br />
<br />
Bom, é isso, essa foi a piada haha.<br />
Se pensar bem, foi um trocadilho, e dos ruins, mas eu ainda dou risada quando lembro.<br />
<br />
Até mais.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2697059789481443605.post-34969249248640325582013-07-06T11:27:00.004-03:002013-09-27T17:07:35.972-03:00Fase Final da MaratonaGostaria de ressaltar aqui os resultados da fase final da maratona, que aconteceu nesse dia 03 (03/07/13), onde os times brasileiros obtiveram os seguintes resultados:<br />
<br />
"Resultados finais: UFMG, POLI e ICMC com 1, UNICAMP com 3 em 69 lugar. UFPE com 5 na posição 43. ITA com 5 na posição 42! ITA é o Campeão Latino-americano!"<br />
Retirado de: <a href="https://www.facebook.com/maratona">https://www.facebook.com/maratona</a><br />
<br />
Parabéns aos brasileiros envolvidos nessa fase da competição, é um grande incentivo para os demais.<br />
<br />
Se você gostaria de resolver os problemas que foram propostos na maratona, acesse esse site:<br />
<a href="https://icpc.kattis.com/">https://icpc.kattis.com/</a><br />
<br />
E confira também os vídeos que o pessoal da ICPC divulgou, dando algumas dicas de como resolver estes mesmos problemas:<br />
<a href="http://www.youtube.com/user/ICPCNews/videos">http://www.youtube.com/user/ICPCNews/videos</a><br />
<br />
E se preparem. A fase regional da maratona está chegando.<br />
As incrições regulares estão abertas até dia 29/07.<br />
Após esse prazo, o preço sobe um pouco, com o prazo até dia 31/08.<br />
<br />
É só isso que tenho a dizer.<br />
Até mais.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2697059789481443605.post-71616147665103308352013-05-25T21:09:00.002-03:002013-05-25T21:09:51.763-03:00Maratona Catarinense de ProgramaçãoEae, tudo certo?<br />
<br />
Venho aqui divulgar, um pouco tarde, talvez, a Maratona Catarinense de Programação, que acontecerá em Joinville, Santa Catarina.<br />
Se você é do Sul, ou próximo, ou nem um pouco perto, venha participar.<br />
E apresse-se, pois as vagas estão acabando!<br />
<br />
Acontecerá no dia 15/06/13.<br />
<br />
Mais informações em:<br />
<a href="http://www2.joinville.udesc.br/~esp7maratona/">http://www2.joinville.udesc.br/~esp7maratona/</a>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2697059789481443605.post-29224373567954326462013-05-15T16:34:00.000-03:002013-05-15T16:34:07.596-03:00Gerador de Casos de TesteUm dos grandes desafios envolvidos em resolver um exercício da maratona de programação é pensar em um caso de teste onde seu programa vai falhar.<br />
Os casos de teste oferecidos na descrição do exercício geralmente cobrem a parte mais simples e superficial do mesmo, mas quando chega a hora de submeter o código, ele deve passar por casos de testes gigantescos e complexos, os quais você nem de longe tratou.<br />
<br />
Nesse post vou dar um breve exemplo de como criar um gerador de casos de teste, o qual pode lhe ajudar a testar o programa e verificar por si mesmo em quais casos seu programa está falhando.<br />
<br />
Aqui está o código que eu montei para exemplificar esse post:<br />
<a href="https://github.com/crbonilha/codes/blob/master/Exemplo%20Gerador%20Casos%20de%20Teste">https://github.com/crbonilha/codes/blob/master/Exemplo%20Gerador%20Casos%20de%20Teste</a><br />
<br />
(Linha 6 do código):<br />
Caso esteja programando na linguagem C ou C++ (meu caso), será necessário utilizar alguns metodos responsáveis por manipular arquivos externos, tais como arquivos .txt, ou arquivos sem extensão alguma, mas que contenham nele apenas valores que serão usados no seu programa.<br />
Esses metodos manipulam variáveis do tipo FILE, que serão responsáveis por representar seu arquivo externo. Quem ainda não tem muita familiaridade com essa abordagem, procure estudar algo na internet, em especial o método "fopen()" e "fprintf()", que, para o nosso caso, é mais do que o suficiente.<br />
<br />
Voltando ao contexto da maratona, para que você pense em como gerar um caso de teste, primeiro você tem que entender a "hierarquia" de cada caso de teste, por exemplo, no exercicio Bilhetes Falsos (<a href="http://www.urionlinejudge.com.br/judge/problems/view/1318">http://www.urionlinejudge.com.br/judge/problems/view/1318</a>), cada caso de teste contém dois inteiros, N e M, e logo após, M inteiros. Seu gerador será responsável por gerar os dois inteiros iniciais (N e M), e logo após, M inteiros. Sim, é bobagem, mas é importante (Linhas 15 e 21).<br />
Outro detalhe que pode passar em branco é que dentre todos os M valores gerados, todos devem estar no intervalo de 1 a N, portanto cuidado na hora de chamar o método de valores aleatórios (Linha 19).<br />
<br />
Eu costumo deixar a parte do N e M por minha conta (Linha 13), assim eu decido se quero um caso de teste grande ou pequeno, porém esses mesmos valores poderiam facilmente serem gerados aleatoriamente, como os outros.<br />
<br />
Ok, após todos os valores gerados, basta adaptar seu programa que resolve o exercício para ler as entradas do arquivo de teste que você gerou, em vez de ler da entrada padrão como estamos acostumados. Para isso estudem o método "fscanf()".<br />
<br />
Agora é possível criar milhares de casos de teste e fazer seu programa rodar todos em segundos. A última parte é saber identificar, dentre milhares de saidas, qual está errada. Restam-lhe duas alternativas: na internet é possivel encontrar os casos de teste de entrada e suas saidas utilizados nas maratonas anteriores, portanto basta encontrá-los e compará-los ao teu; o site com juiz online do URI tem uma ferramenta chamada toolkit, e com ele é possível entregar um caso de teste gerado por você e verificar qual seria a saída de um programa que está funcionando corretamente.<br />
<br />
Obviamente, ambas as formas de comparar a saida com algum recurso da internet não lhe será útil na hora da maratona, porém bugs nos quais o seu programa aparentemente para de funcionar, ou estoura o tempo limite, podem ser visivelmente notados com esse tipo de abordagem.<br />
<br />
A ferramenta está aí, basta saber quando e como usá-la...Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2697059789481443605.post-19425089184277250502013-05-12T15:26:00.000-03:002013-05-12T15:26:09.509-03:00Curso do MITEssa semana dei de cara com um ótimo curso do MIT, disponibilizado online e o melhor, de graça.<br />
<br />
Tratam-se de aulas dadas para um grupo de estudantes do MIT, que cobrem tópicos da ciência da computação, tal como algoritmos clássicos, estruturas de dados, paradigmas de programação, entre outros. As aulas foram gravadas e disponibilizadas no site do MIT, neste link:<br />
<a href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/">http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/</a><br />
<br />
Há também algum conteúdo na página, tal como alguns exercícios complementares, notas dos autores, e se não me engano, alguns testes.<br />
<br />
Os vídeos estão em inglês, porém caso você não entenda o idioma, o youtube consegue traduzir a fala e ativar legendas. É claro que a legenda automática não é perfeita, mas já passou da hora de você estudar inglês, não? Não há desculpa para não falar inglês hoje em dia, visto que boa parte do conteúdo de qualidade está disponibilizado em inglês, o "idioma universal".<br />
<br />
Bom, é isso, estudem!Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2697059789481443605.post-18054213821509156972013-05-05T22:57:00.002-03:002013-05-05T22:57:56.525-03:00#10 UpdateEae, como estão?<br />
<br />
Vim fazer um post rápido só pra anunciar que cheguei a marca de 100 exercícios resolvidos no site URI. Isso mesmo, uma centena deles, resolvidos.<br />
<br />
Ainda não conhece o URI? Veja o post que fiz sobre ele aqui: <a href="http://crbonilha.blogspot.com.br/2013/03/e-maratona.html">http://crbonilha.blogspot.com.br/2013/03/e-maratona.html</a><br />
<br />
Falta pouco para a maratona, então bora estudar.<br />
<br />
Quem precisar de mim, estarei semi-ativo no <a href="http://www.urionlinejudge.com.br/forum/">fórum do URI</a>.<br />
<br />
Até mais.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2697059789481443605.post-33863994089757035142013-04-28T22:53:00.000-03:002013-04-28T22:53:10.656-03:00As famosas PilhasVocê já ouviu falar de pilhas? (me refiro a estrutura de dados)<br />
<br />
A estrutura de dados pilha pode parecer simples e inofensiva, porém em certos contextos, principalmente em problemas específicos da maratona de programação, a implementação de uma pilha pode ser fatal.<br />
Um exercício aparemente difícil se torna fácil com uma pilha.<br />
<br />
Uma prova? O exercício Ácido Ribunocléico Alienígena é um problema que caiu na maratona alguns anos atrás, e é um dos tópicos mais acessados deste blog, por viajantes do google a procura de resoluções do mesmo. Na época, eu não conhecia a implementação em pilhas, e nem eu lembro como resolvi, mas garanto que hoje eu resolveria algo parecido em metade do tempo só implementando uma pilha.<br />
<br />
O link do exercicio, caso esteja curioso, é esse: <a href="http://www.urionlinejudge.com.br/judge/problems/view/1242">http://www.urionlinejudge.com.br/judge/problems/view/1242</a><br />
<br />
Meu objetivo não é explicar aqui como funciona o conceito de pilhas, mas sim dizer que esse conceito existe.<br />
Tem bastante material na internet, então procurem um pouco, e saibam que esse exercício pode ser resolvido, de forma ridiculamente fácil, utilizando pilhas.<br />
<br />
Alguns outros exercícios que utilizam pilhas podem ser encontrados no site URI, na aba de estrutura de dados dos problemas.<br />
<br />
Por hoje é só, estudem!Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2697059789481443605.post-25863560320257007032013-04-22T08:33:00.001-03:002013-04-22T08:33:37.400-03:00O Algoritmo de DijkstraJá ouviu falar do algoritmo de Dijkstra?<br />
<br />
O algoritmo de Dijkstra é famoso por resolver o problema de caminhos mínimos em um tempo bem considerável. Haviam outros algoritmos com o mesmo objetivo antes dele, e surgiram mais após ele, mas em questão de complexidade de implementação e testes com o pior caso, ele continua sendo o mais conveniente.<br />
<br />
Mas vamos ao que interessa. Em maratonas de programação, é crucial conhecer esse algoritmo e saber implementá-lo em pouco tempo, pois, como diz Steven Halim (uma espécie de gênio, reconhecido por participações na maratona de programação), não basta "lembrar do algoritmo, mas não saber implementá-lo". Um bom maratonista conhece N algoritmos e implementa todos em uma velocidade alta, para que não haja perda de tempo com coisas simples, e sobre mais tempo para os problemas mais difíceis da maratona.<br />
Portanto, você que diz conhecer o algoritmo, se desafie a implementá-lo em em menos de 5 minutos, e caso não consiga, pratique.<br />
<br />
Agora, para quem não conhece, trate de estudar. Esse algoritmo cai em muitos exercícios, e sua lógica é muito peculiar, uma vez que abre um novo ponto de vista para quem o aprende.<br />
<br />
Aqui estão alguns exercícios do site URI que envolvem o algoritmo Dijkstra:<br />
Fácil:<br />
<a href="http://www.urionlinejudge.com.br/judge/problems/view/1148">http://www.urionlinejudge.com.br/judge/problems/view/1148</a><br />
Médio:<br />
<a href="http://www.urionlinejudge.com.br/judge/problems/view/1123">http://www.urionlinejudge.com.br/judge/problems/view/1123</a><br />
Difícil:<br />
<a href="http://www.urionlinejudge.com.br/judge/problems/view/1085">http://www.urionlinejudge.com.br/judge/problems/view/1085</a><br />
<br />
Nota:<br />
Nenhum problema vai estampar na cara que utiliza o algoritmo de Dijkstra, e raramente vai ser uma simples implementação de Dijkstra. Um bom problema vai envolver um pouco de interpretação de contexto, e pequenas modificações em como os grafos são representados e corridos. As vezes também será necessário uma modificação no próprio algoritmo de Dijkstra, como no terceiro caso.<br />
<br />
Nota 2:<br />
O algoritmo de Dijkstra faz a busca pelo grafo. A forma como o grafo é montado, é outra história. Nos primeiros dois exercícios citados, os grafos são montados com peculiaridades diferentes, porém o Dijkstra funciona da mesma maneira nos dois casos, uma vez que o grafo está montado.<br />
Em relação ao terceiro exercício, o grafo fica ainda mais complexo, e acredito que uma modificação no Dijkstra se faça necessário. Não tenho certeza, pois ainda não resolvi, mas me disseram que o Dijkstra resolve, então vamos lá.<br />
<br />
Por hoje é isso, estudem o Dijkstra, é importante, e no Google tem material sobrando.<br />
Até mais.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2697059789481443605.post-5788801571086686052013-04-12T13:23:00.000-03:002013-04-12T13:23:19.398-03:00Projeto adiado!<div class="separator" style="clear: both; text-align: left;">
</div>
<div class="separator" style="clear: both; text-align: left;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhbxR76MZP0WlHaB8eJZGxzGl4jip5YPd037WZ1OvlbaTraCP3aNu1GMQjxVSomyjnxWy73sbnZEhKs2sCaPr_Dtv_Ug7fXnhf-_d2MaQpuQDW1cNAxlAsyadlM7a417dp3XYbbI_0floJS/s1600/rpg6_1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhbxR76MZP0WlHaB8eJZGxzGl4jip5YPd037WZ1OvlbaTraCP3aNu1GMQjxVSomyjnxWy73sbnZEhKs2sCaPr_Dtv_Ug7fXnhf-_d2MaQpuQDW1cNAxlAsyadlM7a417dp3XYbbI_0floJS/s1600/rpg6_1.png" /></a></div>
<br />
Venho, por meio desse post, anunciar que o desenvolvimento do projeto de RPG foi adiado..<br />
Não sei, eu geralmente me saio bem em um projeto quando estou empolgado, e esse projeto, por algum motivo, já não me apresenta essa empolgação..<br />
Decidi esperar a vontade voltar, pois assim asseguro que o projeto será feito com vontade, e não forçado por causa do compromisso..<br />
<br />
Pra quem é desenvolvedor e ficou curioso com o código fonte do mesmo, hoje eu vou distribuir.<br />
Vale lembrar que nenhum dos gráficos usados no projeto são de minha autoria, eu apenas os utilizei como forma de portfólio. Nunca tive retorno financeiro desse projeto, e nem pretendo.<br />
Espero que façam bom uso do mesmo, não expondo de forma incorreta, mas sim usando para fins de estudos.<br />
<br />
O projeto foi desenvolvido no Eclipse, e a hierarquia de pastas do mesmo está como de costume do Eclipse. Se quiserem testar o jogo, terão que compila-lo junto a uma IDE.<br />
Não vou disponibilizar um arquivo baixável para o celular por dois motivos: não sei como, e estou com preguiça. Se eu mudar de ideia eu coloco aqui.<br />
O link do projeto está aqui: <a href="http://www.mediafire.com/download.php?l6nj7gkgdjc1n5d">http://www.mediafire.com/download.php?l6nj7gkgdjc1n5d</a><br />
<br />
O projeto está bem bagunçado, e como é meio complexo, foram usadas várias classes e linhas de código. Eu procurei comentar o máximo possível, mas provavelmente continuará confuso para os mais desatentos.<br />
Se quiserem editar, continuar o projeto, ou algo do tipo, estão liberados.<br />
Se tiverem alguma dúvida em relação ao projeto, enviem um e-mail para: cristhian.bonilha@hotmail.com<br />
<br />
Bom, é isso, até mais!Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2697059789481443605.post-39597490768232035922013-04-06T13:32:00.000-03:002013-04-06T13:32:12.598-03:00O quão rápido você consegue digitar?<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiM-_6FKp1hvB2RGHzcsGFu2bnx8Fi-L8Bl4d5A7kjNmVCNO2MnlJ08Hzmkekw2fJO00GzS_wldG2pdOSAfZ4ctsmuMndzMeGcCjPKElQDvi7e_Ssc7EZTNtatOynj3Beqe7DDDKEBZF_hl/s1600/typeracer2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiM-_6FKp1hvB2RGHzcsGFu2bnx8Fi-L8Bl4d5A7kjNmVCNO2MnlJ08Hzmkekw2fJO00GzS_wldG2pdOSAfZ4ctsmuMndzMeGcCjPKElQDvi7e_Ssc7EZTNtatOynj3Beqe7DDDKEBZF_hl/s1600/typeracer2.png" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
No mundo da programação, seu maior companheiro é o teclado (e o café), porém nem todos compreendem a importancia que tem ter uma boa relação com o mesmo.<br />
<br />
Até semana passada, eu me julgava um digitador ninja, com super velocidade e precisão, porém notei que eu estava muito preso ao ato de <b>olhar no teclado </b>para caçar as teclas corretas. Isso me fazia perder tempo, e quando tentei digitar sem olhar, minha precisão caiu para zero.<br />
<br />
Eis que começei a aprender a arte da digitação. Cada dedo em seu lugar, memória afiada, e mão na massa.<br />
Não lembro quanto eu tirei no teste de velocidade antes de começar a estudar, porém hoje digito a uma velocidade de 50WPM (Palavras Por Minuto, medição adotada em competições e sites de digitação), a qual já acho boa, e olha que só estou praticando a uma semana.<br />
<br />
Experimente aqui sua velocidade: <a href="http://www.typingtest.com/">http://www.typingtest.com/</a><br />
<br />
Caso não esteja satisfeito, ou queira aprender a digitar sem olhar no teclado, como eu quis, há alguns cursos online com alguma fração grátis. Eu pratiquei nesses:<br />
<a href="http://course.typingtest.com/online-tutor/">http://course.typingtest.com/online-tutor/</a><br />
<a href="http://www.goodtyping.com/default.htm">http://www.goodtyping.com/default.htm</a><br />
<br />
E depois aposte corridas com pessoas de todo o mundo, neste site (foto):<br />
<a href="http://play.typeracer.com/">http://play.typeracer.com/</a>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2697059789481443605.post-28597050945602442962013-03-29T23:45:00.001-03:002013-04-12T13:23:57.574-03:00Batalha GameloopEae, como estão?<br />
<br />
Eu estou meio atarefado, pra variar, mas pra provar que eu não deixei o jogo de lado, eis uma prova irrefutável (ou não) de que ele está em desenvolvimento:<br />
<br />
<div class="separator" style="clear: both; text-align: left;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgDjuUK7gejq7wFGsGT28eeykzsCMOSeQ4iDT_w7bF5NxijwBTJvwbidSn1zqx1LGPR4KVO6lUVc8Jkk35Uqm78W6WAYEyBJZN6XyZ0G7qutVqpJbCaNUF9-pEGz7OzdQ3EUZVjPzWWtHFi/s1600/print_1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgDjuUK7gejq7wFGsGT28eeykzsCMOSeQ4iDT_w7bF5NxijwBTJvwbidSn1zqx1LGPR4KVO6lUVc8Jkk35Uqm78W6WAYEyBJZN6XyZ0G7qutVqpJbCaNUF9-pEGz7OzdQ3EUZVjPzWWtHFi/s1600/print_1.png" /></a></div>
<br />
Nada mais que uma print do gameloop da área de batalha do jogo..<br />
Ainda não está completa, e essa parte é só 1% do código completo, que está por trás desses métodos, porém é ali que rola toda a organização, portanto está entre as partes mais importantes do código, por isso resolvi mostrá-la.<br />
<br />
Eu também imaginei se alguém teria curiosidade em ver um ou outro método, ou uma outra técnica que eu utilizo no desenvolvimento, então eu resolvi postar esse pedaço pra checar. Vocês acham isso interessante?<br />
<br />
Acontece que eu utilizo técnicas que, digamos, podem ser, ou não, as mais recomendadas.. Resumindo, eu ainda sou iniciante na área, e tudo que eu programo está em fase de teste. Qualquer programador experiente vai notar falhas no meu código e oportunidades de otimização, porém por hora esses meus métodos estão funcionando, e eu estou aprendendo bastante com os mesmos, portanto está tudo bem.<br />
<br />
Acho que já falei demais pra um post rápido, até mais.Unknownnoreply@blogger.com0