tag:blogger.com,1999:blog-31847281.post7247316546997621864..comments2017-02-16T21:30:33.562-08:00Comments on Entropy always increases: Analysis of ICPC 2015 world finals problemsBruce Merrynoreply@blogger.comBlogger5125tag:blogger.com,1999:blog-31847281.post-69652259203867943252015-06-14T22:28:54.417-07:002015-06-14T22:28:54.417-07:00@alapan: http://icpc.baylor.edu/download/worldfina...@alapan: http://icpc.baylor.edu/download/worldfinals/problems/icpc2015.pdf<br /><br />@Caleb: I'm not aware of a sub-O(n) solution, but I suppose it is possible that one exists. It would need to exploit properties of the generating function in some way.Bruce Merryhttp://www.blogger.com/profile/02150601792587963530noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-4056834115850074252015-06-02T22:57:44.212-07:002015-06-02T22:57:44.212-07:00In the uva online judge site I believe they modifi...In the uva online judge site I believe they modified problem A a bit (in terms of time)<br />If you look at:<br />http://icpc.baylor.edu/worldfinals/problems/icpc2015.pdf<br />You can see the time limit is 5s and that there's only one test each time.<br />However in the UVA site:<br />https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=865&page=show_problem&problem=4782<br />(If you can't see the problem click on "PDF")<br />They not only reduced the time limit to 3s but "The input file contains several test cases"<br />I have coded a linear O(n) solution an got accepted in here:<br />https://icpc.kattis.com/problems<br />(since n < 10^6 it should pass the limits restriction, but it doesn't in uva probably for the several test cases.)<br />So I wanted to know if either there exists a faster solution (which the UVA team may have found) or they are not right by establishing those limits.<br />Since you didn't post a solution to that problem I'm asking in the comments. <br />Thanks in advance.Calebhttp://www.blogger.com/profile/13384009595445016210noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-9754268639391021542015-05-31T10:21:13.370-07:002015-05-31T10:21:13.370-07:00Bruce, could you please link to the questions (or ...Bruce, could you please link to the questions (or post them if appropriate)?alapanhttp://www.blogger.com/profile/05293481095724720060noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-9497012674799211312015-05-29T01:36:01.072-07:002015-05-29T01:36:01.072-07:00Problem I: Ship traffic
Before start the real imp...Problem I: Ship traffic<br /><br />Before start the real implementation, you can get the mirror images of the ships at one side of the ferry line to the other side and then transfer all the ships onto the first lane. So that, all the ships are in one lane and have the same direction. Mirroring and transferring require some basic calculations.<br />Osman Ayhttp://www.blogger.com/profile/01074697293141213868noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-35048301078158439912015-05-21T20:30:45.262-07:002015-05-21T20:30:45.262-07:00For problem H-Qanat the form of the cost function ...For problem H-Qanat the form of the cost function can be found:<br /><br />F=Sum_{i=0}^{n} h[i+1]^2 / 2 + h[i]*(p[i]-x[i])+(p[i]-x[i])^2/2 + h[i+1]*(x[i+1]-p[i])+(x[i+1]-p[i])^2/2<br /><br />where m=h/w is the slope of the hypotenuse, x[0]=0, x[n+1]=w, and x[i] for 1<=i<=n are the unknown optimal position of the shafts. Also h[i]=m*x[i] is the height of the ith shaft, and p[i] is a point lying between shafts i and i+1, which is at an equal distance from both shaft top points.<br />p[i]=(1-m)*x[i]/2 + (1+m)*x[i+1]/2<br /><br />Due to problems special conditions (h<w) it can be easily proven that x[i]<p[i]<x[i+1].<br /><br />A bit of algebraic work leads to a closed form dependence with x[i] only: <br /><br />F=Sum_{i=0}^{n} x[i+1]^2 * (m^2+m)/ 2 - x[i]^2 * m/2 + (1-m^2)*(x[i+1]-x[i])^2/4<br /><br />The Cost function F depends quadratically on x[i]. Then by simple partial derivation we find n linear and tri-diagonal equations to be satisfied by the positions x[i] (1<=i<=n).<br /><br />x[i+1]+x[i]*a+x[i-1]=0<br /><br />where a=2/(m^2-1)<br /><br />These linear equations can be solved in O(n) using gaussian elimination for tri-diagonal systems.Eduardo Quintana Mirandahttp://www.blogger.com/profile/16961868696600041478noreply@blogger.com