tag:blogger.com,1999:blog-2697059789481443605.post6177902987641939778..comments2023-01-24T06:36:23.012-03:00Comments on Diário de Aprendizado: Contest Bonilha - Editorial (English version)Unknownnoreply@blogger.comBlogger11125tag:blogger.com,1999:blog-2697059789481443605.post-3403991413029146672014-02-12T13:19:07.547-02:002014-02-12T13:19:07.547-02:00Yes, it is the TSP, and the expected complexity fo...Yes, it is the TSP, and the expected complexity for this problem is O(N^2*2^N) (N is actually 15, instead of 16, because the horse is just the start and end of the cycle).<br />Well, I don't know how available the algorithm is at google, because I learned this on a book (Competitive Programming). The idea is to use bitwise operations (heard about?) to transform the pawns you have captured in a integer state, and this state you put on your DP, reusing them later.<br />If you want I can send you my code, and maybe you can understand the idea, but first try studying bitwise operations, or more specifically, bitmask.Bonilhahttps://www.blogger.com/profile/17338867599883324906noreply@blogger.comtag:blogger.com,1999:blog-2697059789481443605.post-35828063149575301212014-02-12T04:57:58.366-02:002014-02-12T04:57:58.366-02:00You're welcome! I've never done a contest ...You're welcome! I've never done a contest yet, but I imagine that must be really hard!<br /><br />I want to ask you about the task Horse. That problem is a TSP (Travelling Salesman Problem) for what I see. I've looked up a little bit on the internet, but I haven't found anything to make it less than O(N!). I've found some places said that with DP you can reduced it to O(N^2*2^N), but there doesn't say how, and still O(16^2*2^16) is a very large number (16777216, aprox 7*10^7).<br />How did you solved that part? It is a TSP, isn't it? Or am I wrong?Anonymoushttps://www.blogger.com/profile/02733407751991099025noreply@blogger.comtag:blogger.com,1999:blog-2697059789481443605.post-72939435849248493372014-02-12T03:13:08.177-02:002014-02-12T03:13:08.177-02:00You are right, I checked and there are no cases wh...You are right, I checked and there are no cases where the answer is 0. If I remember, later I am going to send them an update. Thanks for the advice :)Bonilhahttps://www.blogger.com/profile/17338867599883324906noreply@blogger.comtag:blogger.com,1999:blog-2697059789481443605.post-4440579898018154952014-02-12T01:59:12.115-02:002014-02-12T01:59:12.115-02:00In the Apple task, I think you should add this tes...In the Apple task, I think you should add this test case: <br />5 5 3<br />1 5 1<br />5 1 2<br />5 5 3<br />1 1<br />Or something like that, because you aren't controling when Rafael can't get any apple (I tell you this, because my code gives -1 as answer to this test case, what is obviously wrong, but got AC)<br /><br />May be I'm getting some mistake, I don't konw...<br /><br />Ps: thank you for the contest and the translation :)Anonymoushttps://www.blogger.com/profile/02733407751991099025noreply@blogger.comtag:blogger.com,1999:blog-2697059789481443605.post-89963095174307635682014-02-06T20:41:40.198-02:002014-02-06T20:41:40.198-02:00Got it... (y)Got it... (y)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-2697059789481443605.post-68961292213052950772014-02-06T10:21:10.068-02:002014-02-06T10:21:10.068-02:00Here's what I did: https://github.com/crbonilh...Here's what I did: https://github.com/crbonilha/codes/blob/master/macas.cpp<br />If you have troubles, send me an e-mail and I will explain the code for you.Bonilhahttps://www.blogger.com/profile/17338867599883324906noreply@blogger.comtag:blogger.com,1999:blog-2697059789481443605.post-79920417888405513782014-02-06T10:19:43.998-02:002014-02-06T10:19:43.998-02:00:):)Bonilhahttps://www.blogger.com/profile/17338867599883324906noreply@blogger.comtag:blogger.com,1999:blog-2697059789481443605.post-28307787113287923692014-02-06T08:35:24.270-02:002014-02-06T08:35:24.270-02:00can you please provide a working code of Maçãs . N...can you please provide a working code of Maçãs . Not able to get it. thanks :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-2697059789481443605.post-84088951286233128852014-02-06T03:02:48.277-02:002014-02-06T03:02:48.277-02:00Thank you very much :)) Thank you very much :)) meisyalhttps://www.blogger.com/profile/04146834391166199382noreply@blogger.comtag:blogger.com,1999:blog-2697059789481443605.post-13589844297483426092014-02-06T00:13:56.478-02:002014-02-06T00:13:56.478-02:00No problems :)
Good luck!No problems :)<br />Good luck!Bonilhahttps://www.blogger.com/profile/17338867599883324906noreply@blogger.comtag:blogger.com,1999:blog-2697059789481443605.post-68802608736618757302014-02-06T00:06:46.994-02:002014-02-06T00:06:46.994-02:00I just wanted to say thanks for having translated ...I just wanted to say thanks for having translated it to english, it was really helpful to me to understand some tasks that I couldn't solved by my self :)Anonymousnoreply@blogger.com