tag:blogger.com,1999:blog-8863980713018105303.post6531226098714410782..comments2016-08-17T09:14:47.256-07:00Comments on Kurniady's Blog: Day 5 (April 9th) - ACM ICPC World Finals, Awards, and CelebrationAndrian Kurniadynoreply@blogger.comBlogger10125tag:blogger.com,1999:blog-8863980713018105303.post-27263175864727150672008-07-07T04:03:41.000-07:002008-07-07T04:03:41.000-07:00[...] Day 5 (April 9th) - ACM ICPC World Finals, A...[...] Day 5 (April 9th) - ACM ICPC World Finals, Awards, and Celebration [...]Andrian Kurniady’s Blog » ACM ICPC World Finals 2008 - Banff, Canadahttp://www.kurniady.net/2008/04/20/acm-icpc-world-finals-2008-banff-canada/noreply@blogger.comtag:blogger.com,1999:blog-8863980713018105303.post-49761624374469415562008-07-07T04:05:03.000-07:002008-07-07T04:05:03.000-07:00[...] Continue to Day 5 [...][...] Continue to Day 5 [...]Andrian Kurniady’s Blog » Day 4 (April 8th) - Opening Ceremony, Practice Session, Gondola Ride, and Downtown Banffhttp://www.kurniady.net/2008/06/29/day-4-april-8th-opening-ceremony-practice-session-gondola-ride-and-downtown-banff/noreply@blogger.comtag:blogger.com,1999:blog-8863980713018105303.post-66144295529098019132008-07-12T01:06:43.000-07:002008-07-12T01:06:43.000-07:00... "I want to read that DB2 book..."anw...... "I want to read that DB2 book..."<br>anw, too bad we didn't improve much... but congratz for reaching world final twice.. (uda kayak gitu, pulang gak bawa oleh2 lagi. ckckck.. mengecewakan)flanflygirlhttp://flanflygirl.wordpress.comnoreply@blogger.comtag:blogger.com,1999:blog-8863980713018105303.post-17854822335314540372008-08-28T10:56:52.000-07:002008-08-28T10:56:52.000-07:00Hello Andrian, can you tell me what's the dyna...Hello Andrian, can you tell me what's the dynamic programing state to solve problem F - Glenbow Museum?<br><br>I tried dp[i][j][k] = number of strings of length i having exactly j R's and finishing in O if K == 1, or finishing in R if K == 0.<br><br>This state gives me Wrong Answer, because it counts strings that start and end both with O, for example: ORRRRO.<br><br>Thanks for the help, and take care.Andrés Mejíahttp://blogaritmo.factorcomun.orgnoreply@blogger.comtag:blogger.com,1999:blog-8863980713018105303.post-52692600106146830952008-08-28T13:56:33.000-07:002008-08-28T13:56:33.000-07:00For the Glenbow Museum... I think the observations...For the Glenbow Museum... I think the observations is that you would want<br><br>Total number of R - total number of O = 4, and there are no two Os in a consecutive position (let's call this diff)<br><br>I think I used dpmat[length][diff][last], where last is either R or O. I found the same problem with you, but that can be solved with a bit of trick, which is to run the DP a few times :<br>- Assume the first character is O, then we do init with dpmat[1][-1][O] = 1, and we collect the answer in dpmat[length][4][R] (you cannot have two Os both in the beginning and the end right :D but OR is okay)<br>- Assume the first character is R, then we do init with dpmat[1][1][R] = 1, and we collect the answer in dpmat[length][4][R] AND dpmat[length][4][O] (RO and RR is fine, right? :D )<br><br>Well while looping for the DP you should consider NOT adding cases for OO, otherwise it would be fine. (I think you get this one already).<br><br>-KurniadyKurniadynoreply@blogger.comtag:blogger.com,1999:blog-8863980713018105303.post-7463369343434625782008-08-29T02:15:45.000-07:002008-08-29T02:15:45.000-07:00Hello Andrian,Thanks for your answer. I noticed th...Hello Andrian,<br><br>Thanks for your answer. I noticed there's an even easier way to find the final answer without running the DP twice.<br><br>Notice that for each valid string starting in R and ending in O, there's also a valid string starting in O and ending in R (For example, by reversing it).<br><br>If we use the state dpmat[length][diff][last] what I do is initialize dpmat[1][1][R] = 1 (Assume ALL strings start with R) and the final answer will be dpmat[length][4][R] + 2*dpmat[length][4][O]. That is, first count the strings that start and end in R. Then count the string that start in R and end in 0 and for each one of these strings count its paired "brother" string that starts in O and ends in R.<br><br>-Andrés MejíaAndrés Mejíahttp://blogaritmo.factorcomun.orgnoreply@blogger.comtag:blogger.com,1999:blog-8863980713018105303.post-68827172088816190332008-08-29T03:06:30.000-07:002008-08-29T03:06:30.000-07:00That's a good observation, I haven't notic...That's a good observation, I haven't noticed that back then. Well actually I was solving a harder problem like a few weeks before the world final, in which there's more types of characters (e.g. A B C D... up till n kinds) with my trick (multiple runs)... your way will reduce the number of runs into a half, which is quite nice.<br><br>Therefore on the world final I instantly remembered that trick and solved it without considering any optimizations (just copy pasted the code hehe...)<br><br>-KurniadyKurniadynoreply@blogger.comtag:blogger.com,1999:blog-8863980713018105303.post-71965279118613836132008-09-25T13:30:06.000-07:002008-09-25T13:30:06.000-07:00[...] - bookmarked by 5 members originally found b...[...] - bookmarked by 5 members originally found by sakkigi on 2008-09-12 Day 5 (April 9th) - ACM ICPC World Finals, Awards, and Celebration http://www.kurniady.net/2008/07/07/day-5-april-9th-acm-icpc-world-finals-awards-and-celebration/ - [...]Bookmarks about Acmhttp://www.remmrit.com/acmnoreply@blogger.comtag:blogger.com,1999:blog-8863980713018105303.post-31986729484712230902010-12-10T00:07:27.000-08:002010-12-10T00:07:27.000-08:00I need to contact site admin urgently. Can you und...I need to contact site admin urgently. Can you understand me?<br>Thank youLorencohofhttp://lorrycratmsn.comnoreply@blogger.comtag:blogger.com,1999:blog-8863980713018105303.post-60643276438368164172011-06-14T20:29:26.000-07:002011-06-14T20:29:26.000-07:00Problem F - Glenbow Museum (AC)Hi Adrian, i don...Problem F - Glenbow Museum (AC)<br>Hi Adrian, i don't understand exactly the solution of problem F, i understand that there are are 4 more Rs than Os but i don't understand if you have used permutations or combinations.<br>Sorry for my bad english<br>Simone SantarelliSimonenoreply@blogger.com