tag:blogger.com,1999:blog-50660626919485912252024-03-13T10:33:45.016-03:00Caloventor en DosEquipo argentino de ACM-ICPCMartín Villagrahttp://www.blogger.com/profile/04539435412394117022noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-5066062691948591225.post-40829211082004706532020-11-15T11:45:00.003-03:002020-11-15T14:41:23.834-03:00Solucionario TAP 2020 (por Agustín Santiago Gutiérrez)
<div class="separator" style="clear: both;"><a href="https://1.bp.blogspot.com/-K__pAcJ5mRE/X7E9k_u9yaI/AAAAAAAAV5k/iPbZH6VNy20AMdQGKMlvrZEuGJNGsdwlACLcBGAsYHQ/s1440/IMG_4173.jpg" style="display: block; padding: 1em; text-align: center; clear: left; float: left;"><img alt="" border="0" height="320" data-original-height="1440" data-original-width="1080" src="https://1.bp.blogspot.com/-K__pAcJ5mRE/X7E9k_u9yaI/AAAAAAAAV5k/iPbZH6VNy20AMdQGKMlvrZEuGJNGsdwlACLcBGAsYHQ/s320/IMG_4173.jpg"/></a></div>
<p>Ayer se realizó otra exitosa instancia del Torneo Argentino de Programación. Debido a la pandemia la competencia fue virtual lo que sin duda representa un cambio de paradigma para los equipos ya que a pesar de estar físicamente separados podían usar tres computadoras y disponían acceso al scoreboard de todas las regiones. La sede de Rosario tuvo 11 equipos, de los cuales cuatro fueron clasificados a la siguiente instancia a realizarse probablemente en marzo. La foto es el podio de nuestra sede durante una pequeña revelación virtual post-contest. Gracias Brian Morris por la organización y felicitaciones a todos los equipos por dejar nuestra sede bien en alto!<br /><br />
<div class="separator" style="clear: both;"></div>
<h2>Enunciados</h2>
Siguiendo el siguiente link:
<a href="https://drive.google.com/file/d/1zoiepxGBT1QSGHYv8RBrFQyxG-vk-SGl/view" target="_blank">https://drive.google.com/file/d/1zoiepxGBT1QSGHYv8RBrFQyxG-vk-SGl/view</a><br /><br />
<h2>Solucionario</h2><p>Este año el solucionario lo tenemos gracias al canal de nuestro amigo bonaerense Agustín Santiago Gutiérrez.</p>
<p>
</p><div class="separator" style="clear: both;"><a href="https://www.youtube.com/watch?v=0eWr-ybZy_A" target="_blank" style="clear: left; display: block; float: left; padding: 1em 0px; text-align: center;"><img alt="" border="0" data-original-height="628" data-original-width="1118" src="https://1.bp.blogspot.com/-3uVTeK1LYNI/X7E4Cg_hUyI/AAAAAAAAV4s/LZyKQ3Bv7qIAd9yXmBRa-TrReICQDaFFACLcBGAsYHQ/s320/Screenshot%2B2020-11-15%2Bat%2B11.15.00.png" width="560" /></a></div>
<p></p>
<div class="separator" style="clear: both;"></div>
No se olviden seguirlo y activar las notificaciones porque está haciendo contenido muy copado si les interesa entrenar en ICPC!<br /><br />
<div class="separator" style="clear: both;"></div>
<script src="https://apis.google.com/js/platform.js"></script>
</p><div class="g-ytsubscribe" data-channelid="UCqF1Y3wsJc-JhE9EusFyCHA" data-count="default" data-layout="full"></div><br /><br />
<h2>Scoreboards finales</h2>
Disponibles temporalmente por aquí: <a href="https://placar.naquadah.com.br/boca/Argentina/" target="_blank">https://placar.naquadah.com.br/boca/Argentina/</a><br /><br />
Sede Rosario
<div class="separator" style="clear: both;"><a href="https://1.bp.blogspot.com/-yK50XXumKyY/X7E79bQ85MI/AAAAAAAAV5I/tk48-la5FMMnnFVV7TCs9-lxIaxR9NRfQCLcBGAsYHQ/s0/Screenshot%2B2020-11-15%2Bat%2B11.28.21.png" style="display: block; padding: 1em 0; text-align: center; "><img alt="" border="0" data-original-height="979" data-original-width="3212" src="https://1.bp.blogspot.com/-yK50XXumKyY/X7E79bQ85MI/AAAAAAAAV5I/tk48-la5FMMnnFVV7TCs9-lxIaxR9NRfQCLcBGAsYHQ/s0/Screenshot%2B2020-11-15%2Bat%2B11.28.21.png"/></a></div><br/><br/>
Toda Argentina
<div class="separator" style="clear: both;"><a href="https://1.bp.blogspot.com/-C2QurKCgAM8/X7E9UbAI5TI/AAAAAAAAV5c/UyczOD8yozwiWRcfX0bypnTGFnypFgYWwCLcBGAsYHQ/s0/screencapture-placar-naquadah-br-boca-Argentina-2020-11-15-11_36_57.png" style="display: block; padding: 1em 0; text-align: center; "><img alt="" border="0" data-original-height="2048" data-original-width="1553" src="https://1.bp.blogspot.com/-C2QurKCgAM8/X7E9UbAI5TI/AAAAAAAAV5c/UyczOD8yozwiWRcfX0bypnTGFnypFgYWwCLcBGAsYHQ/s0/screencapture-placar-naquadah-br-boca-Argentina-2020-11-15-11_36_57.png"/></a></div>
Martín Villagrahttp://www.blogger.com/profile/04539435412394117022noreply@blogger.com0tag:blogger.com,1999:blog-5066062691948591225.post-4177643587519797622017-10-22T01:37:00.000-03:002017-10-22T13:47:39.242-03:005 horas en la World Finals 2016Me dieron muchas ganas de escribir cosas que fuimos pensando, analizando y descubriendo en nuestros dos años como competidores a lo cuál, personalmente, le dediqué mucho tiempo. Todas estas cosas que voy a intentar volcar acá son producto de miles de errores, choques contra una pared y consejos de otras personas (entre las cuáles debo mencionar si o si al genio de <i>Nico Alvarez</i>), pero sobre todo producto de <b>mi fascinación</b> por poder lograr que el Caloventor funcione lo mejor posible.<br />
<br />
En este posteo, voy a intentar <b>relatar la World Finals 2016 desde adentro</b>, sobre todo desde mi punto de vista. Creo que es una competencia ejemplificadora ya que nos preparamos mucho para ella y tuvimos casi todos los errores que podíamos llegar a tener. Voy a intentar ser lo más detallista posible, porque nunca encontré una guía detallada que nos ayude, pero seguro me voy a comer varios detalle.<br />
<br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: right; text-align: left;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-CbMEehl8Bgs/WevtXVp6XyI/AAAAAAAAE10/L4JgCXAVhRsCo-9LmzDjhw0OCQJx4TEZACLcBGAs/s1600/IMG-20160518-WA0015.jpg" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" data-original-height="960" data-original-width="1280" height="150" src="https://1.bp.blogspot.com/-CbMEehl8Bgs/WevtXVp6XyI/AAAAAAAAE10/L4JgCXAVhRsCo-9LmzDjhw0OCQJx4TEZACLcBGAs/s200/IMG-20160518-WA0015.jpg" width="200" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Foto en el Warm Up</td></tr>
</tbody></table>
En esta competencia, nosotros íbamos a buscar el premio de campeón latinoaméricano, el cuál nosotros creíamos estar disputando (como finalmente pasó) contra las universidades de Pernambuco y Campina Grande. Las decisiones que fuimos tomando fueron en base a ese objetivo, aunque en algún momento pensamos que podíamos llegar a pelear alguna que otra medalla.<br />
<br />
<span style="color: blue;"><b><i>00:00</i></b></span><br />
Arranca la competencia. Cada uno tiene su rol inicial bien definido y pensado. Esto es importante, porque al principio los nervios y la ansiedad te comen vivo y cuesta <b>pensar</b> si no estás organizado. Los tres sabíamos en que condiciones estába cada uno, yo en particular no había dormido un carajo y estaba con algo de fiebre pero estaba muy motivado, el Marian estaba hiper-nervioso, y Martín... Martín nunca sabe como está, ja. Pero ambos habían dormido bien que no es poco. Los 3 con muchas pilas ya que nos habíamos motivado 15 minutos antes de que nos íbamos a comer vivo a los Brasileros, je. Esas cosas que uno sueña y la mayoría de veces no pasa.<br />
<br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: left; margin-right: 1em; text-align: left;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-KsCgBcE5xNk/Wevn79g24uI/AAAAAAAAE04/Wd2mhGMDf6gLwmybIhook0nBVdLNwEKsQCLcBGAs/s1600/DSC_0005.JPG" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="900" data-original-width="1600" height="179" src="https://3.bp.blogspot.com/-KsCgBcE5xNk/Wevn79g24uI/AAAAAAAAE04/Wd2mhGMDf6gLwmybIhook0nBVdLNwEKsQCLcBGAs/s320/DSC_0005.JPG" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Nuestra tablita final luego de las 5 horas</td><td class="tr-caption" style="text-align: center;"><br /></td></tr>
</tbody></table>
Martín arrancó codeando el template, que es un archivo base que copiamos solo una vez al principio para no hacer 10 veces lo mismo <b>(y que sobre todo sirve para menguar los nervios)</b>, y a ordenar todas las cosas necesarias en la compu, yo me puse a copiar la tablita <i>(ver imagen)</i> y Mariano a leer desde el A.<br />
<br />
Yo soy el que busca el trivial y leo E+. Pegué una ojeada, descarte F,G,H,I y me puse a leer primero el J y como parecía hard volví al E.<br />
<br />
Llega el primer solve del C, y lo mandamos a Mariano a pensarlo. En eso Martín me cuenta el L diciendo que parecía de mi onda, lo pienso y me pareció idéntico a un problema que ya había pensado, por lo que me puse a codear algo "esperando a ver si entraba". Mando y metó un <b><span style="color: red;">TLE</span></b> completamente ilógico. Releó el código y veo que había cerrado mal una llave, que pajero. Lo arreglo, mando y <b><span style="color: lime;">metemos el L!</span></b><br />
<br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: right; text-align: right;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-ZXyG485GIzY/WevoZHhaHsI/AAAAAAAAE08/V8MaJvGOgic3cTatAU53vuzEjzabuD8uACLcBGAs/s1600/photo353922193458047129.jpg" imageanchor="1" style="clear: right; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" data-original-height="1280" data-original-width="960" height="200" src="https://4.bp.blogspot.com/-ZXyG485GIzY/WevoZHhaHsI/AAAAAAAAE08/V8MaJvGOgic3cTatAU53vuzEjzabuD8uACLcBGAs/s200/photo353922193458047129.jpg" width="150" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Brasil festejando nuestro RTE</td></tr>
</tbody></table>
Marian tenía el C y entra a codearlo, Tin estaba leyendo el K y yo me pongo a pensar el E. Me pareció que era para el Marian, vuelvo a pensar el J pero no llego a nada, anotó que es <b>Hard</b> y lo dejo. A todo esto el Marian producto de sus nervios iniciales mando un <b><span style="color: red;">RTE </span></b>por hacer algo<b><span style="color: red;"> </span></b>con complejidad exponencial, con la presión de que la gente lo metía.<br />
<br />
<span style="background-color: blue;"><span style="color: purple;"><br /></span></span><i>
<span style="color: blue;"><span style="background-color: white;"><b>Resumen (a la 0:30) - (45avos - 5tos LATAM)</b></span></span></i><br />
<span style="color: blue;"><span style="background-color: white;">A: Math-Bardo. </span></span><br />
<span style="color: blue;"><span style="background-color: white;">B: No leído.</span></span><br />
<span style="color: blue;"><span style="background-color: white;"><b>C: Codeando/Debugueando (Marian) (40 AC)</b></span></span><br />
<span style="color: blue;"><span style="background-color: white;">D: No leído. </span></span><br />
<span style="color: blue;"><span style="background-color: white;">E: Math-a la espera de Marian (3 AC)</span></span><br />
<span style="color: blue;"><span style="background-color: white;">F: No leido </span></span><br />
<span style="color: blue;"><span style="background-color: white;">G: No leído </span></span><br />
<span style="color: blue;"><span style="background-color: white;">H: No leído </span></span><br />
<span style="color: blue;"><span style="background-color: white;">I: No leído </span></span><br />
<span style="color: blue;"><span style="background-color: white;"><b>J: Pensando (Pablo). </b></span></span><br />
<span style="color: blue;"><span style="background-color: white;"><b>K: Pensando (Tin). </b></span></span><br />
<span style="color: blue;"><span style="background-color: white;">L: AC </span></span><br />
<span style="color: blue;"><span style="background-color: white;">M: La idea está pero hay que codearlo y es una paja (Tin) </span></span><br />
<br />
<div style="text-align: left;">
</div>
Por suerte se ordenó, y sumado a que nadie lo molestaba porque no se nos ocurría una puta idea, metió el<b> <span style="color: lime;">AC</span></b> con lo que subimos momentaneamente a la <b>zona de medallas</b>. So, entra el C. Yo me había puesto a leer el D, y Tin el K. Le cuento al Marian el E, y se me ocurre la idea del D. Como la máquina estaba vacía me la iba a poner a codear, pero yo no soy el coder así que le pregunto a Tin si estaba con alguna idea o le contaba el D. Estaba bloqueado con el K, por lo que le cuento la solución del D por arriba pero le digo que se lo ponga a ver él porque no lo había leído completo. A todo esto el Marian me cuenta su idea del E pero era una fruta que en el podía tardar 10^18. Nos lo ponemos a <b>pensar juntos</b> (que es algo que no solemos hacer antes de la primer hora mucho pero dado la presión inicial valió la pena) y se me ocurre una idea pero que había que codear algo del diego que podía llegar a tardar como 20 minutos. El Marian me da el visto bueno y cómo la máquina estaba desocupada, Marian me deja el E y se pone a pensar el G que lo venían metiendo. Yo me pongo a copiar lo que teníamos en <b>el diego</b> (ese nombre le ponemos a los algoritmos que llevamos impresos en papel) hasta que termino y Tin estaba pseudocodeando el D. <br />
<br />
<i><b><span style="color: blue;">Resumen (a la 1:00) - (27avos - LATAM Champions)</span></b></i><br />
<span style="color: blue;">A: </span><span style="color: blue;">No leído bien, parece para Pablo. </span><br />
<span style="color: blue;">B: No leído. (1 AC)</span><br />
<span style="color: blue;">C: AC </span><br />
<span style="color: blue;"><b>D: Pseudocodeando (Tin) </b></span><br />
<span style="color: blue;"><b>E: Codeando el Diego (Pablo) (18 AC)</b></span><br />
<span style="color: blue;">F: No leido </span><br />
<span style="color: blue;"><b>G: Pensando (Marian) (5 AC)</b></span><br />
<span style="color: blue;">H: No leído</span><br />
<span style="color: blue;">I: No leído </span><br />
<span style="color: blue;">J: Dejado, Med/Hard.</span><br />
<span style="color: blue;">K: Leído. (2 AC)</span><br />
<span style="color: blue;">L: AC </span><br />
<span style="color: blue;">M: La idea está pero hay que codearlo y es una paja (Tin)</span><br />
<br />
Cuando termino de codear, Tin se pone a codear el D, mientras yo imprimo lo del diego y Marian entra a <b>revisarme el código</b> (cosa clave que otro revise lo del diego, en este caso me arreglo mínimo como 5 errores de tipeo) y yo a pseudocodear la otra parte del E. A todo esto Marian tenía la idea del G, me la cuenta diciendome que es algo que nunca habíamos codeado. Yo le dije que no había apuro porque teníamos dos problemas <i><span style="color: orange;"></span></i>, y como la máquina de repente estaba a full se pone a <b>pseudocodear la idea en papel</b>. Muchas veces es más rápido escribir en papel que frente a una computadora y es algo que no muchos equipos hacen. <i> </i><br />
<br />
<span style="color: purple;"><i>Estar frente a la compu te pone presión de que tenés que hacer cosas útiles porque la estás ocupando. Nuestro método de laburo era generalmente cooperativo: Siempre que se podía se pseudocodeaba los detalles finos en papel, la máquina solo se usa para codear y si alguien quiere debuguear lo hace en papel salvo que nadie más necesite codear. Meter los problemas rápido siempre fue sólo de prioridad baja. </i><i><i><b>Nuestra regla número 1 siempre fue no dejar la máquina sin uso.</b></i></i></span><br />
<br />
Por mi parte, yo me pongo a codear lo que queda del E, intermitentemente con Tin que iba codeando partes del D (que era de implementación) entonces <b>codeaba un rato cada uno</b> mientras el otro <b>revisaba su código y pseudocodeaba nuevas partes</b>. Esto estuvo bueno porque yo estaba ansioso y desordenado y no podía codear bien mis ideas del E. Las salidas esporádicas me ayudaban a repensar que tenía que ir haciendo. Mariano termina de pseudocodear el G, y como la máquina estaba a full se pone a pensar el K que era el próximo por subs.<br />
<br />
<i><b><span style="color: blue;">Resumen (a la 1:30) - (39avos - LATAM Champions)</span></b></i><br />
<span style="color: blue;">A: No leído bien, parece para Pablo. (2 AC)</span><br />
<span style="color: blue;">B: No leído. (4 AC)</span><br />
<span style="color: blue;">C: AC </span><br />
<span style="color: blue;"><b>D: Codeando/Debugueando (Tin) (1 AC)</b></span><br />
<span style="color: blue;"><b>E: Codeando/Debugueando (Pablo) (45 AC)</b> </span><br />
<span style="color: blue;">F: No leido</span><br />
<span style="color: blue;"><b>G: Pseudocodeado (Marian) (15 AC)</b></span><br />
<span style="color: blue;">H: No leído</span><br />
<span style="color: blue;">I: No leído</span><br />
<span style="color: blue;">J: Dejado, Med/Hard.</span><br />
<span style="color: blue;"><b>K: Pensando (Marian). (7 AC)</b></span><br />
<span style="color: blue;">L: AC </span><br />
<span style="color: blue;">M: La idea está pero hay que codearlo y es una paja (Tin)</span><br />
<br />
<br />
Este momento fue clave en la competencia, porque estábamos con 3 ideas y una sola computadora, Martín estaba luchando con el D y yo con el E hacía ya un tiempito. Mi programa ya estaba todo codeado pero yo estaba trabado sinceramente porque <b>no entendía que estaba haciendo</b> (el problema E tenía sus vueltitas en el medio de los nervios de la competencia) entonces salí y lo deje a Martín mientras volvía a repensar todo. Ordené mis ideas, y cuando Martín salió a pensar, cambié una línea y de repente todo dio. Lo mande con mucho miedo ya que había muchos WAs y no confiaba en mi overkill pero dio <b><span style="color: lime;">AC!</span></b> Gol de media cancha y entró el Marian porque Martín estaba viendo porque no le daban los ejemplos. Mientras tanto yo me puse a leer el A que Marian dijo que parecía Matemático y Martín <b>encuentra</b> un errorcito en el D <b>pero no entra</b> <b>a codear</b> porque el Marian estaba en la compu y se pone a leer el K que era el próximo.<br />
<br />
<i><b><span style="color: blue;">Resumen (a las 2:00) - (39avos - LATAM Champions)</span></b></i><br />
<span style="color: blue;"><b>A: Leyendo/Entendiendo (Pablo) (4 AC)</b></span><br />
<span style="color: blue;">B: No leído. (9 AC)</span><br />
<span style="color: blue;">C: AC </span><br />
<span style="color: blue;"><b>D: A la espera (Tin) (3 AC)</b></span><br />
<span style="color: blue;">E: AC</span><br />
<span style="color: blue;">F: No leido</span><br />
<span style="color: blue;"><b>G: Codeando (Marian) (26 AC) </b></span><br />
<span style="color: blue;">H: No leído</span><br />
<span style="color: blue;">I: No leído</span><br />
<span style="color: blue;">J: Dejado, Med/Hard.</span><br />
<span style="color: blue;"><b>K: Pensando (Tin) </b></span><span style="color: blue;"><b>(16 AC)</b></span><br />
<span style="color: blue;">L: AC </span><br />
<span style="color: blue;">M: La idea está pero hay que codearlo y es una paja (Tin)</span><br />
<br />
Mientras Mariano codeaba el G, a mi se me ocurre una idea del A pero que necesitaba una mano de los pibes, por lo que me pongo a <b>pseudocodear mi parte </b>(en papel). Mientras analizo el código, me doy cuenta que ni siquiera necesito ayuda de los pibes, porque el problema parecía trivial. A todo esto seguíamos punteros y con 3 ideas así que veníamos bárbaro. Marian se traba con el G y entra el Tin que en 5 minutos arregla el D, manda y otro <b><span style="color: lime;">AC!</span></b> Festeja Calove y entro yo a pseudocodear mi parte del A alternadamente con el Marian. Martín vuelve a pensar el fatídico K.<br />
<span style="color: blue;"><br /></span><i><b>
<span style="color: blue;">Resumen (a las 2:30) - (34avos - LATAM Champions)</span></b></i><br />
<span style="color: blue;"><b>A: Codeando (Pablo) (6 AC)</b></span><br />
<span style="color: blue;">B: No leído. (15 AC)</span><br />
<span style="color: blue;">C: AC </span><br />
<span style="color: blue;">D: AC</span><br />
<span style="color: blue;">E: AC</span><br />
<span style="color: blue;">F: No leido</span><br />
<span style="color: blue;"><b>G: Codeando (Marian) (44 AC)</b></span><br />
<span style="color: blue;">H: No leído</span><br />
<span style="color: blue;">I: No leído</span><br />
<span style="color: blue;">J: Dejado, Med/Hard.</span><br />
<span style="color: blue;"><b>K: Pensando (Tin). (28 AC)</b></span><br />
<span style="color: blue;">L: AC </span><br />
<span style="color: blue;">M: La idea está pero hay que codearlo y es una paja (Tin)</span><br />
<br />
Yo termino de codear el A, lo mando y me como un <b><span style="color: red;">WA</span></b> completamente desmotivante. Mientras Mariano seguía viendo el G, me llega la <b>impresión</b> <b><span style="color: purple;">(Regla de Oro: Cada vez que se manda un problema se imprime y recién se ve el resultado cuando llega la impresión)</span></b>, releo el enunciado y descubro un detallecito, por lo que vuelvo a entrar, cambio una constante, mando y llega el <b><span style="color: lime;">AC!</span></b> Alto grito metí acá. Marian también termina de codear y manda y otro <span style="color: lime;"><b>AC!</b></span> Miro a Latinoamérica: Pernambuco y Campina Grande estaban con 4 y después todos 3 para abajo y nosotros teníamos 6. Estábamos 14avos y podíamos llegar a pelear medalla! Estuvimos 2 minutos congelados en un estado de shock hasta que finalmente nos sentamos a analizar.<br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: right; margin-left: 1em; text-align: right;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-clk7S7u6uCQ/Wevspq6RvRI/AAAAAAAAE1o/lt15BZH05FcHg0c6_PFhQTPqcaUCAr7MQCLcBGAs/s1600/unr%2B14.png" imageanchor="1" style="clear: right; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" data-original-height="437" data-original-width="974" height="89" src="https://1.bp.blogspot.com/-clk7S7u6uCQ/Wevspq6RvRI/AAAAAAAAE1o/lt15BZH05FcHg0c6_PFhQTPqcaUCAr7MQCLcBGAs/s200/unr%2B14.png" width="200" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Caloventor mete el G y queda arriba</td></tr>
</tbody></table>
<br />
El K no salía, me lo cuentan y no era mi onda. Martín se pone a leer el B que era el otro que alguien había metido y el resto de los problemas <b>no tenían ningún AC.</b> El B no lo entendíamos, Marian sigue pensando el K, Martín se lee el I y lo anota como EL HARD y yo el H. Acá la máquina no estaba siendo usada. Terminamos de entender el B y se me ocurre la parte trivial y lo mando a codear a Martín. Esta creo fue una <b>decisión erronea</b>, tendríamos que haber codeado el M que ya lo teníamos pensado y sabíamos como salía. Creo que nos asustó que nadie lo haya metido y me parece que nos <b>apuramos por tener la máquina ocupada</b> en lugar de analizar mejor. Ahí le cuento el problema B al Marian, me dijo que conocía el problema pero que no sabía como se resolvía, malísima noticia. Se nos ocurren una ideas para optimizar y lo dejo porque el me dijo que ya tenía una idea.<br />
<br />
<i><b><span style="color: blue;">Resumen (a las 3:00) - (18avos - LATAM Champions)</span></b></i><br />
<span style="color: blue;">A: AC </span><br />
<span style="color: blue;"><b>B: Codeando (Tin), Pensando (Marian). (24 AC)</b></span><br />
<span style="color: blue;">C: AC </span><br />
<span style="color: blue;">D: AC</span><br />
<span style="color: blue;">E: AC</span><br />
<span style="color: blue;">F: No leido </span><br />
<span style="color: blue;">G: AC</span><br />
<span style="color: blue;"><b>H: Leyendo (Pablo) </b></span><br />
<span style="color: blue;">I: Dejado, HARD. </span><br />
<span style="color: blue;">J: Dejado, Med/Hard. </span><br />
<span style="color: blue;"><b>K: Leyendo/Pensando (Pablo). (38 AC)</b></span><br />
<span style="color: blue;">L: AC </span><br />
<span style="color: blue;">M: La idea está pero hay que codearlo y es una paja (Tin). </span><br />
<br />
Mientras los pibes estaban con el B, yo me pongo a ver un panorama general de la prueba, ya que el B y el K no nos estaban saliendo y nadie había metido nada más. Leo el H y se me ocurren unas ideas que le cuento a Tin y definimos dejarlas por ser Geométrico y re bardero. Vuelvo y me pongo a pensar el K desganado (no es el tipo de problema que yo suelo hacer). Pruebo un par de casos y se me ocurre una idea loca y extraña! Los pibes estaban laburando en el B y le cuento mi idea a Tin que no me entiende nada (producto de mi quemadez, estuvimos como 1 o 2 minutos), entonces me enojo y me pongo a codearla yo. Los pibes mientras tanto buscaban como arreglar la segunda parte del B, <span style="color: purple;"><i>que tenía que salir porque lo metían toooodos</i></span> <b>(error)</b>. Llega el primer <span style="color: blue;">AC</span> del F, pero ya es tarde... No tenía sentido leer ese problema.<br />
<br />
<i><b><span style="color: blue;">Resumen (a las 3:30) - (22avos - LATAM Champions)</span></b></i><br />
<span style="color: blue;">A: AC </span><br />
<span style="color: blue;"><b>B: Pensando como codear una parte (Tin y Marian). (28 AC)</b></span><br />
<span style="color: blue;">C: AC </span><br />
<span style="color: blue;">D: AC</span><br />
<span style="color: blue;">E: AC</span><br />
<span style="color: blue;">F: No leido, dejado. (1 AC)</span><br />
<span style="color: blue;">G: AC</span><br />
<span style="color: blue;">H: Dejado por Geometría HARD </span><br />
<span style="color: blue;">I: Dejado, HARD. </span><br />
<span style="color: blue;">J: Dejado, Med/Hard. </span><br />
<span style="color: blue;"><b>K: Codeando (Pablo). (46 AC)</b></span><br />
<span style="color: blue;">L: AC </span><br />
<span style="color: blue;">M: La idea está pero hay que codearlo y es una paja (Tin). </span><br />
<br />
Faltando una hora y media, y sin muchas ideas concretas, redujimos la prueba a B,K,M, lo cuál es bueno porque<span style="color: purple;"> <b>no tiene sentido pensar tantos problemas al final</b></span> (<b>3</b> sería lo <b>máximo</b> en <b>hora y media</b>). Mi análisis de la situación es que había que meter 8 para ser Latam porque teníamos buena penalidad y 9 para la medalla, entonces estaba apurado para meter B y K.<br />
<br />
Acá yo me pongo a codear la parte borde del K y le pido ayuda al Marian para codear la parte de la simulación trivial. Le cuento mi solución así no más y lo que él tenía que hacer que parecía una boludés pero yo no podía hacer ni un for. Marian se lo pone a hacer. Mientras tanto mandamos las primera subs del B que nos dan <b><span style="color: red;">WA</span></b> (que estábamos seguros que era error en la idea del Marian). <i><span style="color: purple;">Desgraciadamente había un error en el Dijkstra pero no se porque no nos dimos cuenta y nadie releyó el código</span>. Yo estaba casi seguro que la idea del Marian estaba bien</i> pero no dije nada porque estaba con el K, <i>desgraciadamente también estaba mal</i>. Cuestión, priorizamos meter el K.<br />
<br />
<i><b><span style="color: blue;">Resumen (a las 4:00) - (28avos - LATAM Champions)</span></b></i><br />
<span style="color: blue;">A: AC </span><br />
<span style="color: blue;"><b>B: WA (-2) Debugueando (Tin). (39 AC)</b></span><br />
<span style="color: blue;">C: AC </span><br />
<span style="color: blue;">D: AC</span><br />
<span style="color: blue;">E: AC</span><br />
<span style="color: blue;">F: No leido, dejado. (2 AC)</span><br />
<span style="color: blue;">G: AC</span><br />
<span style="color: blue;">H: Dejado por Geometría HARD </span><br />
<span style="color: blue;">I: Dejado, HARD. </span><br />
<span style="color: blue;">J: Dejado, Med/Hard. (1 AC)</span><br />
<span style="color: blue;"><b>K: Codeando (Marian y Pablo). (55 AC)</b></span><br />
<span style="color: blue;">L: AC </span><br />
<span style="color: blue;">M: La idea está pero hay que codearlo y es una paja (Tin). (1 AC)</span><br />
<br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: right; text-align: left;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-9nQzP9o8kZA/Wevs6UgRIBI/AAAAAAAAE1s/RVVpICPkJCocRoLvIFB1Wz5xhauWWf-vACLcBGAs/s1600/IMG-20160525-WA0000.jpg" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" data-original-height="926" data-original-width="720" height="200" src="https://1.bp.blogspot.com/-9nQzP9o8kZA/Wevs6UgRIBI/AAAAAAAAE1s/RVVpICPkJCocRoLvIFB1Wz5xhauWWf-vACLcBGAs/s200/IMG-20160525-WA0000.jpg" width="155" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">El equipo en los últimos momentos</td></tr>
</tbody></table>
Mandamos por primera el K y <b><span style="color: red;">WA</span></b>. Marian se pone a recodear su parte mientras Martín se pone a intentar arreglar el B. Acá pasamos un tiempito debugueando ambos códigos. Yo pruebo un par de casos en el K y dan mal. Mandamos el K con la nueva parte del Marian y otro <b><span style="color: red;">WA</span></b>. Vuelvo a probar los mismos casos. Daban mal, y <b>estábamos tan en cualquiera que ni habíamos probado los casos.</b> Mientras tanto Martín entraba a ver cosas del B.<br />
<br />
<span style="color: blue;">A las 4:30</span>, <b>luego de casi 2 horas</b> <b>sin meter ningún AC</b>, charlamos 10 segundos y metemos una buena decisión y dejamos el B bajando nuestras espectativas (nunca repensadas) de 9 y medalla que teníamos hace 2 horas y apuntando a, <i>al menos</i>, meter 7. Yo encuentro un error en mi parte, puteo, la arreglo y con el nuevo código del Marian daba cualquier cosa. Pruebo con el viejo y da bien. Mando y <b><span style="color: red;">WA!!!</span></b> Marian me putea y dice que usemos su nueva parte, nos ponemos a debuguear y era una boludés, arreglamos, mandamos y <b><span style="color: lime;">AC!!!! </span></b><br />
Otro grito de gol pero que no se grita para que nadie de latinoamérica sepa que metimos el 7mo y especule. <b>Quedaban 16 minutos donde teníamos que meter el B para asegurar el Latam Champions.</b> Nunca nos pusimos a ver el dijkstra del B. Nos pusimos a codear una idea fruta y mandamos 13 submissions probando cosas. Todas WA en la parte trivial del Dijkstra, ja.<br />
<br />
<br />
Terminamos con 7 problema sobre 13, 32avos del mundo y Campeones Latinoamericanos (42avos quedo también con 7 el equipo de Pernambuco que si no metíamos el K nos hubiese ganado y Campina Grande quedó con 6).<br />
<br />
<a href="http://myicpc.icpcnews.com/World-Finals-2016/scoreboard">http://myicpc.icpcnews.com/World-Finals-2016/scoreboard</a><br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: right;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-APzvDcAIqbQ/WevrI9W-VuI/AAAAAAAAE1Y/SRDqcsDrZYoEE9Z5LCecgLQQvBth05rmgCLcBGAs/s1600/rosario.jpg" imageanchor="1" style="clear: right; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" data-original-height="1067" data-original-width="1600" height="266" src="https://1.bp.blogspot.com/-APzvDcAIqbQ/WevrI9W-VuI/AAAAAAAAE1Y/SRDqcsDrZYoEE9Z5LCecgLQQvBth05rmgCLcBGAs/s400/rosario.jpg" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Caloventor recibiendo el Latam Champions</td></tr>
</tbody></table>
Anonymoushttp://www.blogger.com/profile/08383373879221108220noreply@blogger.com3tag:blogger.com,1999:blog-5066062691948591225.post-12281743339529888622017-10-21T14:54:00.000-03:002017-10-23T09:47:37.146-03:00Solucionario TAP 2017Una vez más otra exitosa instancia de esta competencia realizada alrededor de toda Argentina fue llevada a cabo. En esta ocasión Pablo Zimmermann colaboró junto con muchas otras personas en la elaboración de los problemas y a su vez fue coordinador de la sede de Rosario, la cual fue técnicamente posible gracias a Martín Villagra. Como siempre dejamos una foto de nuestra sede (en la que no nos acompañó Mariano por no estar en Rosario) y soluciones a los problemas.<br />
<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-b9cVuBHV6Lw/WeuGt0ZZKvI/AAAAAAAADGU/aUOTCU5mi8QGs3XRSvql6uwE69TMtq0KgCLcBGAs/s1600/22219708_1705801409453669_7496659281427852259_o.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="960" data-original-width="1280" height="300" src="https://2.bp.blogspot.com/-b9cVuBHV6Lw/WeuGt0ZZKvI/AAAAAAAADGU/aUOTCU5mi8QGs3XRSvql6uwE69TMtq0KgCLcBGAs/s400/22219708_1705801409453669_7496659281427852259_o.jpg" width="400" /></a></div><br /><br />
<h2>Links útiles</h2><ul><li>Info de la competencia <a href="http://torneoprogramacion.com.ar/">http://torneoprogramacion.com.ar</a> </li><li>Enunciados <a href="http://torneoprogramacion.com.ar/wp-content/uploads/2017/10/tap2017.pdf">http://torneoprogramacion.com.ar/wp-content/uploads/2017/10/tap2017.pdf</a> </li><li>Scoreboard <a href="http://torneoprogramacion.com.ar/2017/10/05/resultados-tap-2017/">http://torneoprogramacion.com.ar/2017/10/05/resultados-tap-2017/</a></li> <li>Juez online para enviar soluciones <a href="http://redprogramacioncompetitiva.com/contests/2017/11/">http://redprogramacioncompetitiva.com/contests/2017/11/</a></li></ul><br /><br />
<h2>Solucionario</h2>
<h3>A</h3><div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Si ponemos simplemente las notas en un arreglo [do, do#, re, re#, mi, fa, fa#, sol, sol#, la, la#, si], podemos encontrar la respuesta encontrando la nota actual y restando S posiciones. Si la respuesta queda negativa, simplemente sumamos 12. Otra opción es copiar el arreglo una 2da vez para evitar este caso borde o trabajar con el módulo.<br />
Código: <a href="https://pastebin.com/gFzPsdbL">https://pastebin.com/gFzPsdbL</a>
</div></div><br /><br />
<h3>B</h3><div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Consideramos los Pi en orden creciente ( Pi <= Pj , i<j ).
Cada cofre Ci puede satisfacer ahora a un prefijo de piratas (eventualmente vacío). Ya que si satisface al pirata Pi, satisface al Pi-1 (i>0). Podemos ubicar el primer pirata que no es satisfecho por cada cofre buscando el upper bound de Ci en P (luego de ordenar P). Esto tiene una complejidad de NlogN (logN por cada upper_bound).<br />
Con el procesamiento que hicimos podemos saber cuantos cofres podríamos asignar a cada pirata. Analicemos los Pi de derecha a izquierda (comenzando por el más grande) y empecemos a asignar cofres. La cantidad de opciones que barajamos para asignarle cofre al pirata i es la cantidad de cofres mayor o igual a sus requerimientos menos la cantidad de cofres ya asignados a los piratas de su derecha (n-i-1).<br />
Complejidad: O(NlogN)<br />
Código: <a href="https://pastebin.com/YrU2PS6G">https://pastebin.com/YrU2PS6G</a>
</div></div><br /><br />
<h3>C</h3><div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
*g[i] es lo que quiere cada amigo.<br />
*a[i] es la cantidad usada en cada cebada.<br />
Las diferencias g[i] - g[i-1] determinan cuánto debe valer a[i] - a[i-k(mod N)]. <br />
Sea D = gcd(N,K), como sabemos las diferencias cada K elementos, podemos seguir ese ciclo (i, i+k, i+2k, …. (módulo N)) hasta saber todas las diferencias entre elementos de diferencia D. <br />
Elegimos el ciclo que empieza en 0, con diferencia D. Con lo dicho antes podemos encontrar el más pequeño de ese ciclo y suponer que es 0. De esta manera ninguno de todo el ciclo puede ser menor ya que todos los a[i] deben ser positivos. Lo único que podemos hacer es sumarle una cantidad entera a cada elemento de ese ciclo. Hacemos lo mismo con cada ciclo. <br />
Como ya sabemos las diferencias, solo tenemos que ver si es posible cumplir las necesidades de alguno de los amigos y ahí cumpliríamos todas. Para esto vemos algún amigo en particular. Si la suma de los a[i] mínimos supera lo que quiere ese amigo, requeriríamos cebadas negativas, IMPOSIBLE. Si da justo, es posible (cada ciclo tiene un elemento mínimo en 0. <br />
Si es menor, necesitamos aumentar los valores de los ciclos. Sea C = K/D, la cantidad de elementos del mismo ciclo que hay cada K elementos. Si lo que necesitamos aumentar es múltiplo de C, es POSIBLE, modificando cualquiera de ese ciclo. Si no, tendríamos que hacer cebadas fraccionarias, lo cual es IMPOSIBLE.<br />
Código: <a href="https://pastebin.com/Xq6TPWsB">https://pastebin.com/Xq6TPWsB</a>
</div></div><br /><br />
<h3>D</h3><div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
El primer paso es observar cuál va a ser la estrategia para ganar dinero. Lo que se debe hacer es comprar dólares en una ciudad y venderlos en otra, COMPLETAMENTE. La estrategia consiste en hacer este paso repetidas veces de forma de tener cada vez más.
En segunda instancia hay que ver el carácter binario del problema (en este caso es ver que con menos de lo mínimo no voy a poder pero con más de lo mínimo siempre se va a poder), esto siempre es un fuerte indicio de que hay que aplicar búsqueda binaria. Por esta razón realizamos búsqueda binaria para encontrar el mínimo. Ahora, como es la función de evaluación? Es decir, cómo evaluamos si al iniciar con x cantidad de pesos podemos volvernos infinitamente ricos?<br />
Para hacer esto se tiene que tomar en cuenta la estrategia mencionada al principio, esto limita considerablemente las posibilidades a tener en cuenta. Resulta que modelar esta estrategia se vuelve simple creando un grafo ‘especial’ con las ciudades, recorrer una arista en este grafo será equivalente a hacer un paso de nuestra estrategia.<br /><br />
Es recomendable hacer un Floyd-Warshall para pre-calcular la distancia mínima entre dos ciudades cualesquiera, utilizando estas distancias nuestro algoritmo tiene en cuenta rutas entre ciudades indirectas.<br /><br />
El grafo es ‘especial’ porque los pesos de las aristas no son distancias sino que guardan cuánto podemos aumentar nuestro dinero actual. Si en la ciudad X el cambio está 1 a 20 y en la Y 1 a 17, y nuestro dinero es Z, entonces recorrer la arista X->Y modificaría nuestro dinero a Z*20/17-dist(X, Y). Una vez construido el grafo, la función de evaluación consiste en aplicar Bellman-Ford desde nuestro nodo inicial, para encontrar ciclos infinitos. Notar que no es necesario buscar explícitamente el ciclo, basta con ver si luego de N-1 iteraciones el nodo inicial tiene más dinero que con el que se comenzó.
</div></div><br /><br />
<h3>E</h3><div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Este problema tiene dos soluciones. Una es probar, a cada momento, todas las combinaciones posibles de cartas a jugar con el objetivo de maximizar la cantidad de manos a ganar de cada uno de los jugadores. La fuerza bruta no tarda mucho tiempo.<br />
Y la otra es hacer los casos a mano. <br />
* Si Eduardo no tiene el 1, excepto el caso 2-3-4, su abuelo (como puede tener el 1 y una del {2,3,4}) puede dejarle ganar posiblemente la primera mano para encajar {2,3,4} con la carta débil de Eduardo y ganar la otra mano con el 1 en las dos últimas.<br />
* Si Eduardo tiene el 1, tiene que ganar alguna otra mano más. No es difícil ver que le conviene tirar la más baja para tener la mayor cantidad de chances de jugar su 2da mejor carta contra la que le convenga de su abuelo una vez que este le gane la 1er mano. Y hay que analizar los distintos casos.<br />
Hubo soluciones aceptadas que solo contenían 3 ifs.<br />
Código: <a href="https://pastebin.com/1gHDXh2X">https://pastebin.com/1gHDXh2X</a><br />
<a href="https://pastebin.com/ADCi0UhJ">https://pastebin.com/ADCi0UhJ</a>
</div></div><br /><br />
<h3>F</h3><div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Existen distintas soluciones a este problema pero la que considero más simple es calculando el complemento. Es decir en lugar de calcular cuánta felicidad hay dentro del intervalo pedido llamémosle [S, E], mejor cálculo la felicidad total y le resto la que queda afuera de ese intervalo. Resulta que esto último es ligeramente más simple: lo que ‘queda afuera’ se puede subdividir en dos conjuntos DISJUNTOS: los recitales que terminan antes que S, y los recitales que empiezan luego de E. Si voy manteniendo un contenedor con sólo los comienzos de los recitales y otro para los finales de los recitales esto debería ser fácil. Tal contenedor podría implementarse con un segment tree o un árbol balanceado.
</div></div><br /><br />
<h3>G</h3><div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
A primera vista el problema tiene pinta de ser una combinatoria resuelta a partir de programacion dinamica. Podemos pensar que si tuviéramos una dinámica de la forma:
f( x , p1, p2 ) que sea la cantidad de formas de que se obtenga un resultado p1,p2 con x rondas tendríamos la solución al problema en f(N,P1,P2). Esto lo podríamos calcular en O(M) por estado. Pero la complejidad total seria O(P^2*N*M) lo cual es demasiado.
Notar que en esa dinámica p1 y p2 son bastante independientes. Podemos calcular g(x, p1) la cantidad de formas de obtener p1 en x rondas no nulas para un solo jugador. Esto lo haríamos en O(M) en cada paso, con una complejidad total de O(P*N*M).<br />
Luego podemos contar el total de juegos con resultados P1, P2 en N rondas (la respuesta al problema) analizando los casos con x rondas no nulas para el jugador 1 e y rondas no nulas para el jugador 2 y sumar todas (son disjuntas evidentemente) con x+y<=N. Para saber cómo las distribuimos en N formas las x e y tenemos comb[N][x]*comb[N-x][y], teniendo un total de g(x,P1)*g(y,P2)*comb[N][x]*comb[N-x][y]. Con una complejidad O(N^2) pre calculando los combinatorios en O(N^2) también.<br />
Complejidad: O(P*N*M + N^2)<br />
Código: <a href="https://pastebin.com/1i7JwYtg">https://pastebin.com/1i7JwYtg</a>
</div></div><br /><br />
<h3>H</h3><div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Si no hubiera números consecutivos iguales se puede ver que podemos garantizar que existe una montaña con la presencia de una cúspide (es decir un numero v[i] que es mayor que su predecesor y sucesor). Entonces eliminamos (como si comprimiéramos) consecutivos repetidos y contamos la cantidad de cúspides. Para qué predecesor y antecesor este definido en caso de que solo haya un número podemos considerar 0 auxiliares en los extremos.<br />
Complejidad: O(N)<br />
Código: <a href="https://pastebin.com/jiqn0v02">https://pastebin.com/jiqn0v02</a>
</div></div><br /><br />
<h3>I</h3><div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Para determinar si son similares hay que notar que los puntos pueden llegar a lo sumo ser una rotación de los originales (o una rotación invertida). Podemos probar con cada una de las rotaciones posibles (y su rotación invertida) chequeando si se corresponde con la original. Para hacer el chequeo basta con comprobar que los ángulos internos son iguales y que los lados son proporcionales.
</div></div><br /><br />
<h3>J</h3><div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Lo primero que hay que notar es que por cada nombre N, como no es compartido y cada jurado tiene sólo 2 nombres, tiene que tener un opuesto N’ (N’ esté presente en cada edición si y solo sí no esté N). <br />
Entonces si le podemos asociar a cada nombre un posible opuesto (con el caso especial de los nombres que estén siempre), claramente es posible que siempre hayan sido los mismos (lo probamos constructivamente). Caso contrario no.<br />
Para esto, podemos guardar para cada nombre una lista de apariciones y simplemente buscar un posible opuesto y eliminar ambos hasta que no quede ningún nombre disponible.<br />
Código: <a href="https://pastebin.com/r5pPqGXT">https://pastebin.com/r5pPqGXT</a>
</div></div><br /><br />
<h3>K</h3><div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Sea M la cantidad de elementos impares en el arreglo. <br />
*Para M = 0 la respuesta es 0. Supongamos M >= 1. <br />
- Se pueden convertir a todos los elementos en pares haciendo M + 1 operaciones de la siguiente forma: <br />
* Si M = 1: dividimos el único número impar a[i] y multiplicamos alguno de los pares a[j] (existe porque N >= 2). Después dividimos a[j] y multiplicamos a[i]. <br />
* Si M > 1: Seleccionamos 2 impares, uno se divide, otro se multiplica. Nos queda un impar menos gastando una operación. Repetimos esto hasta que M <= 1.<br /><br />
Lema.: la respuesta es <= M si y sólo si existe algún a[i] (par o impar) y un k (1 <= k <= M) tal que el k-ésimo bit de a[i] es 0. <br />
Dem (super resumida): <br />
* (=>) Supongamos que no existen a[i] y k como se describen arriba. Supongamos que aplicamos M operaciones o menos. Necesitamos multiplicar cada impar (las divisiones no generan pares) plus una extra previa para el último número que dividimos. Contradicción, necesitamos más de M.<br />
* (<=) Sea i el índice descrito, y k el bit. Aplicamos M-k veces el protocolo de tocar otros dos impares (uno lo dividimos, otro lo multiplicamos). Finalmente dividimos k veces el a[i] mientras que multiplicamos impares. Luego de a lo sumo M operaciones (dependiendo de si a[i] era impar) se obtienen todos pares.<br /><br />
Ahora que sabemos que la rta <= M, a cada impar se le asigna un valor g[i] que es la cantidad mínima de divisiones que necesita para hacerse par. <br /><br />
Se puede demostrar que, dada R la respuesta, el algoritmo que “parifica multiplicando” R impares y “parifica dividiendo” los M-R restantes es posible si y sólo si la sumatoria de los g[i] (de los M-R) es menor o igual a R.<br />
* Por lo tanto se puede aplicar el algoritmo greedy para encontrar la solución que “parifica dividiendo” los de menor g[i].<br />
Código: <a href="https://pastebin.com/VSTUxsDY">https://pastebin.com/VSTUxsDY</a>
</div></div><br /><br />
<h3>L</h3><div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Este problema consta de dos partes. Una es encontrar las 6 combinaciones posibles de bolsitas que se pueden armar, a las que enumeramos:<br />
1. LLLL<br />
2. OOOO<br />
3. TTTT<br />
4. LLSS<br />
5. LSTT<br />
6. LLOO<br /><br />
Podemos suponer greedymente que los paquetes 5 y 6 están a lo sumo una vez, puesto que si no también existe una solución usando los paquetes (3,4) y (1,2) respectivamente por cada parcito de los anteriores que da lo mismo.<br />
A partir de ahí, es fácil ver que si seguimos el orden 4-3-2-1 encontramos la solución óptima. Por lo tanto solo es necesario probar los 4 casos sobre la paridad de bolsas hechas con p5 y p6 y seguir con el algoritmo.<br />
También hay una solución sin probar los 4 casos que sigue un orden greedy particular de eliminación que se la deja al lector como ejercicio.<br />
Código: <a href="https://pastebin.com/cFVUDHBH">https://pastebin.com/cFVUDHBH</a>
</div></div><br /><br />Martín Villagrahttp://www.blogger.com/profile/04539435412394117022noreply@blogger.com2tag:blogger.com,1999:blog-5066062691948591225.post-80851530415787520812017-05-24T13:51:00.003-03:002017-10-21T14:57:35.071-03:00[VIVO] - Latam Scoreboard World Final ICPC 2017Sigue los equipos latinoaméricanos filtrados: <a href="http://bit.ly/2rhxAI6">http://bit.ly/2rhxAI6</a>
<br/><br/><br/><div class="separator" style="clear: both; text-align: center;"><a href="http://bit.ly/2rhxAI6" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://1.bp.blogspot.com/-W26ULquiwQQ/WeuKVCJ5a7I/AAAAAAAADGk/KoBTyjFgjO4Qaor0jKf87toAY0xN8hfmACLcBGAs/s400/2017-10-21-145654_1294x729_scrot.png" width="400" height="225" data-original-width="1294" data-original-height="729" /></a></div>Mariano Crosettihttp://www.blogger.com/profile/15432656094614740834noreply@blogger.com0tag:blogger.com,1999:blog-5066062691948591225.post-8840201510702948362016-11-19T00:34:00.000-03:002016-11-21T15:51:28.672-03:00Solucionario Regional Latinoamérica 2016Pese a algunos percances con el problema E, podemos decir que la prueba fue entretenida y satisfactoria. Solamente un equipo logró resolver todos los problemas (nuestras felicitaciones al equipo de Cuba). Mariano y yo (Martín) colaboramos en la sede de Buenos Aires durante la competencia, mientras que Pablo tomó el rol de coach de los equipos de nuestra universidad (Universidad Nacional de Rosario).<br /><br /><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-kExdm5tfeqI/WC-b-okL5QI/AAAAAAAACSQ/mvwP_SDc5TM7ehDQtdA_1bP4sU1Iib53ACLcB/s1600/15123192_1350799838287163_5995594349609889980_o.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="213" src="https://2.bp.blogspot.com/-kExdm5tfeqI/WC-b-okL5QI/AAAAAAAACSQ/mvwP_SDc5TM7ehDQtdA_1bP4sU1Iib53ACLcB/s320/15123192_1350799838287163_5995594349609889980_o.jpg" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Caloventor, junto a los equipos de la UNR que participaron en el Regional</td></tr>
</tbody></table>
<span id="goog_1731092393"></span><span id="goog_1731092394"></span><br />
<br />
<h2>
Links Útiles</h2>
<ul>
<li>Enunciados: <a href="http://maratona.ime.usp.br/resultados16/contest.pdf">http://maratona.ime.usp.br/resultados16/contest.pdf</a></li>
<li>Juez para submitear: <a href="https://www.urionlinejudge.com.br/judge/es/problems/origin/136">https://www.urionlinejudge.com.br/judge/es/problems/origin/136</a> (al menos hasta que se suban los problemas a <a href="https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=752">live archive</a>)</li>
<li>Standings: <a href="https://icpc.baylor.edu/regionals/finder/southamerica-south-2016/standings">https://icpc.baylor.edu/regionals/finder/southamerica-south-2016/standings</a></li>
</ul>
<br />
<br />
<h2>
Soluciones</h2>
Aquí les dejamos el solucionario, el cual es una traducción mas o menos fiel del realizado por FFAO (Fernando Fonseca) en su blog: <a href="https://algorithmmarch.wordpress.com/2016/11/15/final-brasileira-da-maratona-2016/">https://algorithmmarch.wordpress.com/2016/11/15/final-brasileira-da-maratona-2016/</a>. Incluimos una solución detallada del problema E que aunque no fue parte de la prueba oficial, nos parece un problema muy interesante.
<br />
<br />
<h3>A</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>Trivial</h3>
Basta con probar todas las posibilidades e imprimir la mejor de ellas.
</div>
</div>
<br />
<br />
<h3>
B</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
Greedy</h3>
Considere un grafo donde dos elementos están conectados si son compatibles. Si un vértice posee grado menor que $A$, es imposible que forme parte de la respuesta (no importa que otros vértices elijamos, el vértice nunca cumple la condición de tener al menos $A$ vecinos), por lo que podemos removerlo.<br />
<br />
De la misma forma, si nuestro grafo posee $N$ vértices y uno de ellos tuviera grado mayor que $N-B$, es imposible que forme parte de la respuesta, y podemos removerlo.<br />
<br />
Continuamos quitando vértices hasta que ningún vértice precise ser removido. Lo que nos queda es un conjunto válido, por definición, y debe ser el mayor posible, pues solamente removimos vértices que nunca iban a ser parte de la respuesta.<br />
<br />
Resta pensar sobre como implementar esto eficientemente: el truco es mantener un set de vértices ordenados por su grado, posibilitando identificar rápidamente los vértices de menor y mayor grado. Cuando un vértice es removido, el grado de todos sus vecinos es actualizado en el set.<br />
En C++ la forma más fácil de implementar esto es usar un arreglo gr[i], que guarde el grado de $i$ y un set< pair< int, int > > que guarde pares de la forma (gr[i], i). El orden por defecto del set va a priorizar la primera coordenada (el grado), por lo cual podemos usar begin() y end() para obtener los vértices de menor y mayor grado. Para decrementar el grado de un vértice $i$ puedo quitar (gr[i], i) del set, hacer gr[i]-- y luego agregar (gr[i], i) al set.
</div>
</div>
<br />
<br />
<h3>
C</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
Geometría/Combinatoria</h3>
Este es uno de esos problemas tramposos: el enunciado lo hace parecer más difícil de lo que es.<br />
<br />
Es intuitivo que si un conjunto de puntos cumple con la propiedad de que al rotarse vuelva a ser el mismo, este conjunto puede ser dividido en varios polígonos regulares (por ejemplo, si $\alpha = 120º$, para que al rotar el conjunto vuelva a ser él mismo, el conjunto debe formar varios triángulos equiláteros, y el centro de rotación debe ser el centro de los triángulos).<br />
<br />
Ahora viene la parte crucial del problema: las coordenadas son enteras, por lo que (quitando los cuadrados) los polígonos regulares no existen! (prueba, para los curiosos: <a href="http://hrcak.srce.hr/file/2836">http://hrcak.srce.hr/file/2836</a>)<br />
<br />
Teniendo en cuenta esto, las únicas cosas que pueden rotarse y volver a ser lo mismo son puntos (exactamente sobre el punto de rotación) y segmentos de recta (rotadas $180º$, con centro de rotación en el punto medio). Sabiendo esto, la única posibilidad que necesitamos considerar es cuando el $\alpha = 180º$.<br />
<br />
El resto es combinatoria: cada par de puntos puede ser rotado a partir de su punto medio, entonces podemos tomar todos los pares y calcular sus puntos medios, que son los posibles centros de rotación. Para cada posible centro, si este tiene $P$ pares que pueden ser rotados por él, para cada $0<=p<=P$ existen $\binom{P}{p}$ subconjuntos de tamaño $2p$ que utilizan ese punto como centro de rotación.
</div>
</div>
<br />
<br />
<h3>
D</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
Greedy/Geometría</h3>
El área del diagrama es la suma de las áreas de los triángulos formados por dos atributos adyacentes. Si existen $n$ atributos, el área de un triángulo adyacente a los atributos $P_i$ y $P_{i+1}$ puede ser dada calculada por la fórmula $\frac{1}{2} \sin(\frac{2 \pi}{n}) P_i P_{i+1}$. Los dos primeros términos son constantes para todos los triángulos, por lo que basta escoger el orden de los valores de P que maximizen la suma de los productos $P_i$ $P_{i+1}$.<br />
<br />
Intuitivamente, queremos que el mayor valor de $P$ contribuya lo máximo posible para la respuesta, entonces lo mejor sería multiplicarlo con los siguientes dos mayores valores de P. Continuando el razonamiento, si $P$ está ordenado de forma que $P_1$ es el mayor y $P_n$ es el menor, el mejor orden es $..., P_7, P_5, P_3, P_1, P_2, P_4, P_6, ...$.
</div>
</div>
<br />
<br />
<h3>
E</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
Estructura/Wavelet Tree o Segment Trees</h3>
<h3>Solución 1</h3>
Este problema requiere conocimiento de una estructura llamada Wavelet Tree. Permite responder a la pregunta "cual es el $k$-ésimo menor elemento en el intervalo $[i,j]$ de un arreglo dado?" en $O(\log{}n)$.<br />
<br />
Esta estructura puede ser usada para resolver el problema "Batata Quente" de la primera fase de la maratona de Brasil (<a href="http://maratona.ime.usp.br/prim-fase16/maratona.pdf">http://maratona.ime.usp.br/prim-fase16/maratona.pdf</a>) en $O(n\log{}n)$ (La solución oficial tenía complejidad de $O(n \sqrt{n}\log{}n)$, usando sqrt decomposition.) <br />
<br />
Hay una explicación disponible en Quora: <a href="https://www.quora.com/How-can-you-build-a-data-structure-on-an-array-that-returns-kth-order-statistics-on-subarrays-in-logarithmic-time">https://www.quora.com/How-can-you-build-a-data-structure-on-an-array-that-returns-kth-order-statistics-on-subarrays-in-logarithmic-time</a>.<br />
También se encuentra descripta en el paper de los autores, que también explican como hacer la actualización de intercambiar dos elementos adyacentes (es muy simple): <a href="https://www.dcc.uchile.cl/~jperez/papers/ioiconf16.pdf">https://www.dcc.uchile.cl/~jperez/papers/ioiconf16.pdf</a>.
<br />
<br />
<h3>Solución 2</h3>
Existe otra solución posible para responder la misma query de los Wavelet Trees en $O(\log^2{}n)$, que consiste en construir un segment tree sobre el rango de valores. Por ejemplo, si el arreglo $V$ es $V[0]=2, V[1]=0, V[2]=1, V[3]=2, V[4]=3$, entonces en la hojas guardaremos $hoja[0]=\{1\}, hoja[1]=\{2\}, hoja[2]=\{0, 3\}, hoja[3]=\{4\}$ (una especie de inversión del arreglo). La operación del segment tree va a ser la unión (sobre multiset) y para responder las queries debemos usar búsqueda binaria sobre cada nodo.
<br />
Nota: No es necesario codearse un árbol balanceado, podemos usar la STL (ver: <a href="http://codeforces.com/blog/entry/11080">http://codeforces.com/blog/entry/11080</a>)
</br>
</br>
<h3>Solución 3</h3>
Es posible hacer otra solución utilizando segment trees persistentes y contestar la query en $O(\log{}n)$. Esta solución alternativa fue explicada por Victor Agnez en el blog de FFAO (la cual inspiró la explicación que sigue). El código está disponible en: <a href="http://ideone.com/HdOhu1">http://ideone.com/HdOhu1</a>.
</br>
</br>
Para facilitar la explicación, primero vamos a considerar un problema más simple: a partir de un arreglo de números, mantener un segment tree que responda cuantos elementos con valor entre $a$ y $b$ existen. Esto es fácil, construimos un segment tree donde la hoja $i$-ésima guarda la cantidad de veces que el número $i$ aparece en el arreglo. Utilizamos la operación suma para construir el segment tree. Lo que tenemos es que cada nodo representando el rango $[a, b]$ nos dice cuantos valores hay en ese rango.
</br>
En este segment tree es fácil buscar el $K$-ésimo menor elemento: lo hacemos recorriendo el árbol desde la raíz. Suponiendo que estamos en el nodo que representa el intervalo [a,b], el hijo izquierdo contiene la cantidad de elementos en el rango $[a, \frac{a+b}{2}]$. Si esa cantidad es menor o igual a $K$, entonces el $K$-ésimo menor elemento se encuentra en el hijo izquierdo. De lo contrario, el $K$-ésimo menor está en el hijo derecho. Si llegamos a una hoja, encontramos el $K$-ésimo.
</br>
</br>
Volviendo al problema E: vamos a suponer que para cada prefijo del arreglo, tenemos ese segment tree. Ahora, si miramos el $j$-ésimo segment tree y un nodo dentro del mismo representando el intervalo $[a, b]$, él mismo va a tener guardado cuantos valores en el rango $[a, b]$ hay en las posiciones $[0, j]$ del arreglo original. La clave de esta solución está en notar que si un nodo del $j$-ésimo segment tree guarda cuantos hay en el intervalo $[0, j]$, podemos restarle el mismo nodo pero del $(i-1)$-ésimo segment tree y obtener cuantos hay en el intervalo $[i, j]$ (es decir tomamos cuantos hay en o antes de $j$ pero le restamos los que aparecen antes de $i$). Es decir que, restando nodo a nodo el $j$-ésimo y el $(i-1)$-ésimo segment tree, puedo obtener un nuevo segment tree que me cubriría sólo el subarreglo $[i, j]$. Recorriendo este segment tree, puedo encontrar el $K$-ésimo menor de la misma forma ya explicada. El detalle está en que no es necesario crearse el nuevo segment tree entero, basta con ir haciendo la restas entre los dos árboles a medida que voy necesitando los valores.
</br>
</br>
Por último, notar que el $i$-ésimo segment tree es muy semejante al segment tree de prefijo $(i-1)$: apenas se agrega un elemento (sólo se hizo una operación de modificación). Por lo que utilizando persistencia (que aprovecha la memoria en común entre los árboles) podemos efectivamente tener los árboles de todos los prefijos.
</div>
</div>
<br />
<br />
<h3>
F</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
Trivial/Simulación</h3>
Basta simular el camino del robot como se describe en el enunciado..
</div>
</div>
<br />
<br />
<h3>
G</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
Strings/KMP</h3>
Es uno de los problemas más elegantes de la prueba, es difícil de entender al principio pero el código es muy corto.<br />
<br />
El primer paso es relativamente intuitivo: como para los matching no importa que letra es cual, debemos representar las strings de una forma que no importe cual letra es cual.<br />
<br />
Tal vez la forma más obvia sería sustituir la primera letra que aparece por "a", la segunda letra que aparece por "b", y así sucesivamente. Pero esa representación no es muy práctica pues es difícil determinar las representación de substrings de manera eficiente: por ejemplo, la representación de la substring "cd" en "abcdef" es "ab", y eso traería problemas más adelante.<br />
<br />
Una posibilidad mejor de representación: representamos cada letra por la distancia entre esa letra y su última ocurrencia (si la letra no hubiese aparecido antes, ponemos -1). Por ejemplo: la string "awawww" se vuelve "-1 -1 2 2 1 1". Es fácil ver que con esta representación conseguimos lo que queríamos: dos strings que matchean (por ejemplo, "awa" y "dcd"), tendrán siempre la misma representación.<br />
<br />
Una vez hecha la conversión, casi que podemos usar KMP, pero todavía tenemos el problema de las substrings: por ejemplo, la substring "waw" en "awawww" (-1 -1 2 2 1 1) tiene la representación -1 -1 2, mientras que la substring correspondiente de la representación es -1 2 2. Podemos ver que pasó aquí: el primer 2 está apuntando hacia afuera de la substring, por lo que debería ir un -1. Ese es el único cambio que debemos hacer al calcular la representación de una substring.<br />
<br />
Recordemos que hace el algoritmo de KMP: repetidamente se toman dos prefijos iguales y compara si los próximos caracteres concuerdan. En el código del KMP, el cambio anterior puede ser traducido en un único if: en la comparación de los próximos caracteres, si alguno de ellos apunta fuera del prefijo, debe ser considerado como un -1.
</div>
</div>
<br />
<br />
<h3>
H</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
Greedy</h3>
Puede ser razonable pensar en una DP para resolver este problema, pero los límites son demasiado grandes. Vamos a analizar mejor las condiciones del enunciado. Vemos que se deben satisfacer las siguientes condiciones:<br />
Dentro de las primeras $K$ noches, ninguna es eliminada.<br />
Dentro de las primeras $2K+1$ noches, como máximo 1 es eliminada.<br />
Dentro de las primeras $3K+2$ noches, como máximo 2 son eliminadas.<br />
...<br />
<br />
Si fuéramos a eliminar una noche de entre las primeras $2K+1$, ciertamente será la noche de costo máximo entre las noches $K+1$ y $2K+1$.<br />
<br />
Extendiendo esto para las primeras $3K+2$ noches, escogemos la noche de mayor costo entre $2K+2$ y $3K+2$ y necesitamos decidir si vale la pena eliminar una noche de entre las primeras $2K+1$. La segunda noche escogida será entonces la mejor noche de entre las primeras $2K+1$, o la segunda mejor noche entre $2K+2$ y $3K+2$.<br />
<br />
Continuando este proceso, vemos que el problema puede ser resuelto por un algoritmo greedy: es mantenida una priority queue con las mejores noches a eliminar hasta el momento. Cuando la noche $i$ es procesada, se verifica si vale la pena remover alguna noche ya escogida para incluir la noche $i$. La excepción es si $i$ es múltiplo de $K+1$, en tal caso no es necesario remover ninguna noche anterior para incluir $i$.
</div>
</div>
<br />
<br />
<h3>
I</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
Optimización DP</h3>
Primero debemos responder a la pregunta: Cuál es el menor costo posible para unir las casas de la ciudad $i$ a la ciudad $j$ a una misma estación? Una propiedad de conjuntos de puntos en una recta es que el punto que minimiza la suma de las distancias a los demás es la mediana del conjunto; de esta forma si consideramos la posición de todas las casas, la estación debe ser construida en la ciudad en que se encuentra la casa de posición mediana. El cálculo del costo en si puede ser efectuado con algunos pre-cálculos y sumas parciales.<br />
<br />
Lo que resta del problema es modelar y optimizar una DP. Para optimizarla debemos aplicar lo que se conoce como "divide and conquer trick". Pueden buscar información sobre esta técnica de optimización en Google, material en inglés hay de sobra. Vamos a intentar en las próximas semanas subir al blog material en español sobre esto.
</div>
</div>
<br />
<br />
<h3>
J</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
Matemática</h3>
Si el coach retorna a la sala inicial después de recorrer $T$ túneles, eso significa que la sala inicial es parte de un ciclo, cuyo tamaño es un divisor de $T$ mayor que 1. Es posible probar que el número de grafos en los cuales la sala forma parte de un ciclo de tamaño $C$ disminuye a medida que $C$ aumenta, luego queremos que $T$ tenga la menor cantidad de divisores posibles, y si los tiene, que sean grandes: esto sucede si $T$ es primo, pues los únicos divisores de T serán 1 y él mismo. Así, basta imprimir el mayor primo menor o igual $N$.<br />
<br />
Prueba, si alguien está interesado: vamos a calcular el número de grafos en que el vértice 1 es miembro de un ciclo de tamaño $C$. Podemos escoger los demás vértices del ciclo de $\binom{N-1}{C-1}$ maneras, y el orden de los vértices en el ciclo de $(C-1)!$ maneras. Los demás vértices pueden tener un túnel yendo hacia cualquier lugar, teniendo así $(N-1)^{N-C}$ posibilidades. Así, el número final es $\binom{N-1}{C-1} (C-1)! (N-1)^{N-C}$, el cual decrece a medida que aumenta $C$ (perdemos un factor de $N-1$ para agregar un factor menor).
</div>
</div>
<br />
<br />
<h3>
K</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
Flujo</h3>
Vamos a resolver el problema suponiendo que ya sabemos quien es el hombre lobo, después basta repetir el algoritmo para cada uno de los participantes.<br />
<br />
La elección óptima para los que pueden votar al hombre lobo es claramente votar en él, por lo que no necesitamos preocuparnos por esas personas. Considerando que el hombre lobo recibe $X$ votos, él gana si alguien recibe por lo menos $X$ votos, o si alguna de las dos personas que puede elegir el lobo tiene al menos $X-1$ votos.<br />
<br />
En el fondo, este es un problema bien tradicional de flujo máximo: Cada persona recibe una unidad de flujo de la fuente, que debe enviar para alguna de sus dos posibles elecciones (realizar un voto). Cada elección puede recibir como máximo $X-1$ o $X-2$ votos, y esta es la cantidad de flujo que puede pasar para la fuente. Los aldeanos ganan si todos consiguen votar, o sea, si el flujo máximo fuese igual al número de personas que deben escoger sus votos.
</div>
</div>
<br />
<br />
Martín Villagrahttp://www.blogger.com/profile/04539435412394117022noreply@blogger.com16tag:blogger.com,1999:blog-5066062691948591225.post-72944422466638853722016-09-22T22:16:00.002-03:002016-09-25T17:24:44.281-03:00Solucionario TAP 2016Aquí un solucionario respectivo al contest del Torneo Argentino de Programación (TAP) 2016. El solucionario NO es oficial. (Los enunciados pueden encontrarlos <a href="http://torneoprogramacion.com.ar/wp-content/uploads/2016/09/tap2016.pdf">aquí</a>). Los resultados finales de todo el país se encuentran <a href="http://torneoprogramacion.com.ar/2016/09/21/resultados-tap-2016/" target="_blank">aquí</a>. Este año tuvimos la oportunidad de organizar el TAP en nuestra sede.<br />
<br />
Éste es el orden de dificultad (creciente) de los problemas que pensé aún antes del TAP (fui problemsetter!):<br />
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Spoiler</a></div><div><div class="spoiler" style="display: none;">
A, J / L, C, F, H, B, G / D, E, I, K. Muy probablemente difiera con lo que muchos piensen pués es una prueba dónde se han concentrado mucho los problemas en la franja media (abarcando muy bien el espectro de medio-fácil a medio-difícil).</div>
</div>
<br />
<br />
Pienso que en general ha sido una muy bella prueba con problemas muy divertidos y creo que podría hablar por todos los problemsetters si digo que todo salió bastante bien.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://4.bp.blogspot.com/-Dm_BaOdiBsY/V-SXgKNV2oI/AAAAAAAACPQ/9fUReEtW_qAHWmqiAimrDJ6UBOD1tYYJgCK4B/s1600/photo632328678028715962.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="480" src="https://4.bp.blogspot.com/-Dm_BaOdiBsY/V-SXgKNV2oI/AAAAAAAACPQ/9fUReEtW_qAHWmqiAimrDJ6UBOD1tYYJgCK4B/s640/photo632328678028715962.jpg" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><span style="font-size: small;"><i>Los equipos compitiendo en la sede de Rosario</i></span></td></tr>
</tbody></table>
<br />
A continuación el solucionario, que hicimos junto a Martín. <br />
<br />
<h3>
Problema A</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
(ad hoc)</h3>
El problema trivial. Imprimir "S" o "N" según si había o no la letra 'i'.<br />
Solución Python de una línea:<br />
<span class="im">print("SN"["i"in input()])</span></div>
</div>
<br />
<br />
<h3>
<span class="im">Problema B</span></h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
<span class="im">(programación dinámica)</span></h3>
<span class="im">- Dividimos los puntos que no son E ni S en dos conjuntos: A = { E+1, E+2, ... S-1 } (mod N) y B = { E-1, E-2, ... S+1 } (mod N)<br />- Sea A_i y B_i los i-esimos de los respectivos conjuntos en el orden mencionado (partiendo desde E), observar que el recorrido óptimo recorre los A_i y B_i en orden.<br />- El problema puede resolverse con programación dinámica en N^2. <br />- La recursion nos queda de la forma f(i,j,flag) respuesta óptima de llegar a S habiendo recorrido hasta A_i del conjunto A y B_i del conjunto B, flag indica si nos encontramos en i o j. <br />- Se podría prescindir de flag ya que dado un par (i,j) sin saber cual corrresponde a A y cual a B podemos determinarlo (los puntos son bien de A y otros de B) y podemos considerar que la segunda componente del par es el elemento donde nos encontramos.</span></div>
</div>
<br />
<br />
<h3>
<span class="im">Problema C</span></h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
<span class="im">(DFS)</span></h3>
<span class="im">- Guardamos para cada materia la cantidad de correlativas no aprobadas y marcamos como no aprobadas a todas las materias. <br />- Al principio la respuesta de cantidad de materias en el sistema es 0. <br />- Cada vez que aprobamos una materia la marcamos como aprobada y la "procesamos". El procesamiento consiste en ver si está aprobada y la cantidad de correlativas no aprobadas es 0, de ser así incrementamos la respuesta, disminuimos en 1 la cantidad de correlativas no aprobadas de sus hijos y los procesamos. <br />- Ver que la condición del procesamiento se satisface sólo una vez. Luego sólo una vez se recorrerán a sus hijos. El procesamiento es invocado sólo por el padre y cuando se aprueba la materia. La complejidad es O(N+M).</span></div>
</div>
<br />
<br />
<h3>
<span class="im">Problema D</span></h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
<span class="im">(geometría, giro ó intersección círculos ó set)</span></h3>
<span class="im">- Para cada par de puntos (x,y) calculamos todos los posibles valores de lados de un triángulo semejante al original con un lado igual al segmento formado por estos puntos (6 casos).<br />- Podemos utilizar intersección de círculo para determinar donde se encontrarían el tercer punto (dos posibilidades para cada elección de lados).<br />- Chequeamos si estos puntos existen en nuestro input. Lo podemos hacer con un set en O(log(N)).<br />- Complejidad: O(N^2 log(N)).<br />- Tener cuidado de no estar contando repetidos. Tener en cuenta el caso donde el triángulo usado es isósceles.</span><br /><br />
<h4>
<span class="im">Solucion alternativa:</span></h4>
<h4>
<span class="im"></span></h4>
<span class="im">Esta solución me dio AC, según mi análisis de complejidad es O(N^3). Aunque puede que las restricciones propias de la geometría euclídea y puntos enteros hagan que sea mucho menor.<br />- Creamos map< long long, bitset<1000> > mp[MAXN]. Donde para cada vertice v y distancia a otro vertice d mp[v][d] representa el conjunto de vertices a distancia d de v con subíndice mayor que v.<br />- Para cada par de puntos (x,y) calculamos por proporcionalidad todos los posibles valores de lados de un triángulo semejante al original con un lado igual al segmento formado por estos puntos (6 casos). Este punto es igual a la solucion anterior. Ver que solo nos importan si estas distancias al cuadrado son enteras.<br />- Siendo l1 y l2 el tamaño de los lados para el par de vértice (x,y) obtenido en un caso del apartado anterior actualizamos la respuesta con size( interseccion(mp[x][l1],mp[y][l2]) ).<br />- Si usamos un unordered_map (mas el uso de bitset para representar conjuntos), la cantidad de operaciones es de N cubo. Aunque hay que resaltar que la interseccion posiblemente sea O(N) pero con una constante muy baja (1/64) por el uso de bitset. Además la intersección sólo se ejecuta si l1 y l2 calculados resultan enteros y además l1 y l2 existen como claves en mp[x] y mp[y] respectivamente. Lo cual no siempre sucede y hace más rápida a nuestra solución.</span></div>
</div>
<br />
<br />
<h3>
<span class="im">Problema E</span></h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
<span class="im">(grafos DFS)</span></h3>
<span class="im">- La observación clave es: "Existe una cadena de botones que independientemente de donde me halle me lleve al 1 sí y sólo sí para todo par de estados existe una cadena de botones que independientemente de cual de los dos me halle me lleva al estado 1".<br />- => trivial<br />- <= induccion sobre el conjunto de estados donde posiblemente estoy. La premisa me permite ir reduciendo en 1 la cantidad aplicando la cadena que me da.<br />- Luego si consideramos el grafo cuyos vertices son pares de aplicaciones (i,j) y existe una arista a (a,b) si apretando un boton paso del estado i al a y del j al b. (N^2 vértices </span><span class="im"><span class="im">N^2M</span> aristas). Existe existe una cadena de botones que independientemente de cual de las dos aplicaciones A,B me halle me lleva a la 1 sii existe un camino (A,B) a (1,1).<br />- Tenemos que chequear que para todas las aplicaciones a,b del vertice (a,b) se pueda alcanzar el vertice (1,1) en el grafo descripto.<br />- El grafo tiene </span><span class="im"><span class="im"><span class="im">N^2</span></span> vertices y </span><span class="im"><span class="im"><span class="im">N^2</span></span>M aristas. La complejidad total es de O(</span><span class="im"><span class="im"><span class="im">N^2</span></span>M). </span></div>
</div>
<br />
<br />
<h3>
<span class="im">Problema F</span></h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
<span class="im">(greedy)</span></h3>
<div>
Para resolver este problema se deben hacer primero varias observaciones.</div>
<div>
1) Sólo las letras D y R importan, podemos eliminar todas</div>
<div>
las demás letras.</div>
<div>
2) Si hay dos D o dos R consecutivas en un nombre es lo mismo que solamente tener una.</div>
<div>
3) La tercera es que si existe un DR en un nombre, entonces de forma greedy podemos pintar ambas letras de fucsia</div>
<div>
(sumando 1 a la respuesta) y ya borrarla de la palabra.</div>
<div>
Utilizando todas estas observaciones, los posibles nombres se reducen a tres: D, R y RD.</div>
<div>
<br /></div>
<div>
Resta
ver como combinar estas palabras de forma óptima. Si tenemos al menos
una D, se la puede juntar con una RD: DRD. Aplicando 3) esta DRD se
transforma en una D (y le suma uno a la respuesta).</div>
<div>
Análogamente R+RD se transforma en R (sumando uno a la respuesta). </div>
<div>
En
cambio si no tenemos ninguna R ni ninguna D, solamente nos queda juntar
las RD (aquí se desperdician las dos letras de los extremos).</div>
<div>
Por último, cuando sólo nos quedan D's y R's, la cuenta es muy simple. La fórmula quedaría:</div>
<div>
if(cant_RD>0){</div>
<div>
if(cant_D+cant_R>0) ans += cant_RD</div>
<div>
else ans += cant_RD - 1</div>
<div>
}</div>
<div>
ans += min(cant_D, cant_R)</div>
<div>
</div>
</div>
<br />
<br />
<h3>
Problema G</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
(trie)</h3>
- El costo en el camino es el xor del costo de las aristas.<br />
- Usando la promoción ir del nodo A al B cuesta lo mismo haciendo cualquier camino (usar dos veces un tramo sale gratis).<br />
- Tomando una ráiz arbitraria R, costo(A,B) = costo(A,R) xor costo(B,R).<br />
- Sean val[A] = costo(A,R) (podemos computarlo con un DFS). Ahora la respuesta para un nodo v es max_{a in V} val[a] xor val[v]. Este es un problema clásico lo podemos resolver pensando a cada val[v] como string de 0's y 1's y construyéndonos un trie con ellas (con el bit mas significativo a la izquierda). Luego para cada v obtenemos la respuesta utilizando el trie, siempre eligiendo el caracter más conveniente "encendiendo" bits en el resultado siempre que sea posible. </div>
</div>
<br />
<br />
<h3>
Problema H</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
(programación dinámica)</h3>
- Sea f(X,Y,N) la respuesta a nuestro problema podemos hacer programación dinámica.<br />
- Observar que f(X,Y,N) cuando Y>0 y N>1 depende solo posiblemente de f(X,Y-1,N-1) y f(X-1,Y-1,N-1) (cuando Y==0 o N==1 es un caso base). La cantidad de estados visitados es NN ya que Y y N son recuperables uno del otro.<br />
- Tirar el parámetro que podemos recuperar y hacer la DP en N<span class="im"><span class="im"><span class="im">^2</span></span></span>.</div>
</div>
<br />
<br />
<h3>
Problema I</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
(matemática, ec lineal modular, grafo, Prim)</h3>
<div>
La idea principal es esta: Imaginar un grafo donde los vértices son
las ranas y las aristas indican el tiempo (absoluto) en que esas dos ranas se
encuentran. Pensamos ahora como resolver el problema utilizando este grafo. Un algoritmo posible es
similar al Prim, comenzando desde la rana infectada. La idea es que en cada paso del Prim, de todas las ranas no infectadas se elija la se encuentre primero con una infectada, luego esta rana se infecta. Así el árbol recubridor representaría la historia de las infecciones.</div>
<div>
En lugar
de generar el grafo explícitamente (el cual puede tener infinitas
aristas), para cada nodo expandido, buscaremos el tiempo de encuentro
con las ranas no infectadas. Es importante tomar en cuenta solamente los
encuentros después de que la rana fue infectada (razón por la cual este algoritmo no es exactamente Prim).</div>
<div><br />
Resta ver como calcular los tiempos de encuentro:</div>
<div>
<br /></div>
<div>
Supongamos que tenemos dos ranas i y j, y queremos saber el próximo encuentro después del tiempo t, llamemosle t'.</div>
<div>
Fijamos en que punto del patrón se van a encontrar: llamemosle m (es decir t'%K==m)</div>
<div>
Calculamos
en que posición se encuentra cada rana en el tiempo t + el tiempo que
le lleva alcanzar el primer m, llamemosle p_i y p_j.</div>
<div>
Si después de una ciclo completo del patrón la rana i avanza c_i charcos, se puede inferir que los puntos en los que t'%K==m</div>
<div>
tienen la forma:</div>
<div>
t' = p_i + x * c_i (mod n)</div>
<div>
<br /></div>
<div>
Utilizando estos datos podemos plantear la siguiente ecuación:</div>
<div>
p_i + x * c_i = p_j + x * c_j (mod n)</div>
<div>
<br /></div>
<div>
Resolviendo esta ecuación es posible encontrar el primer tiempo de encuentro de las ranas (si es que existe).</div>
<div>
Luego hacemos un for para todos los posibles m y tomamos el mínimo.</div>
</div>
</div>
<br />
<br />
<h3>
Problema J</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
(greedy)</h3>
- Ir poniendo las palabras en orden decreciente de longitud, empezando una nueva columna de ser necesario anchura igual a la palabra a insertar es óptimo.</div>
<div>
</div>
</div>
<br />
<br />
<h3>
Problema K</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
(teoría de juegos, greedy ó programación dinámica)</h3>
Por simplicidad dividimos en dos partes la explicación. <br />
<br />
<h4>
Parte I: </h4>
- Existe un único camino simple de M a P. Veamos el problema como un camino M <-> P y "subarboles" colgantes de el mismo conformado por los nodos que no pertenecen al camino.<br />
- Inicialmente M y P pertenecen al camino. Para todo vertice no perteneciente al camino visitarlo implica "salirse del camino" y no se puede volver a entrar. Tanto M como P sólo pueden visitar un único de los subárboles mencionados.<br />
- La respuesta óptima de salirse del camino desde un vértice v es fácilmente calculable con un DFS. El problema quedó reducido a un camino y un vértice que se desprende de cada nodo del camino:<br />
M - o - o - o - o - o - o - P<br />
| | | | | | | | |<br />
o o o o o o o o<br />
<br />
Si bien creo que hay una solución que yo categorizaría de greedy para este problema (se basa en de observaciones matemáticas) esta es la solución con DP que hice, lo bueno es que es muy simple entender que funciona.
<br />
<div>
<br />
<br />
<h4>
Parte II:</h4>
- En lo sucesivo c[i] es el valor de cada vértice del camino, ca[i] del que se desprende de él con i=0..len-1. Donde len es la cantida de nodos del camino M-P, el nodo 0 representa a M y len-1 a P. Además consideramos len impar (si no és se puede agregar un nodo con c y ca igual a 0) y mid será la posición del vértice del medio.<br />
- Es fácil calcular con programación dinámica (en el código pueden ver las fórmulas)<br />
- sumMid[i]: el acumulado de c[i] de i hasta el mid.<br />
- toMid[i]: estando en el nodo i la máxima cantidad de puntos podemos hacer yendo a lo sumo hasta mid.<br />
- fromMid[i]: estando en el nodo mid la máxima cantidad de puntos podemos hacer yendo para el lado donde se encuentra i, y llegando a lo sumo hasta un nodo antes de i.<br />
- Ahora resolveremos el problema con programación dinámica, siendo f(i,j) la cantidad de puntos si ambas juegan óptimo arrancando M en la posición i del camino y P en la j. Nosotros queremos calcular f(0,len-1).<br />
<b>Caso base:</b><br />
f(mid-1,mid+1) = max ( ca[mid-1] - max(ca[mid+1],ca[mid]+c[mid]) , ca[mid]+c[mid] - ca[mid+1] )<br />
Como M juega primero puede elegir salirse del camino (primera opción) o ir al medio. P juega el máximo posible a consecuencia de ello.<br />
<b>Paso inductivo:</b> (Acá i y j están a distancia mayor que dos)<br />
<b>(A)</b> i puede elegir irse del camino y ganar ca[i], con lo cual j puede seguir por el camino hasta a lo sumo un vértice antes de dicho nodo. Así la óptima es en este caso: ca[i] - max( sumMid[j] + fromMid[i] , toMid[j] )</div>
<div>
<br />
<b>(B)</b> i puede elegir seguir en el camino, sumando c[i+1]. Luego j puede:<br />
<b>(B.1)</b> seguir en el camino sumando c[j-1]. A lo cual el juego sigue en f(i-1,j-1). Teniéndose el valor óptimo para j de esta opción (dado que i ya eligió seguir en el camino) resulta: c[j-1] - f(i+1,j-1)<br />
<b>(B.2)</b> abandonar el camino en j, teniéndose una fórmula análoga al apartado <b>(A)</b> (pero ahora es j el que abandona el camino y ya se ha avanzado M hasta i+1): ca[j] - max( sumMid[i+1] + fromMid[j] , toMid[i+1] )<br />
Así la fórmula para el apartado <b>(B)</b> es: c[i+1] - max( c[j-1] - f(i+1,j-1) , ca[j] - max( sumMid[i+1] + fromMid[j] , toMid[i+1] ) ) (j elije la mejor opción de ambas).<br />
Quedando el max entre las fórmulas de (A) y (B).<br />
- La dinámica f(i,j) se basa sólo en el estado anterior f(i-1,j-1). Sólo se visitan O(N) estados. Podemos tirar un parámetro y recuperarlo del otro y la complejidad total será O(N).</div>
</div>
</div>
</div>
<br />
<br />
<h3>
Problema L</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<h3>
(ad hoc, greedy)</h3>
Existen muchas soluciones posibles, a continuación la que yo creo más corta y simple. El problema nos define un árbol, y luego nos da una cadena. Nuestra tarea es decir si esta cadena es un camino en el árbol o no. Notar que en este árbol el padre es siempre mayor a sus hijos, por lo que todo camino válido va a estar dividido en dos partes: una ascendente y otra descendente. El máximo M de la cadena nos dara el punto de separación. <br /> <br />
Para los elementos que estén en la parte ascendente tenemos que chequear que su anterior es el hijo. Para los elementos que estén en la parte descendente tenemos que chequear que su siguiente es el hijo. Para chequear si a es hijo de b podemos utilizar directamente la definición dada en el enunciado: b>2 and (a+1==b or a+2==b).<br /> <br />
Por último debemos asegurarnos que la parte ascendente y la descendente sean disjuntas. Para esto basta con solo verificar que el anterior y siguiente de M son distintos.
</div>
</div>Mariano Crosettihttp://www.blogger.com/profile/15432656094614740834noreply@blogger.com12tag:blogger.com,1999:blog-5066062691948591225.post-84643491288589312462016-08-30T21:58:00.000-03:002016-10-21T11:57:43.058-03:00Introducción de cero a la programación competitivaEscribo esta entrada porque varios me han pedido consejo de por dónde empezar a introducirse a la programación competitiva.<br />
<a href="https://1.bp.blogspot.com/-dx2rSVRXvsk/V8edwZdIUXI/AAAAAAAAAL8/qPeUtwf9quQ2dVMFr-Q_-Oh0FX4rvjfzACLcB/s1600/competitiveprogramming.png" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><br /></a>
<br />
Voy a suponer que tienen conocimientos de programación básicos. Quizás más adelante agregue alguna referencia de dónde pueden aprender a programar pero creo que hay muchísimo más material de esto que de programación competitiva en sí.<br />
<br />
Recomiendo seguir los siguientes tres puntos para empezar de 0. No están hechos para hacerse en orden sino a la par. Esto puede llevar tiempo, así que a no desmotivarse. Más abajo listo material útil. Y por último doy algunos tips que se me fueron ocurriendo a medida que escribía esto.<br />
<br />
<u><span style="font-size: large;">Introduciéndose:</span></u><br />
<br />
1. Si nunca submiteaste un problema, create una cuenta en USACO (ver
link del compilado) y ver la primer seccion para ver como es la
dinámica, el formato que tenés que respetar, de como submitear una
solución en un juez online.<br />
<br />
2. Ver el libro de Steven Halim. La sección introductoria y de problemas ad
hoc es un buen punto de partida. Otro portal por el que se puede empezar
es URI que tiene problemas ordenados por dificultad y podemos elegir
los más fáciles.<br />
<br />
3. Crearse una cuenta en Codeforces. Podés empezar haciendo problemas A de
Div2 (los más fáciles y tratar de hacerlos). Si tu respuesta es
incorrecta te permite ver por qué y cómo debería ser la respuesta
correcta del programa.<br />
<br />
4. Seguir el libro Halim en secciones posteriores (como Greedy, Programación Dinámica, Grafos) para incorporar conocimientos teóricos nuevos que nos van a permitir resolver un espectro más amplio de problemas. Siempre es importante no quedarnos con los problemas fáciles que se nos ocurren rápidamente ni tratar sólo los tan difíciles que debamos ver siempre la solución, sino ir ampliando de a poco nuestro horizonte y dejar un tiempo razonable el problema en el tintero. Ojo, que también es importante que si no salió el problema, buscar la solución tratar de implementarla por uno mismo y entender por qué no me salió (tal vez algo teórico que no sabía y deba aprender, o quizás alguna manera de enfocarlo distinto), incorporar este nuevo conocimiento y pensar cómo podría ayudarme a resolver otros problemas distintos.<br />
<br />
<u><span style="font-size: large;">Material útil:</span></u><br />
<br />
<b><span style="font-size: small;">USACO</span></b>: <a href="http://train.usaco.org/usacogate">http://train.usaco.org/usacogate</a><br />
Es una página de entrenamiento para competencias (IOI) de secundario de los norteamericanos.<br />
Muy amena introducción. Recomendable para hacer la primer sección como introducción a la dinámica de la progrmación competitiva.<br />
Recomiendo seguir la guía si estás entrenando para el secundario pero sino no sugiero hacerlo, creo que hay lugares mejores orientados a la ICPC.<br />
Es motivante el hecho de que necesitás hacer los problemas de una sección para pasar a la siguiente pero a veces traba un poco, en estos casos recomiendo buscar alguna solución en internet y submitearla.<br />
<br />
<b>Codeforces:</b> <a href="http://codeforces.com/">http://codeforces.com/</a><br />
Es una comunidad muy piola que organiza competencias online periódicamente. También hay algunas guías de temas teóricos desde básicos hasta muy avanzados.<br />
Súper recomiendo crearse una cuenta acá y empezar a ver problemas. Los problemas están clasificados en dos divisiones (Div2, fáciles y Div1 avanzados). Además en las competencias suelen estar ordenados por dificultad creciente.<br />
La página tiene una sección llamada Gym, muy útil para practicar con tu equipo competencias oficiales anteriores ya que simula el scoreboard como si estuvieras compitiendo con las personas que participaron antes.<br />
<br />
<b>Training Camp Argentina:</b> <a href="https://sites.google.com/site/trainingcampargentina2016/">https://sites.google.com</a><a href="https://www.blogger.com/null">/site/trainingcampargentina2016/</a><br />
De los training camps argentinos da para hablar mucho, pero en resúmen es un evento HIPER recomendable (diría que hasta escencial!) para participar. Organizado por gente muy buena onda y copada, con mucho trabajo solidario aporta para que este tema de las competencias se extienda en todo el país.<br />
Siempre decimos que sin ayuda de estos eventos nunca hubiéramos clasificado a nuestra primer mundial. Se hacen en junio generalmente y consiste en un curso donde todos los días tener clases teóricas a la mañana y simulacro de competencia por las tardes. Es muy intensivo pero re vale la pena hacerlo!!<br />
Acá puse la página de la edición 2016 pero si googlean por año, aparecen todos lo anteriores. Tiene slides de teoría que se dio y links a las competencias que se simularon.<br />
<br />
<b>Live Archive </b><a href="https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8">https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8</a><br />
Uno de los tantos jueces en línea. Acá tenemos, por ejemplo, los regionales de años anteriores. Aunque particularmente no recomiendo quemarse problemas de estos así pueden simularlos después con sus equipos.<br />
<br />
<b>UVa Online Judge:</b> <a href="https://uva.onlinejudge.org/">https://uva.onlinejudge.org/</a><br />
Otro juez en línea. El libro de Halim tiene referencias a problemas que se encuentran acá.<br />
<br />
<b>Competitive Programing (Libro de Halim)</b><br />
<a href="https://sites.google.com/site/stevenhalim/">https://sites.google.com/site/stevenhalim/</a><br />
Este libro lo compramos nosotros. No se comercializa acá y hay que esperar algunos meses a que llegue acá en Argentina, pueden intentar buscar alguna versión por Internet.<br />
Yo creo que está bueno para empezar, de hecho nosotros empezamos por acá y le debemos mucho mucho a Steven Halim. Tuvimos la oportunidad de agradecerle personalmente y sacarnos una foto con él! (siempre asiste como invitado a las finales)<br />
Está bueno que presenta un panorama general de las categorías de problemas existentes y cada sección tiene un desarrollo que llegua a conceptos avanzados, dando código de ejemplo y referencias a problemas de jueces online.<br />
También existe el libro Programming Challenges de Steven Skiena, que tiene un approach un poco menos centrado a las competencias pero más claro en cuánto a las introducciones a los temas.<br />
<br />
<b>URI online Judge </b>(https://www.urionlinejudge.com.br/judge/en/login)<br />
Es un juez brasilero. Cada vez más está incorporando y traduciendo problemas al español. Una de las ventajas de URI frente a otros portales es que tiene los problemas clasificados por dificultad.<br />
Ésto esta muy bueno, entre muchas varias otras cosas porque cuando uno empieza no tiene la capacidad de discernir cuando un problema es complicado y no está a su alcance ó cuando simplemente le tiene que dedicar más tiempo. Y está bueno empezar con problemas fáciles, especialmente si uno aprendió a programar hace poco es probable que tenga muchos errores las primeras veces.<br />
<br />
<b>e-maxx.ru:</b> <a href="http://e-maxx.ru/algo/">http://e-maxx.ru/algo/</a><br />
Es una página con muchísimo material avanzado en ruso. Los rusos son la vanguardia en esto así que es común ver material en ruso. Yo siempre usé Google para traducir pero quizás Yandex sea mejor.<br />
<span style="font-size: large;"></span><br />
<span style="font-size: large;"><br /></span>
<span style="font-size: large;"><u>Tips:</u></span><br />
<ul>
<li>Qué es un <i>Juez en Línea</i>? Es un sitio donde hay problemas y puedes submitear código para que checkee si resuelve el problema. <br /><br />Es muy importante que a la hora de hacer problemas no sólo los pienses, sino programes y submitees. Es muy común al principio tener errores en los que nuestro programa anda bien en CASI todos los casos pero hay alguno que falla porque no lo contemplamos. De hecho no cometer errores implementando el problema, aún teniendo una idea correcta es una gran parte de la competencia. Por eso creo que es escencial que para mejorar hagan problemas que ESTEN SEGUROS que van a poder submitear el código en algún juez y verificar que sea correcto.</li>
<li>Los jueces corrigen MUY ESTRICTAMENTE como van a ver si hacen la primera
sección del USACO. Son máquinas, así que una mayúscula en vez de
minúscula, un espacio o un salto de línea de más hará que nuestra
solución este MAL.</li>
<li> Programar en C++: siempre escoger el lenguaje, dentro de los que
permiten las competencias, es una cuestión de gustos. Pueden elegir Java
si prefieren. Yo recomeidno C++ por varias razones:<br /><ol>
<li>Creo que hay más material en C++ que en Java.</li>
<li>Python creo que fue introducido para incentivar la participación ya que
se está enseñando mucho en primeros años. En la ICPC se lo está
comenzando a adoptar pero aún tiene varios problemas que genera que NO
todos los problemas puedan ser resueltos en python. Esto se debe a que
usa los tiempos límite de ejecucción de Java y no tiene tiempos límite
propios, puede que muchas veces Python sea más lento y un programa que
resuelve satisfactoriamente y en la complejidad requerida el problema y
aún así el veredicto sea Time Limit Exceeded .</li>
<li>Por sobre C, C++
tiene la STL con muchas estructuras ya hechas que aporta mucha ventaja
(set, map, priority_queue, etc).</li>
</ol>
</li>
<li>Considerar ir al training camp es una
excelente idea. Si sos alumno de
la FCEIA, año a año se ha tratado que los gastos de traslado sean
cubiertos con apoyo del departamento de Computación. A veces el evento cuenta con sponsors que cubren gastos de
alojamiento. El respeto y relevancia que la ICPC inspira así como los
resultados que hemos logrados han hecho tomar conciencia a los
profesores de REPROGRAMAR fechas de examenes. No sólo en Computación
sino desde la Escuela de Ciencias Exactas hay una voluntad de hacer
prosperar esto. Así que si de algún modo es impedimento para su
participación algún compromiso académico, esto se puede llegar a ver y
tratar razonablemente.</li>
<li> Rodeate de gente con la que puedas compartir y apoyarte. La idea que
surgan talleres, entrenadores y materias optativas sobre Programación
Competitiva es para satisfacer la necesidad de estos espacios. En nuestro inicio tuvimos
la suerte de formar el equipo y apoyarnos entre nosotros fue muy
importante para seguir avanzando. </li>
</ul>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://1.bp.blogspot.com/-dx2rSVRXvsk/V8edwZdIUXI/AAAAAAAAAL8/qPeUtwf9quQ2dVMFr-Q_-Oh0FX4rvjfzACLcB/s1600/competitiveprogramming.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="240" src="https://1.bp.blogspot.com/-dx2rSVRXvsk/V8edwZdIUXI/AAAAAAAAAL8/qPeUtwf9quQ2dVMFr-Q_-Oh0FX4rvjfzACLcB/s400/competitiveprogramming.png" width="400" /></a></div>
<br />
Mariano Crosettihttp://www.blogger.com/profile/15432656094614740834noreply@blogger.com5tag:blogger.com,1999:blog-5066062691948591225.post-70219576498785525582016-05-29T03:28:00.000-03:002016-05-29T05:52:00.728-03:00Un sueño hecho realidad, somos LATAM Champions!!Un proyecto que empezó en Febrero de 2014, cuando armamos el equipo con el único objetivo de viajar a Marruecos.<br />
<br />
Tras dos años entrenándonos duramente, compartimos muchísimas experiencias con toda la comunidad a la cual le debemos tanto, aprendimos un montón y llegamos acá para disputar el Latam en nuestra última competencia juntos.<br />
Sabíamos lo difícil que era pero también que era posible.<br />
<br />
Las 5 horas de competencia pasaron como relámpago. Tuvimos un momento de inspiración en la mitad de competencia y en menos de media hora metimos 3 problemas quedando 2 problemas arriba de los equipos Brasileros con quienes estábamos disputando.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://3.bp.blogspot.com/-DP_wD7bulZg/V0qMbh9xSJI/AAAAAAAABPM/0xQ3D2bWO6sk5OR4e4DGnj78PQ3cI68xACLcB/s1600/13245297_10153827610539118_4014517904736596149_n%2B%25281%2529.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="240" src="https://3.bp.blogspot.com/-DP_wD7bulZg/V0qMbh9xSJI/AAAAAAAABPM/0xQ3D2bWO6sk5OR4e4DGnj78PQ3cI68xACLcB/s320/13245297_10153827610539118_4014517904736596149_n%2B%25281%2529.jpg" width="320" /></a></div>
<br />
Las dos últimas horas fueron muy duras, llenas de tensión, especulación y nervios. Todo lo que habíamos aprendido nos lo jugábamos en ese momento, ahí se definía todo.<br />
Finalmente terminamos viviendo un sueño. Fue la perfecta culminación del proyecto en conjunto que venimos llevando durante estos dos años.<br />
Proyecto que nos llevó a conocer lugares y personas maravillosas y a ocupar muchos de nuestros ratos libres.<br />
<br />
Queríamos agradecer a todos los que nos han acompañado en todo este camino.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-lz-9Yn-xR9k/V0qErsmMUbI/AAAAAAAABOE/9dBv2hQCl3ksmPwMaqGdd1-maP_sqa2rgCLcB/s1600/foto%2Bcon%2Bleo%2By%2BNio.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="320" src="https://2.bp.blogspot.com/-lz-9Yn-xR9k/V0qErsmMUbI/AAAAAAAABOE/9dBv2hQCl3ksmPwMaqGdd1-maP_sqa2rgCLcB/s320/foto%2Bcon%2Bleo%2By%2BNio.jpg" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">con Leo y Nico (escondido)</td></tr>
</tbody></table>
<br />
Primero de todo, agradecer a toda la comunidad de Argentina, que hicieron posible nuestra primera clasificacion. Especialmente a <b>Nico Álvarez</b> y <b>Leopoldo Taravilse</b>, nuestros coaches y precursores de los training camps de Argentina, que nos ayudaron a encaminarnos en nuestro entrenamiento a la primera Regional y siempre estuvieron con nosotros.<br />
<br />
Empezamos sin saber mucho por donde empezar y decidimos comprar el libro "Competitive Programming" de <b>Steven </b>y<b> Felix Halim</b> (https://sites.google.com/site/stevenhalim/). Este libro nos sirvió una banda como guía y lo seguimos durante todo nuestro primer año a rajatabla. Es un honor para nosotros habernos encontrado en persona con Steven y haber podido saludarlo en persona durante nuestra última World Final en Tailandia.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-q-lD0AplDPA/V0qFiyuz-hI/AAAAAAAABOU/v5yL7WFbOrIdKbThDEd4a4SG_jCiWdzxwCLcB/s1600/IMG_8743.JPG" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="240" src="https://3.bp.blogspot.com/-q-lD0AplDPA/V0qFiyuz-hI/AAAAAAAABOU/v5yL7WFbOrIdKbThDEd4a4SG_jCiWdzxwCLcB/s320/IMG_8743.JPG" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><i>con Steven Halim y sus hijos</i></td></tr>
</tbody></table>
<br />
También a los organizadores del training camp de Campinas, especialmente a <b>Rodolfo Azevedo</b> que le pone muchas energías para que éste se realize y nos invitó estos dos años. Este training tiene un nivel increíble y nos ayudó mucho en nuestras participaciones para los dos mundiales.<br />
Un agradecimiento a todos los entrenadores que allí acudieron, especialmente a <b>Tomasz Idziaszek</b>, por su gran didáctica, a quién le agarramos mucho cariño.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-3PwgfGDsMJU/V0qH2htFMRI/AAAAAAAABOo/aYXpxwoEAngytgr2OcvXMb9tf5YqCvJiACLcB/s1600/10945607_10152812200909118_4997827291930968483_n.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="240" src="https://3.bp.blogspot.com/-3PwgfGDsMJU/V0qH2htFMRI/AAAAAAAABOo/aYXpxwoEAngytgr2OcvXMb9tf5YqCvJiACLcB/s320/10945607_10152812200909118_4997827291930968483_n.jpg" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">en el Training Camp de Brasil 2015</td></tr>
</tbody></table>
<br />
Por otro lado a toda la comunidad latinoamericana en general, en especial a los organizadores de la <b>Red de Programacion Competitiva</b>, es un placer contar con una comunidad donde prima la buena voluntad, donde más allá de la competitividad siempre hay un ambiente de compañerismo y solidaridad.<br />
También queremos agradecer al <b>Ministerio de Ciencia y Tecnología de la Nación</b> que apoya económicamente esta actividad para que año tras año los equipos de Argentina estemos en la mundial representando a la Argentina, así como a <b>Irene Loiseau</b>, la directora de nuestra región, que genera que todo esto sea posible. Por nuestra parte queremos agradecer a la <b>Universidad Nacional de Rosario</b> por apoyarnos y permitir que sea posible viajar para entrenar a Brasil. Sin ese apoyo nos hubiera sido imposible sortear las dificultades económicas.<br />
<br />
También agradecer al departamento de Computación de nuestra facultad. Son los que primero nos apoyaron pagando algunos pasajes a pesar del poco presupuesto que poseen. Especialmente queremos agradecer el eterno apoyo del profesor <b>Dante Zanarini</b> que siempre se movió para darnos una mano, a <b>Exequiel Rivas</b> que organizó por primera vez el TAP en Rosario laburando a pulmón junto a <b>Gabina Bianchi</b> que siempre nos estuvo acompañando con muchísimo entusiasmo. También queremos agradecer el apoyo constante de <b>Ana Casali</b>, la directora de departamento que siempre nos apoyó y nos escuchó.<br />
<br />
Por último, a nuestros familiares y amigos que nos han acompañado a lo largo de estos años, aguantando a veces nuestros aburridos monólogos sobre los problemas que hacíamos, je.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-zMCEeyKCaPA/V0qLp3_bB7I/AAAAAAAABPE/oRnbwnqf1DQS3ID08okz5X-u0jvfU73RQCLcB/s1600/13318407_1200880469945768_882696521_n.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="207" src="https://3.bp.blogspot.com/-zMCEeyKCaPA/V0qLp3_bB7I/AAAAAAAABPE/oRnbwnqf1DQS3ID08okz5X-u0jvfU73RQCLcB/s320/13318407_1200880469945768_882696521_n.jpg" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><i>con nuestras familias antes de irnos a Brasil</i></td></tr>
</tbody></table>
<br />
Ojalá nuestra experiencia sirva para dar impulso a futuras generaciones de competidores del interior del País, tenemos intención de publicar alguna guía sobre lo que fuímos haciendo nosotros durante estos años para que los estudiantes nuevos que aparezcan no estén tan perdidos como estuvimos nosotros los primeros meses.<br />
<br />
Probablemente nos despedidamos como competidores (quién sabe?), pero esperamos impulsar la participación dentro de nuestra universidad.<br />
<br />
<br />
Mariano Crosetti<br />
Martín Villagra<br />
Pablo Zimmermann<br />
<div>
<br /></div>
Anonymoushttp://www.blogger.com/profile/08383373879221108220noreply@blogger.com0tag:blogger.com,1999:blog-5066062691948591225.post-5090817420426239612016-04-16T18:29:00.001-03:002016-04-18T00:02:26.585-03:003° competencia de la Red de Programación Competitiva (2016)<div class="separator" style="clear: both; text-align: center;"><a href="https://acm.javeriana.edu.co/maratones/2016/03/scoreboard.htm" target="_blank" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://4.bp.blogspot.com/-SkBeG737yd0/VxRN3vNjp9I/AAAAAAAABOc/Hb36MqfrM54rQDL4oDZW6tXMOFbfWwnpQCLcB/s640/Screenshot%2Bfrom%2B2016-04-17%2B23-56-10.png" /></a></div>
<br />
Aquí va el solucionario. Recordar que si no conocen algún término o algoritmo mencionado es recomandable que dejen de leer la solución y aprendan sobre ese algoritmo antes de seguir.
<br />
<br />
<h2>
Juez Online y Enunciados </h2>
<a href="https://acm.javeriana.edu.co/maratones/2016/03/">https://acm.javeriana.edu.co/maratones/2016/03/</a><br />
<br />
<br />
<br />
<br />
<h2>
Soluciones</h2>
<div>
<br /></div>
<h3>
A. Acronyms</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Este era el trivial de la competencia.</div></div><br /><br />
<h3>
B. Tobby Bones</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Este tipo de problemas son clásicos problemas de Segment Tree. Para hacer este tipo de problemas se los debe tener bien claro. En el segment tree cada nodo representa un rango del arreglo, pues bien en este problema cada nodo guarda los números que aparecen en ese rango. Ahora, para poder contestar la consulta eficientemente debemos guardar estos números usando un árbol balanceado de búsqueda (por ejemplo Treap, Red-Black Tree, Splay Tree, etc).
<br/>
<br/>
Existe una estructura oculta dentro del estándar de C++ que implementa esto, por lo que evitamos programar uno desde cero. (ver <a href="http://codeforces.com/blog/entry/11080">http://codeforces.com/blog/entry/11080</a>)</div></div><br /><br />
<h3>
C. Tobby and Query</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Otro problema de segment tree. En este caso aprovechamos que los valores posibles del arreglo son pequeños. En cada nodo guardamos una máscara de bits que indica que números aparecen bajo ese rango, la operación es el or de bits(|) y luego para devolver la cantidad simplemente contamos la cantidad de bits encendidos (la función __builtin_popcount(x) suele ser útil).</div></div><br /><br />
<h3>
D. Standard Deviation</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Solo debemos trabajar las formulas. En particular conviene definir el númerador de forma recursiva (respecto a n), de esta forma precalculamos todos los posibles númeradores. Una vez hecho esto por cada query obtenemos el numerador correspondiente, lo dividimos por (n-1) y por último la raíz cuadrada.</div></div><br /><br />
<h3>
E. Tobby and the LED display</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Este problema es trivial, solo hay que hacer lo que piden sin complicarsela mucho.</div></div><br /><br />
<h3>
F. Triangular Test II</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Para este tipo de problema que parecen basarse en alguna propiedad matemática que seguramente desconocemos, conviene crear una solución bruta e intentar encontrar algo de útilidad. Si hacemos esto nos daremos cuenta que la respuesta puede ser 1, 2 o 3 (nunca más que 3). Por lo tanto generamos todos los números triangulares y todas las sumas de dos números triangulares y los vamos marcando en un arreglo de 10^6. Por cada n, si la posición correspondiente está marcada imprimimos 1 o 2, si no la respuesta es 3.</div></div><br /><br />
<h3>
G. Tobby and the line game</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
La respuesta a este problema es: ((xR-xL)*(xR-xL)+(yR-yL)*(yR-yL))/6.</div></div><br /><br />
<h3>
H. Painting the Wall</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Por cada celda a pintar tenemos que decidir si la misma es pintada por una linea vertical o por una horizontal. El hecho de que tenemos que elegir entre cosas y que esas decisiones afectan a las otras decisiones nos lleva a pensar que se trata de un problema de flujo. Notemos que las lineas son horizontales o verticales, por lo que intuimos cierta bipartitud e intentamos armar un grafo. Ponemos las lineas horizontales a la izquierda y las verticales a la derecha del grafo. Luego agregamos por cada celda una arista conectando las dos lineas que le corresponden. Este grafo es bipartito.
<br/>
Ahora, si miramos el problema presentado en este grafo, necesitamos seleccionar un conjunto de vértices que cubran todas las aristas. Esto se conoce como el cubrimiento mínimo (min vertex cover) y para grafos bipartitos es igual al maximum matching (ver teorema de König). Podemos generar el matching usando el algoritmo de flujo de preferencia (por ejemplo Dinic) y luego reconstruir el cubrimiento (es decir cuales son los vértices que elegimos) utilizando el teorema de König.</div></div><br /><br />
<h3>
I. Tobby on Tree</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Este problema es una aplicación casi directa de lo que se conoce como Heavy Light Decomposition. Se recomienda leer y entender bien este tema antes de intentar hacer este problema.
<br/>
<br/>
La solución en sí es esta: Generamos la descomposición y por cada cadena tenemos un Segment Tree (algo muy común cuando se hace Heavy Light), usando el GCD como operación.</div></div><br /><br />
<h3>
Problem J. Tobby Stones</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Este problema era difícil porque requería implementar un árbol balanceado de búsqueda, con varias cosas. En primer lugar si no tenemos la operación de dar vuelta (la de tipo 1), el problema se puede hacer con segment tree (para consultar sobre rangos) con lazy propagation (pues necesitamos generar cambios sobre rangos eficientemente). En cada nodo guardo cuantos blancos y cuantos negros hay en el rango que él cubre y la operación es la suma. Generar la operación del Lazy (es decir las alteraciones) es algo más complicado. La operación necesita poder alterar un rango y poder combinarse con otra alteración en O(1). Nosotros tomamos que puede valer 0 (no operación), 1 (flip), 2 (set white) o 3 (set black). Para el lazy necesitamos saber como se altera el valor del nodo por cada operación (lo cual es obvio) y como combinar alteraciones. Para esto último hacer una tablita de 4x4 y analizar: Si hago un set white y luego un flip es como si hubiera hecho un set black. Si hago un set black y luego un set white es como si hubiera hecho sólo un set white. Y así llenar toda la tablita y usarla para combinar las alteraciones.
<br/>
<br/>
Si llegamos hasta acá sólo nos queda las de tipo 1 (reverse), pero para hacer este tipo de queries necesitamos un árbol balanceado de búsqueda, podríamos hacer una sqrt decomposition pero las cotas parecen demasiado grandes para esto. El problema de dar vuelta apareció como el problema más hard del TAP 2014 (problema K). Se resuelve usando lazy propagation sobre el árbol de búsqueda. Porqué un árbol de búsqueda? Bueno podemos guardar un arreglo en un árbol de búsqueda como un conjunto de pares (posición, valor).
<br/>
<br/>
Recomendamos aprender a usar Treaps como árbol de búsqueda por defecto pues ellos son los más cortos y fáciles de codear. El tutorial de <a href="http://e-maxx.ru/algo/treap">http://e-maxx.ru/algo/treap</a> es muy bueno (usen el traductor de Yandex, que es mejor para el ruso). Allí explica como usar el Treap para representar arreglos, lo cual nos da la posibilidad de hacer operaciones bastante locas (como por ejemplo borrar una posición de un arreglo) eficientemente. EL Treap es una estructura muy poderosa, es posible hasta simular arreglos de 2^64 (reutilizando memoria).
</div></div><br /><br />
<h3>
K. Tobby and Seven</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Como la cantidad de bits swapeados es poca, podemos probar todas las permutaciones <b>distintas</b>. Tienen que empezar por permutaciones que generen números altos y luego cada vez más bajos hasta encontrar una múltiplo de 7, ahí imprimirlo y cortar (pues sino da Time Limit).
<br/>
<br/>
Notar que necesitamos generar todas las permutaciones <b>distintas</b> (cada permutación que chequeamos tiene que ser diferente a la que chequeamos anteriormente). Para hacer esto podemos recorrer todas las máscaras de k bits (2^20), las que tienen un número de bits encendidos igual a la cantidad de bits encendidos de los bits swapeados del número original son permutaciones válidas.
</div></div><br /><br />
<h3>
L. Tobby and Prime Sum</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Utilizamos una dinámica que siempre solemos utilizar, que es una dinámica sobre los digitos. Notar que si encontramos la respuesta para cuando l=0 y r cualquiera, llamemosla g(r), podemos hacer g(r)-g(l-1) y encontrar la respuesta al problema, por lo que efectivamente reducimos un parámetro de la query.
<br/>
<br/>
La dinámica consiste en ir "armando" cada número desde el dígito más significativo hasta el menor. En su estado lleva la posición (si estoy poniendo el primer, segundo dígito, etc) y cuanto vale la suma hasta ahora de todos los dígitos que ya puse (<=4500). En cada paso voy a probar poner cada uno de los 10 dígitos. Hay que tener cuidado de solamente generar los números <=r. Para eso agregamos una flag al estado. Cuando la flag esta activa solo puedo poner digitos menores o iguales al que tiene r en esa posición, si pongo un dígito menor entonces los siguientes digitos pueden ponerse cualquier cosa (total el número ya es menor: 1234xxx es menor a 1235010 sin importar que haya en las x) por lo que desactivo el flag.
<br/>
<br/>
Esta parte depende mucho de como lo implementen, pero a nosotros lo que nos quedó fue para cada posible suma de dígitos, cuantos números forman esa suma. Por lo cual generamos todos los primos <=4600 y para cada uno de ellos sumamos la cantidad de números que lo formaban.
</div></div>Martín Villagrahttp://www.blogger.com/profile/04539435412394117022noreply@blogger.com11tag:blogger.com,1999:blog-5066062691948591225.post-3134950296972375262015-11-16T15:10:00.000-03:002015-11-16T16:51:27.469-03:00Solucionario Regional Latinoamérica 2015Primero que nada agradecer a los organizadores de la competencia y al departamento de nuestra carrera que nos apoyaron siempre. Después casi dos años entrenando tuvimos un resultado muy gratificante, logramos ser campeones de nuestra región! (Argentina, Perú, Bolivia, Uruguay, Chile y Paraguay). Estamos muy contentos por haber clasificado a las siguientes World Finals, a realizarse en Tailandia. Felicitaciones a todos los equipos que participaron. Esperamos que en los siguientes años otros equipos vivan lo que nosotros vivimos.
<br />
<br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: left; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://3.bp.blogspot.com/-rBG66TUL_aw/VkoYntPAHUI/AAAAAAAABDc/wu4gXhQE0V0/s1600/IMG_20151114_202657_HDR.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="480" src="http://3.bp.blogspot.com/-rBG66TUL_aw/VkoYntPAHUI/AAAAAAAABDc/wu4gXhQE0V0/s640/IMG_20151114_202657_HDR.jpg" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Los tres equipos de Rosario: Flower Power, Caloventor en Dos (con nuestro elefante) y [Listas, Turings y Lambdas]</td></tr>
</tbody></table>
<h2>
Scoreboard final</h2>
<a href="http://bombonera.org/board/" target="_blank">http://bombonera.org/board/</a><br />
<br />
<h2>
Juez Online y Enunciados </h2>
<a href="https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=702">https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=702</a><br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://2.bp.blogspot.com/-aPtnbm_R27M/VkoYnjlCC6I/AAAAAAAABDY/abI1AiIHgZo/s1600/IMG_20151114_181424_HDR.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="http://2.bp.blogspot.com/-aPtnbm_R27M/VkoYnjlCC6I/AAAAAAAABDY/abI1AiIHgZo/s400/IMG_20151114_181424_HDR.jpg" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Nuestra compu al final de la competencia</td></tr>
</tbody></table>
<br />
<br />
<h2>
Soluciones</h2>
<div>
<br /></div>
<h3>
A - At most twice</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Hay una <a href="https://es.wikipedia.org/wiki/Programaci%C3%B3n_din%C3%A1mica">dinámica</a> que siempre aniquila a los problemas de este estilo que es ir avanzando sobre la cadena de caracteres de la representación decimal del número, conservando información útil y decir si se puede encontrar o no un número como el buscado. Generalmente llevamos además en el estado si el prefijo que venimos procesando es igual al del número dado o menor (para saber que dígito poner si decidimos cambiar asegurándonos que estamos analizando números menores al dado). Aquí la información adicional era la cantidad de cada dígito usada. Luego reconstruir adecuadamente para encontrar la mayor solución. Complejidad: O(3^10 * 18 * 2).
También puede resolverse más fácil con greedy.</div></div><br /><br />
<h3>
B - Blood groups</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
El problema nos pide si se puede encontrar una asociación padre-gen del hijo para cada uno de los genes activos del hijo, sabiendo que cada padre puede dar a lo sumo un gen. Eso es buscar si existe un matching completo (para la cantidad de genes del hijo) en un <a href="https://es.wikipedia.org/wiki/Grafo_bipartito">grafo bipartito</a> dado por los padres y los genes activos del hijo, lo cuál se puede resolver con cualquier algoritmo de <a href="https://es.wikipedia.org/wiki/Red_de_flujo">Max Flow</a>. Notar que cualquier padre no matcheado puede dar el gen 0 sin alterar la configuración del hijo excepto que tenga cada uno de los N genes. En ese caso, puede dar cualquiera de los que ya le hayan pasado otro padre excepto que el hijo no tenga ningún gen, en cuyo caso la respuesta es negativa.</div></div><br /><br />
<h3>
C - Cake cut</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Si fijamos el punto i que elige Carol entonces Carla intenta elegir el punto j que está "más al medio" (minimiza la diferencia de áreas). Podemos para cada i calcular su j pero es O(n^2). La clave es notar que si ya calcule el j de un i puedo aprovechar esto para calcular el j correspondiente al i+1: el j de este i+1 tiene que estar sí o sí igual o más adelante que el j del i. Teniendo esto en cuenta podemos ir aumentando los índices i y j (de tal manera que siempre el corte i-j quede a la "mitad") en O(n).</div></div><br /><br />
<h3>
D - D as in Daedalus</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Como quiere obtener la mayor puntuación absoluta posible siempre le conviene sumar la mayor cantidad de puntos. Osea jugar la mayor carta tal que el banco pague. Simple simulación.</div></div><br /><br />
<h3>
E - Exposing corruption</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Primero observar que el grafo es <a href="https://es.wikipedia.org/wiki/Grafo_bipartito">bipartito</a>. Ahora veamos que pasa con cada <a href="https://es.wikipedia.org/wiki/Grafo_conexo">componente conexa</a> de este grafo. Se puede ver que si elijo cambiar de partido a uno, voy a tener que cambiar todos los pertenecientes a su componente conexa sí o sí. Por lo tanto por cada componente conexa voy a guardarme el costo de cambiar de partido a todos los pertenecientes a la misma y la diferencia en cantidad de personas que genera. Calculado esto se puede hacer una <a href="https://es.wikipedia.org/wiki/Problema_de_la_mochila">dinámica estilo mochila</a>, donde la capacidad es el presupuesto, los objetos son cada componente conexa y quiero maximizar la cantidad de personas en el primer partido. Dar vuelta todo y hacer lo mismo para el otro partido.</div></div><br /><br />
<h3>
F - Fence the vegetables fail</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Recordemos que cuando un punto esta dentro de un polígono cualquier semirecta que salga de ese punto se interseca con el poligono una cantidad impar de veces. Nuestro algoritmo "tira" semirectas horizontales hacia la izquierda. Para eso hacemos un <a href="https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/">sweep line</a> de izquierda a derecha. Por cada punto (x, y) veo cuantas rectas verticales pasaron por ese x anteriormente. Para esto podemos usar un <a href="https://en.wikipedia.org/wiki/Fenwick_tree">bit (fenwick tree)</a> o un <a href="https://en.wikipedia.org/wiki/Segment_tree">segment tree</a> o hasta segment tree con lazy.</div></div><br /><br />
<h3>
G - Galactic taxes</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Cada camino es una recta en el gráfico costo en función del tiempo (pues sumo los A y B de las artistas que lo componen). Si dibujamos imaginariamente las rectas de todos los caminos posibles, para cada t nos quedaríamos con la que menor costo tiene. Si miramos la grafica notamos que tiene un solo máximo (parecido a la idea del <a href="http://wcipeg.com/wiki/Convex_hull_trick">convex hull trick</a>, buscar). Por lo cual podemos hacer <a href="https://en.wikipedia.org/wiki/Ternary_search">ternary search</a> sobre la respuesta. En cada paso se fija el t y se hace un <a href="https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">Dijkstra</a>.</div></div><br /><br />
<h3>
H - Height map</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Las caras que siempre van a estar van a ser la de abajo y la de los cuatro costados. Para las caras superiores (horizontales) podemos hacer un flood fill (dos casillas están conectadas si son adyacentes y tienen la misma altura) y contar la cantidad de regiones.<br />
Para las caras laterales paralelas al eje x podemos hacer un algoritmo para cada par de filas adyacentes . Vamos de izquierda a derecha y tenemos tres estados: la cara actual mira hacia al norte, la cara mira hacia el sur, o no hay cara(las casilla del norte y la del sur están a igual altura). Cuando cambio a alguno de los dos primeros sumo 1 a la respuesta.<br />
Para calcular las verticales paralelas al eje y simplemente giro 90° y hago el mismo algoritmo.<br />
<br />
También se puede resolver contando aristas y vértices y usando la propiedad C = A-V+2</div></div><br /><br />
<h3>
I - Identifying tea</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Trivial de la competencia</div></div><br /><br />
<h3>
J - Just a bit sorted</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Este problema era el hard de la competencia. Hay dos formas de encararlo. Una idea es con <a href="https://es.wikipedia.org/wiki/Programaci%C3%B3n_din%C3%A1mica">Programación Dinámica</a> pensando que pasa cuando se agranda K pero no sabemos de que manera se resuelve. La otra es hacer fuerza bruta con los casos más pequeños e intentar buscar una formula que determine un elemento de tabla (N,K) dado los anteriores. Nosotros estuvimos un rato intentando esto último pero no nos salió en la competencia. La formula es complicada pero no imposible de hallar. Usando está formula (no es necesario) se puede incluso reducir la complejidad a N lgN, o hacer programación dinámica en N^2. Notar que para Q = N y Q > N el número de posibilidades es él mismo.</div></div><br /><br />
<h3>
K - Keep it energized</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Definimos f(i) = mínimo costo de llegar desde i hasta el final. La respuesta al problema es f(0).<br />
<br />
Al comienzo f(0...n-1)=inf y f(n) =0. Recorremos en orden descendente de nivel los shops. Para cada shop=(L, S, C) calculo la máxima posición p a la que puedo llegar desde L con energía S usando <a href="https://en.wikipedia.org/wiki/Binary_search_algorithm">búsqueda binaria</a>. Luego cuando tomo en cuenta este shop puedo llegar desde L a cualquier posición en [L, p].<br />
<br />
En particular me conviene saltar a la posición que me cueste menos llegar al final. Por lo que el costo mínimo usando este shop es C+min f(i), con i=L...p.<br />
Para cada nivel me quedo con el shop que me genere menor costo. Se puede implementar usando un <a href="https://en.wikipedia.org/wiki/Range_minimum_query">RMQ</a> sobre los f(i) (existen otras soluciones).</div></div>Martín Villagrahttp://www.blogger.com/profile/04539435412394117022noreply@blogger.com10tag:blogger.com,1999:blog-5066062691948591225.post-60179461465978721252015-11-02T23:57:00.002-03:002015-11-03T18:10:03.183-03:00Solucionario TAP 2015Logramos que nuestra universidad fuera sede por primera vez! Muchas gracias a Exequiel Rivas por la organización.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-GyPy9w30orE/VjPu24V23BI/AAAAAAAABCs/USoFqIU6jRI/s1600/12105727_1014161708635339_452152940689633872_n.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="424" src="http://3.bp.blogspot.com/-GyPy9w30orE/VjPu24V23BI/AAAAAAAABCs/USoFqIU6jRI/s640/12105727_1014161708635339_452152940689633872_n.jpg" width="640" /></a></div>
<br />
<h2>
Problemset</h2>
<a href="http://torneoprogramacion.com.ar/wp-content/uploads/2015/09/pruebaTAP2015.pdf">http://torneoprogramacion.com.ar/wp-content/uploads/2015/09/pruebaTAP2015.pdf</a><br />
<br />
<h2>
Scoreboard Final</h2>
<a href="http://torneoprogramacion.com.ar/2015/09/27/resultados-tap-2015/">http://torneoprogramacion.com.ar/2015/09/27/resultados-tap-2015/</a><br />
<br />
<h2>
Juez Online</h2>
A: <a href="http://coj.uci.cu/24h/problem.xhtml?pid=3381">http://coj.uci.cu/24h/problem.xhtml?pid=3381</a><br />
B: <a href="http://coj.uci.cu/24h/problem.xhtml?pid=3382">http://coj.uci.cu/24h/problem.xhtml?pid=3382</a><br />
C: <a href="http://coj.uci.cu/24h/problem.xhtml?pid=3383">http://coj.uci.cu/24h/problem.xhtml?pid=3383</a><br />
D: <a href="http://coj.uci.cu/24h/problem.xhtml?pid=3384">http://coj.uci.cu/24h/problem.xhtml?pid=3384</a><br />
E: <a href="http://coj.uci.cu/24h/problem.xhtml?pid=3385">http://coj.uci.cu/24h/problem.xhtml?pid=3385</a><br />
F: <a href="http://coj.uci.cu/24h/problem.xhtml?pid=3386">http://coj.uci.cu/24h/problem.xhtml?pid=3386</a><br />
G: <a href="http://coj.uci.cu/24h/problem.xhtml?pid=3387">http://coj.uci.cu/24h/problem.xhtml?pid=3387</a><br />
H: <a href="http://coj.uci.cu/24h/problem.xhtml?pid=3388">http://coj.uci.cu/24h/problem.xhtml?pid=3388</a><br />
I: <a href="http://coj.uci.cu/24h/problem.xhtml?pid=3389">http://coj.uci.cu/24h/problem.xhtml?pid=3389</a><br />
J: <a href="http://coj.uci.cu/24h/problem.xhtml?pid=3390">http://coj.uci.cu/24h/problem.xhtml?pid=3390</a><br />
K: <a href="http://coj.uci.cu/24h/problem.xhtml?pid=3391">http://coj.uci.cu/24h/problem.xhtml?pid=3391</a>
<br />
<br />
<h2>
Soluciones</h2>
<br />
<h3>
Problema A – AM/FM</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Supongamos que tenemos el punto óptimo. El punto óptimo está en la intersección de áreas de algunas estaciones. Cualquier punto que tome que pertenezca a esa intersección va a ser igual de óptimo. Tenemos dos casos:<br />
<ul>
<li>Si la intersección es un círculo, entonces en el centro hay una estación por lo que puedo mover el punto en el centro de esa estación.</li>
<li>Si la intersección no es un círculo, entonces está formada por la intersección de dos o más círculos no concéntricos. Puedo mover el punto al punto en donde algún par de circunferencias de esta intersección se cruzan.</li>
</ul>
<div>
Hemos demostrado que solo basta con probar los centros de las estaciones O(N) y las intersecciones entre las circunferencias O(N^2) como posibles candidatos. Solo resta buscar con fuerza bruta O(CANDIDATOS*N) cual es el candidato con más estaciones.</div>
</div>
</div>
<br />
<br />
<h3>
Problema B – Buen kilo de pan Flauta</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Debemos hacer búsqueda binaria sobre la respuesta. Si fijamos una cantidad mínima de triángulos en cada división, podemos ir tomando de manera greedy en O(10^6) y ver si es posible o no lograr tal cantidad mínima.
</div>
</div>
<br />
<br />
<h3>
Problema C – CompuTenis recargado</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Solo tenemos que simular el partido.
</div>
</div>
<br />
<br />
<h3>
Problema D – Directo a la felicidad</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Para cada componente del grafo, o bien podemos poner estadios en todas las ciudades o bien agregar rutas y transformarlo en completo. Simplemente elegir la opción de menor coste y sumar el resultado de cada componente.
</div>
</div>
<br />
<br />
<h3>
Problema E – Empaquetamiento perfecto</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Próximamente! (en unos días, vayan pensando en estados y exponenciación de matrices)
</div>
</div>
<br />
<br />
<h3>
Problema F – Favoritismo inducido</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Planteamos una dinámica sobre el árbol. Dado un nodo v pintado de color c, cual es el índice de disturbios mínimo que se puede lograr mirando solo el subárbol de raíz en v? Esto es f(v, c). Para calcular f(v, c), simplemente para cada hijo de v, pruebo asignarle cada uno de los colores y obtengo el mínimo de su subárbol (acá uso f recursivamente) y me quedo con el mínimo.
</div>
</div>
<br />
<br />
<h3>
Problema G – Genética alienígena II</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
El proceso de convertir la cadena sería ir matcheando un sufijo de la primer cadena y un sufijo de la segunda. El sufijo de la primer cadena se va a ir invirtiendo ocasionalmente. Una primera observación es que si sabemos cual es el sufijo de la primer cadena, podemos recuperar el sufijo de la segunda porque ambas tienen la misma cantidad de carácteres.<br />
<br />
El truco está en notar que el sufijo de la primer cadena en cualquier estado es una substring de la cadena con la que empecé (que puede estar invertida). Por lo tanto para describir el estado solo basta con un (i, j, inv) donde inv es 1 o 0.<br />
Con esto puedo recuperar el sufijo de la segunda haciendo j-i+1. Ya pudiendo describir el estado eficientemente podemos probar todo haciendo una dinámica, que tome un estado y diga cual es la mínima cantidad de movimientos necesarios.
</div>
</div>
<br />
<br />
<h3>
Problema H – Haciendo la tarea</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
La cantidad de restas es pequeña. Podemos simular el proceso e imprimir cuantas restas hicimos.
</div>
</div>
<br />
<br />
<h3>
Problema I – Invasión extraterrestre</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Como N<=1000 podemos agregar todos los sufijos de ambas cadenas a una lista. Imaginemos primero que eso de que cambian de frecuencia no pasa, es decir sólo tenemos que matchear. Tenemos todos los sufijos y los ordenamos. Para cada sufijo i de una palabra, el siguiente sufijo (i+1) va a ser con el que más caracteres tenga en común al comienzo (no existe otro sufijo que tenga más carácteres al comienzo en común con i que i+1). Si el siguiente sufijo es de la otra palabra, los caracteres que tengan en común al comienzo determinan una subcadena en común entre ambas cadenas. Prestemos atención, para cada posición de la primer cadena (en realidad para cada sufijo) estamos encontrando la subcadena con más caracteres en común. Osea que mirando todas las posiciones (sufijos) y sacando un máximo ya tengo la respuesta.
<br />
<br />
Por último, para lidiar con los cambios de frecuencias hay que ‘normalizar’ los sufijos. Antes de agregar el sufijo a la lista lo transformo. Voy de izquierda a derecha. Si ese caracter no apareció antes la transformo la menor letra que no haya sido usada. Si el carácter ya apareció, la transformo a la letra que había usado antes.<br />
Ej:<br />
zzzybbx -> aaabccd<br />
azmmd -> abccd<br />
Luego aplico el algoritmo ya explicado. Se provee una implementación muy clara realizada por Emilio Lopéz <a href="http://sprunge.us/SZIW?c++">http://sprunge.us/SZIW?c++</a>
</div>
</div>
<br />
<br />
<h3>
Problema J – Jugando con Piedras II</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Lo esencial es resolver el problema primero para 1, 2 y 3 pilas, luego la estrategia general se puede deducir viendo esos tres casos. Sea E la estrategia de jugar inverso a la última jugada de tu oponente. Es decir, sacar N piedras de la pila que tu rival saco 1, sacar N-1 de la que tu rival saco 2, etc. Si el segundo jugador puede ganar siguiendo la estrategia E - es decir luego de k turnos de sacar N+1 (entre ambos) el primero no puede jugar – usa esa estrategia. Si no puede, es decir el primero tiene una jugada ganadora JG que impide al 2do seguir con la estrategia E, hagamos que el primero empieze con JG y siga la estrategia E con las jugadas del segundo. Es claro que llegamos a la situación donde el 2do no podía jugar y en este caso el primer jugador tiene asegurada la victoria.
</div>
</div>
<br />
<br />
<h3>
Problema K – Kimetto, Kipsang y Kipchoge</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Tenemos que mantener un par de cosas. Primero, para cada posición i, cual es la siguiente posición j tal que S[i]=S[j], llamemosle next (next(i)=j). Podemos usar varios sets para hacer esto. Lo mismo para la posición anterior, ant(j)=i.
<br />
Ahora dada una query E k podemos reducir el problema a buscar en el rango [0, k] cual es el máximo ant. Si mantenemos los valores de ant en un arreglo, sacar el máximo en un rango se puede hacer eficientemente con un segment tree!
<br />
Sólo resta ver como actualizar los next y los ant en cada query.
</div>
</div>
<br />
<br />Martín Villagrahttp://www.blogger.com/profile/04539435412394117022noreply@blogger.com11tag:blogger.com,1999:blog-5066062691948591225.post-11293522931230029712015-10-26T20:00:00.000-03:002015-10-30T02:42:50.516-03:00Tres problemas de regionales<br />
Explicaremos soluciones a algunos problemas de regionales latinoamericanos que no pudimos resolver durante competencia cuando simulamos el año pasado.<br />
<br />
<h3>
<a href="https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=195&problem=1154" target="_blank"><br class="Apple-interchange-newline" />Long Night of Museums (Latin America 2008)</a></h3>
<a href="https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=195&problem=1154">https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=195&problem=1154</a><br />
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
En este problema solo hay que calcular para cada conjunto de museos, cual es el tiempo mínimo en recorrerlos. Esto se resuelve fácilmente haciendo <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem" target="_blank">la clásica dinámica del TSP</a>.<br />
Luego me quedo con el conjunto de mayor tamaño que tarde como mucho 7 horas (420 minutos) en recorrerse.<br />
</div></div>
<br />
<br />
<br />
<h3>
<a href="https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3306" target="_blank">Shrinking Polygons (Latin America 2004)</a> </h3>
<div>
<a href="https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3306">https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3306</a></div>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Es claro que el poligono regular divide a la circunferencia en arcos iguales.<br />
Por lo tanto la longitud de los arcos a probar tiene que ser divisor del perimetro de la circunferencia.<br />
Para cada divisor d (que son menores a ~500) , vemos si podemos formar el polígono. Esto no es tan fácil pues no sabemos con que punto 'empezar'. Para resolver esta parte linearizamos el problema: Desplegamos los puntos en una recta, y creamos una copia justo al lado de esta. Esto es: si un punto i estaba en la posición Y[i], también va a haber un punto en la posición Y[i] + C, donde C es el perimetro de la circunferencia.<br />
Ahora observemos que si hay un punto i / Y[i] < C tal que si haciendo saltitos de longitud d solo pasamos por lugares que tienen puntos, entonces ya tenemos nuestro poligono!<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-szI8F3FQc6c/Vi8ClJvq62I/AAAAAAAAA_Y/Zj_-3NE5QQI/s1600/polygon.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="128" src="http://2.bp.blogspot.com/-szI8F3FQc6c/Vi8ClJvq62I/AAAAAAAAA_Y/Zj_-3NE5QQI/s320/polygon.png" width="320" /></a></div>
Con esta idea podemos diseñar una dinámica, que diga dado un punto i, si haciendo estos saltitos paso solo por lugares que tienen puntos.<br />
dp[i] = true si Y[i]+d>2*C (nos salimos del arreglo)<br />
dp[i] = false si no hay punto en la posicion Y[i]+d<br />
dp[i] = dp[j] si hay un punto j en la posición Y[i]+d<br />
<br />
Solo tenemos que chequear si existe un i / Y[i]<C y dp[i]=true. Si se cumple esto se puede formar el poligono con arcos de longitud d y la respuesta sería: N - C/d.<br />
(hay que buscar el menor d que lo cumpla)<br />
</div></div>
<div>
<br /></div>
<div>
<br /></div>
<h3>
<a href="https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1470" target="_blank"><span style="font-size: 18.72px;">Mission Impossible (Latin America 2005)</span></a></h3>
<b><a href="https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1470"><span style="font-family: inherit;">https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1470</span></a></b><br />
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<div>
<span style="font-family: inherit;">Este problema fue lejos el que más nos costó. Estuvimos literalmente meses y rescribimos la solución desde cero varias veces (principalmente debido a bugs en nuestras librerías de geometría).</span><br />
<br />
Tenemos dos partes.<br />
La primer parte es para cada informante calcular su `insider-coefficient`. Lo calculamos sin nada raro, sacando el minimo entre las distancias a cada lado del poligono.<br />
Ahora nos queda ver dado un informante saber si es accesible o no. Podemos descartar antes que nada los que se encuentren directamente adentro de un radar. Pero falta ver como detectar los que se encuentran encerrados por radares.<br />
Está es la parte difícil. Tenemos que crearnos un grafo no dirigido con los radares. Dos radares estarán conectados sí y solo sí la intersección de sus areas es no nula (no puedo pasar entre de ellos). Ahora reducimos el problema a decir si un informate está dentro de un ciclo de este grafo o no (si está adentro está encerrado).<br />
Podemos hacer una dfs, y cada vez que nos encontramos con una back edge, checkear si el informante está en el ciclo determinado por esa back edge.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-cGpBS_WJnHE/Vi8N1fqnNTI/AAAAAAAAA_o/mGJhmsZcGVQ/s1600/Untitled.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="263" src="http://2.bp.blogspot.com/-cGpBS_WJnHE/Vi8N1fqnNTI/AAAAAAAAA_o/mGJhmsZcGVQ/s320/Untitled.png" width="320" /></a></div>
<br />
Si bien no estamos chequeando todos los ciclos del grafo, hay que observar que si tomamos la unión de las área de los ciclos detectados, cualquier ciclo (incluso los no detectados) van a estar contenidos en esta área.</div>
</div></div>Martín Villagrahttp://www.blogger.com/profile/04539435412394117022noreply@blogger.com0tag:blogger.com,1999:blog-5066062691948591225.post-81933277983113031592015-10-15T08:15:00.000-03:002015-11-01T21:04:27.056-03:0011° competencia de Red de Programación Competitiva (2015)<br />
Esta competencia nos resultó entretenida. Los problemas eran muy lindos!<br />
<br />
<div style="text-align: center;">
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://4.bp.blogspot.com/-p56g3hMVlD8/Vi75JFpxlFI/AAAAAAAAA_I/_-bA7BV_yhE/s1600/12112285_1672259366353246_6995431195466997908_n.jpg" style="margin-left: auto; margin-right: auto;"><img border="0" height="281" src="http://4.bp.blogspot.com/-p56g3hMVlD8/Vi75JFpxlFI/AAAAAAAAA_I/_-bA7BV_yhE/s640/12112285_1672259366353246_6995431195466997908_n.jpg" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><i><span style="font-size: x-small;">scoreboard en la posmaratón de la competencia</span></i></td></tr>
</tbody></table>
</div>
<br />
<br />
<h2>
Link a los problemas</h2>
<a href="https://drive.google.com/file/d/0ByI9GfoY63_aVlJmbmNPdGJHYWM/view?usp=sharing">https://drive.google.com/file/d/0ByI9GfoY63_aVlJmbmNPdGJHYWM/view?usp=sharing</a><br />
<br />
<h2>
Juez modo posmaratón</h2>
<a href="https://acm.javeriana.edu.co/maratones/2015/11/">https://acm.javeriana.edu.co/maratones/2015/11/</a><br />
<br />
<h2>
Soluciones</h2>
<br />
<h3>
A: Alcoholic Pilots</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Este era el trivial de la competencia.
</div>
</div>
<br />
<br />
<h3>
B: Bargaining</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Podemos reducir este problema a que comenzamos con un rectángulo de E x D, nuestro polígono inicial. Cada ecuación nos define una recta. Para cada una de estas rectas debemos 'cortar' el polígono y quedarnos con la parte deseada. Se puede cortar un poligono con una recta en O(n), solo basta ver de que lado quedan los extremos de las aristas. (Si quedan en lados diferentes hay que calcular la intersección entre la arista y la recta). Finalmente imprimir el área del poligono final.
</div>
</div>
<br />
<br />
<h3>
C: Cuban Challenge</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Acá hay un grafo bipartito! Si pintamos las casillas como un tablero de ajedrez, una pieza de domino SIEMPRE 'conecta' dos casillas de diferente color. En el grafo tenemos por un lado las casillas blances y del otro las negras. Unimos dos casillas si se puede poner una pieza de domino que las cubra. El problema se reduce a calcular el matching maximo sobre este grafo (pues queremos cubrir la mayor cantidad de casillas)
</div>
</div>
<br />
<br />
<h3>
D: Drinking Game</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Primero que nada siempre vamos a poder poner un 1 cada número, total gcd(x, 1)=1 para todo x>0. En base a esto la observación más importante es que como los números son menores a 20, nunca voy a poner un número mayor o igual a 39, pues en vez de sumarle 19, le resto 19 y tengo un 1 que me hace menos problema. En base a esto podemos hacer una DP que pruebe todo. Para ver si puedo poner un número, en vez de llevar los números que ya use y ver si es coprimo con todos ellos, me conviene hacer otra cosa. Un número es coprimo con otro si sus factorizaciones no tienen ninguno primo en común. Usando esto puedo llevar los primos ya usados y ver para cada número entre 1 y 39 si lo puedo usar o no. Si lo puedo usar puedo agregar los nuevos primos usados por este número a los que ya tenía y llamar a la DP en la siguiente posición con estos nuevos .<br />
<br />
<br />
Como los primos que pueden ser usados son los <=39, (los cuales son muy pocos), puedo guardar los usados con una máscara de bits. Nuestra dp quedaría dp[posicion][primosusados].
</div>
</div>
<br />
<br />
<h3>
E: Exquisite Strings</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
El problema consistía en dada una string S contar la cantidad de pares de subcadenas S[i..j] S[a..b], tales que las primeras k letras de ambas sean iguales (módulo 1000000007). Si clasificábamos los sufijos suf[i]=S[i..n-1] de más de k caracteres según su prefijo (lo podíamos hacer con hashing o con SA+LCP). Examinando un grupito de estos cualquier subcadena que tenga como prefijo los k primeros caracteres de estos sufijos del grupo se puede emparejar con cualquier otra de este grupo (y sólo con esas). Así que sí {i1, i2, ... im} formaban partes de este grupo calculabamos la sumatoria de sum=|S|-ik-k+1 (k=1..m). Luego total+=(sum*(sum-1)/2). <br />
<br />
(Para hacer /2 módulo 1000000007 podemos multiplicar por 500000004).
</div>
</div>
<br />
<br />
<h3>
F: File Transmission</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Necesitamso tener en claro componentes biconexas.<br />
Veamos que si dados dos nodos existen dos caminos dijuntos que los conectan entonces no tengo que agregar nada (pues mando 50gb por uno y 50gb por el otro). Esto es lo mismo que decir que si ambos nodos esten en una componente biconexa. Si en cambio nos dan dos nodos en distintas componentes biconexas la cosa cambia, tendriamos que 'salir' de la componente, pasar por algunos bridges (y otras componentes biconexas) y por último 'entrar' en la componente biconexa. Condensemos todos los nodos de una sola componente en uno solo (usando union-find por ejemplo). El grafo resultante es un árbol. Las aristas que quedan son los puentes. Ahora para responder la query tenemos que calcular la distancia entre las componentes a los cuales esos nodos pertenecen y multiplicarla por 50. Esto se puede hacer usando LCA.
</div>
</div>
<br />
<br />
<h3>
G: Greedy Artisan</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Este problema sale Greedy. Primero ordenamos las matryoshkas por las condiciones que nos dice. Luego de elegir la matryoshka más pesada, la elección de las otras a comprar es greedy.
</div>
</div>
<br />
<br />
<h3>
H: Heavy Luggage</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Esto sale con matrices. Imaginemos que nos dan un estado x en un vector de tamaño n (nos indica cuanto peso tiene cada persona).<br />
Entonces se puede calcular fácilmente a partir del grafo el estado siguiente x' (hacer cuentitas). Más aún podemos construir una matriz P / Px=x'<br />
Si P no es inversible quiere decir que hay multiples soluciones (imprimir lost luggage!)<br />
Supongamos que P es inversible. Entonces (P^-1) x' = x<br />
Volviendo al problema, si nos dan el estado final f. Podemos hacer ((P^-1)^k) f y obtenemos el estado inicial, la respuesta al problema.<br />
<br />
Queda para analizar como resolver los problemas de precision dado que nos dan un número con 200 dígitos.
</div>
</div>
<br />
<br />
<h3>
I: Incredulous Ed </h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Dado los números pequeños, podemos hacer simplemente fuerza bruta y probar todas las secuencias posibles. Una forma es hacer una función f(posicion, usados) donde usados es una mascara de bits que indica que números (del 1 al 9) fueron usados por la secuencia y posicion es donde hay que poner el siguiente número. Agregamos el número y llamamos recursivamente en posicion+1 (solo si agregarlo genera una secuencia valida lo cual es chequeable con usados)
</div>
</div>
<br />
<br />
<h3>
J: Jair vs Chadan</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
El problema de este es que era difícil de entender. La idea central es esta: si yo tengo un juego en donde se va formando un número desde los digitos más significativas hasta los menos. En cada paso yo tengo un conjunto de digitos para elegir. Si yo quiero máximizar el número que se forme, que es lo que me conviene hacer? Es obvio que tengo que elegir el digito más grande, SIN importar lo que pase después. El problema se resuelve basicamente simulando el juego y usando una estrategia así para cada jugador.
</div>
</div>
<br />
<br />
<h3>
K: Keypad Problem</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Este problema es una generalización complicada del algoritmo de Euclides extendido. El número se va a poder formar si es múltiplo del máximo común divisor del conjunto de todos los números. https://es.wikipedia.org/wiki/Algoritmo_de_Euclides. Para no tener problemas de overflow, nosotros aplicamos dos heurísticas. Primero disminuir el número objetivo al mínimo posible, asignando greedymente algunas combinaciones. Y luego, se puede demostrar que usando a lo sumo log (20000)=15 números, alcanza para generar el objetivo. Usando un método divide and conquer, podés lograr multiplicar a lo sumo 4 veces (log 15), logrando no tener problemas de overflow. También es posible lograr una solución “menos bonita” usando big integer.</div>
</div>
<br />
<br />Martín Villagrahttp://www.blogger.com/profile/04539435412394117022noreply@blogger.com6tag:blogger.com,1999:blog-5066062691948591225.post-8936921169251063072014-12-09T11:46:00.000-03:002015-10-30T02:40:31.774-03:0010ma competencia de Red de Programación Competitiva (2014)<br /><br />Muy linda competencia. Este es el scordeboard a 4 horas de competencia:<br /><br /><div style="text-align: center;">
<a href="http://2.bp.blogspot.com/-FkfaX6rZf9g/VIcLLuP56oI/AAAAAAAAAqE/2D2A4DKDftE/s1600/10389697_1538324083080109_7170157832340825618_n.jpg"><img border="0" src="http://2.bp.blogspot.com/-FkfaX6rZf9g/VIcLLuP56oI/AAAAAAAAAqE/2D2A4DKDftE/s1600/10389697_1538324083080109_7170157832340825618_n.jpg" /></a></div>
<br />(el F también nos salió)<br /><br /><h2>
<a href="http://acm.javeriana.edu.co/maratones/forum/viewforum.php?f=785&sid=13246e8bc7183a90ca8e9422044417d9" target="_blank">Links a los enunciados</a></h2>
<a href="http://acm.javeriana.edu.co/maratones/forum/viewforum.php?f=785&sid=13246e8bc7183a90ca8e9422044417d9">http://acm.javeriana.edu.co/maratones/forum/viewforum.php?f=785&sid=13246e8bc7183a90ca8e9422044417d9</a><div>
<br /></div>
<br /><h2>
Soluciones</h2>
<div>
<br /></div>
<h3>A: Arrangement of Contest</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Solamente nos importa la primer letra de cada problema, usamos un arreglo para saber si tal letra está como primer carácter en algún problema.
</div></div><br /><br />
<h3> B: Ballot Analyzing Device</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Simplemente hacer las cuentas. La función round de C++ puede ser útil para el redondeo.
</div></div><br /><br />
<h3> C: Trener</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Usando la misma técnica de A, para cada letra guardo cuantas apariciones tiene. En base a esto generar la respuesta.
</div></div><br /><br />
<h3>D: Dwarf Tower</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Nos armamos una especie de grafo, los nodos son los items y hay una arista (a, c) de peso b si puedo formar c usando los items a y b. Haciendo Dijstra (modificado para que funcione con estas aristas raras), obtenemos la respuesta.
</div></div><br /><br />
<h3>E: Energy Tycoon</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Para este problema alcanza ver tres detalles:<br /><ul>
<li>Solo conviene quitar plantas si tenemos una que ocupa 2 espacios y podemos colocar una de 1 espacio.</li>
<li>Al no tener costo remover una planta, siempre que haya espacio conviene colocar, de última se removerá luego.</li>
<li>Solo removemos cuando no hay más espacio, sino es innecesario.</li>
</ul>
Luego simulamos esta estrategia.
</div></div><br /><br />
<h3>F: Flight Boarding Optimization</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Fue un tanto complicado. Primero calculabamos mol[i][j], la cantidad de personas en la fila i que molestan a la j (i<j). Con eso haciamos molr[i][j], la cantidad de personas de la fila j que son molestadas por las personas en las filas i, i+1, …, j.<br /><br />Una vez obtenida esta información, hicimos una DP (programación dinámica), dp[i][j][kr]. La idea sería la siguiente: suponiendo que yo estoy construyendo las zonas de izquierda a derecha, estoy parado en la fila j, la primer fila de la zona actual es i y me quedan kr zonas por crear. Podría elegir empezar una nueva zona conteniendo a j (si me quedan zonas disponibles) o agregar j a la zona actual (en cuyo caso aumenta la dificultad en exactamente molr[i][j]). Así, el óptimo para el estado i,j,kr actual es el mínimo entre estas dos opciones.
</div></div><br /><br />
<h3>G: Garage</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
<div>
<ul>
<li>Primero se ve fácil que las podemos trabajar independientemente para el sentido horizontal como vertical.</li>
<li>Luego se ve claramente (y se puede demostrar) que a partir de W = w no podemos impedir colocar 1 bloque, a partir de W = 3w no podemos impedir colocar 2 bloques, …., a partir de W = (2k+1)w no podemos impedir colocar k bloques.</li>
<li>La cuenta simple (W-w) / (2w) te devuelven los que entran horizontalmente y multiplicamos por los que entran verticalmente.</li>
</ul>
</div>
</div></div><br /><br />
<h3> H: Kusac</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Este problema es simple si lo pensamos recursivamente.
<div>
<ul>
<li>Primero dados n sausages y m personas ( f(n,m)), si n>= m, repartimos las sausages, hasta que no se pueda, quedandonos f(n%m,m).</li>
<li>Si n < m, tenemos la obligación de hacer mínimo n cortes (1 x sausage), aprovechamos y cortamos cada una para darle la parte que le tocaría a cada persona (n/m), y nos quedan n pedazos más pequeños e iguales para darles a m-n personas. f(n,m-n)+n.</li>
<li>Si n = 0, no queda nada para repartir y cortamos la recursión.</li>
</ul>
</div>
</div></div><br /><br />
<h3> K: Lopov</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Este problema es greedy, simplemente ves ordenadamente desde la mochila de menor peso, cual joya te conviene meter. Para calcular eso en O (lg n) se puede usar por ejemplo un set.
</div></div><br /><br />
<h3>L. Organizator</h3>
<div class="divspoiler"><a class="solbutton" href="javascript:void(0);" onclick="if (this.parentNode.nextSibling.childNodes[0].style.display != '') { this.parentNode.nextSibling.childNodes[0].style.display = ''; } else { this.parentNode.nextSibling.childNodes[0].style.display = 'none';}">Mostrar Solución</a></div><div><div class="spoiler" style="display: none;">
Calculando en un arreglo todos los valores se puede hacer. Simplemente hay que recorrer todos los divisores de cada número que te dan de forma eficiente (usando una criba).
</div></div>Martín Villagrahttp://www.blogger.com/profile/04539435412394117022noreply@blogger.com0tag:blogger.com,1999:blog-5066062691948591225.post-28412382954979334902014-12-04T11:42:00.000-03:002014-12-09T19:00:56.710-03:00El difícil camino de la ICPC en nuestra zona<div style="background: rgb(255, 255, 255); border: 0px; color: #333333; font-family: 'Droid Sans', Georgia, 'Times New Roman', Times, serif; font-size: 16px; line-height: 24px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;">
<div style="display: none;">
<img src="https://lh5.googleusercontent.com/-pq-PqVQMUt0/VIcMiKJ_n5I/AAAAAAAAAqU/E8uqXAiOl_0/w465-h549-no/LatinAmerica.gif" /></div>
La clasificación del equipo fue un hecho histórico a nivel provincial (somos el primer equipo de Santa Fe en clasificar). Hemos encarado el proyecto con mucha pasión ya que hacemos lo que realmente nos gusta: divertirnos trabajando en equipo para resolver problemas.</div>
<div style="background: rgb(255, 255, 255); border: 0px; color: #333333; font-family: 'Droid Sans', Georgia, 'Times New Roman', Times, serif; font-size: 16px; line-height: 24px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;">
Ser los primeros conlleva una gran responsabilidad: la tarea de hacer camino. Nuestro objetivo es sentar precedentes a nivel local. No es lo mismo proponerse participar desde aquí, en nuestra localidad que en otras donde ya hubieron personas que transitaron los senderos que nosotros tuvimos que hacer durante este año.</div>
<div style="background: rgb(255, 255, 255); border: 0px; color: #333333; font-family: 'Droid Sans', Georgia, 'Times New Roman', Times, serif; font-size: 16px; line-height: 24px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;">
Afortunadamente, pudimos asistir al Training Camp organizado en la UBA que nos fue de increíble a ayuda para entrenarnos. Ahí conocimos mucha gente muy bien dispuesta a darnos una mano. Todo esto no habría sido posible sin la ayuda de personas a nivel nacional (de Buenos Aires, Córdoba, Bahía Blanca, entre otros) y de una comunidad internacional regional creciente (Perú, Brasil, etc), así como de comunidades de países que ya tienen larga trayectoria y equipos muy bien formados para estas competencias (Estados Unidos, Rusia, China). Romper con las barreras geográfica no nos fue fácil. Tuvimos que hacer sacrificios para poder dedicarnos a este proyecto.</div>
<div style="background: rgb(255, 255, 255); border: 0px; color: #333333; font-family: 'Droid Sans', Georgia, 'Times New Roman', Times, serif; font-size: 16px; line-height: 24px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;">
Nos gustaría mucho incentivar a nivel local las competencias y que las personas que vengan en un futuro de nuestra facultad (¡y todo Santa Fe!) cuenten con un antecedente y mayores facilidades, como material teórico y práctico, y que ellos también trabajen en pos de las nuevas generaciones, incentivando la participación en la región.</div>
<div style="background: rgb(255, 255, 255); border: 0px; color: #333333; font-family: 'Droid Sans', Georgia, 'Times New Roman', Times, serif; font-size: 16px; line-height: 24px; margin-bottom: 24px; padding: 0px; vertical-align: baseline;">
Además de la dificultad inherente de la competencia y el entrenamiento (que lo afrontamos con mucho gusto) tuvimos que sortear varias dificultades, sobre todo infraestructurales, debido a que no constábamos con antecedentes de una participación importante y no había mucha difusión de las competencias. En su mayoría los gastos tuvimos que cubrirlos nosotros (excepto por algunos pasajes en colectivos a BsAs que fueron cubiertos por la facultad). Pero a medida que avanzamos y vamos más lejos los gastos se vuelven realmente imposible de financiarlos por nuestra cuenta. Es por eso que creemos que es importante sentar un fuerte precedente para que instituciones públicas y privadas interesadas y comprometidas con la educación, formación y difusión de la programación y algoritmia (y en especial de estas competencias) puedan prestar un apoyo económico, de modo de formar una infraestructura que incentive a futuros competidores, haciéndosele más llevadero el camino y pudiéndose ocupar plenamente del entrenamiento para la competencia en sí.</div>
Martín Villagrahttp://www.blogger.com/profile/04539435412394117022noreply@blogger.com0tag:blogger.com,1999:blog-5066062691948591225.post-64375772862552261942014-12-03T18:58:00.000-03:002019-10-31T03:39:12.966-03:00Bot para el Laser Age <div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-7TI225i8uiw/VIdsoldqntI/AAAAAAAAAuY/zDdkTL3i5_c/s1600/laserage_gold1.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://1.bp.blogspot.com/-7TI225i8uiw/VIdsoldqntI/AAAAAAAAAuY/zDdkTL3i5_c/s1600/laserage_gold1.jpg" height="253" width="320"></a></div>
Hace unos días me puse con este jueguito que tenía de cuando era chico. Es de una página que ya cuando lo jugaba no existía más. Estuve meses y meses jugando y nunca logré ganarlo. Ahora que soy más grande y después de intentar por varios días, fracasé rotundamente de nuevo.<br />
<br />
Como estaba decidido a ganarlo de cualquier forma posible, decidí hacer un programa que lo gane por mí. Aprovechando que con la API de Windows se pueden leer pixeles de la pantalla, cambiar la posición del mouse y esas cosas no fue tan díficil.<br />
<br />
<br />
<br />
<br />
El bot básicamente busca un lugar en donde no haya tiros y se mueve a esa posición. Eso cada 10 milisegundos. Acá dejo el video de cuando lo gané por primera vez (solamente los últimos niveles). Los tiros se detectan según el color, por eso cuando aparece el bicho final con esos tiros blancos que no habían aparecido antes tengo que pararlo y agregar el nuevo color a la detección de tiros.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='560' height='315' src='https://www.youtube.com/embed/UdI1vJwmLKI?feature=player_embedded' frameborder='0'></iframe></div>
<br />
Es un juegazo aunque no muy conocido. Se puede descargar en:<br />
<a href="http://www.acid-play.com/download/laserage-gold">http://www.acid-play.com/download/laserage-gold</a><br />
<br />
El bot lo pueden descargar aquí:<br />
<a href="https://github.com/vmartinv/laserage-bot">https://github.com/vmartinv/laserage-bot</a><br />
<br />
<br />
<br />Martín Villagrahttp://www.blogger.com/profile/04539435412394117022noreply@blogger.com0tag:blogger.com,1999:blog-5066062691948591225.post-74789043673762608082014-11-30T17:06:00.000-03:002019-11-07T23:40:28.404-03:00Frutcherman's Algorithm<div class="separator" display="none" style="clear: both; display: none; text-align: center;">
<img border="0" src="https://4.bp.blogspot.com/-T8dz7bxDjIM/VIdXgGo0q6I/AAAAAAAAAuI/44E2G1qbF4E/s1600/Screenshot%2B-%2B12092014%2B-%2B05%3A09%3A48%2BPM.png" height="320" width="320">
</div>
Este es un algoritmo que hice para una materia de mi facultad. Se intenta dibujar un grafo lo más 'lindo' posible, es decir, minimizando la cantidad de aristas que se cortan.<br />
Funciona bajo un sistema de fuerzas. Los nodos se repelen naturalmente, pero las aristas añaden fuerza de atracción. En teoría cuando se simula este sistema el grafo tiende a un estado más ordenado, que es lo que estamos buscando.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='560' height='315' src='https://www.youtube.com/embed/qzOLzU77Qt0?feature=player_embedded' frameborder='0'></iframe></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: left;">
El programa está hecho enteramente en Python, usamos pygame para mostrar en pantalla y interactuar con el mouse/teclado. Pueden ver el código acá:</div>
<span style="color: #0000ee; text-decoration: underline;"><a href="https://github.com/vmartinv/interactive-frutchermans">https://github.com/vmartinv/interactive-frutchermans</a></span><br />
<div>
<span style="color: #0000ee;"><u><br /></u></span>
<br />
<div class="separator" style="clear: both; text-align: left;">
Para hacerlo nos basamos en el paper original. Pueden aprender más sobre este tipo de algoritmos acá:</div>
<div class="separator" style="clear: both; text-align: left;">
<a href="http://en.wikipedia.org/wiki/Force-directed_graph_drawing">http://en.wikipedia.org/wiki/Force-directed_graph_drawing</a></div>
<br />
Hicimos una sola modificación al estado de equilibrio de forma más rápida. A medida que el sistema se vuelve más estable, las fuerzas se reducen y se tarda más en llegar al estado de equilibrio. Por eso hicimos que las fuerzas sean modificadas por un valor creciente en el tiempo, al cual llamamos temperatura. Y por qué no empezamos con mucha temperatura directamente? En este caso el sistema se vuelve tan inestable que nunca se alcanzaría el equilibrio, en la práctica el grafo parece transformarse como en un "gas".<br />
<br /></div>
Martín Villagrahttp://www.blogger.com/profile/04539435412394117022noreply@blogger.com0