Here's a partly documented solution to Problem B: http://ideone.com/CjB58d
Basically, if problem X is basic and has K problems (including itself) that depend on it, directly or indirectly, the K spots in which you do those problems are chosen uniformly at random from all subsets of size K. On Sat, Jun 25, 2016 at 6:54 AM, meir <[email protected]> wrote: > So It's been two weeks and still no analysis for GCJ round 3. > I thought I'd start a thread with the aim to cover all questions of round > 3. > > I will start with what I know, and hope someone will add an explanation to > the tougher problems. > > Problem A was fairly simple with nearly everyone in the competition > solving correctly. > The first observation I made is it that it is never in your interest to > take a non preferred problem, this immediately limits your possible actions > from 3 to 2. This however is not enough to make it brute forceable even for > small input. The next thing we realize is that if you can get maximal > points for a problem in hand you should do this and will never lose a > better opportunity. Also you should never finish with problems in hand so > if you have problems equal to the remaining days you must submit all of > them. This leads to simple rules and a stack simulation, no look ahead > beyond the number of days left required. A simpler to understand ,though > slightly harder to code, solution my wife suggested is to repeatedly > eliminate consecutive pairs of identical preferences for 10 points in any > order, and when you are done you have an alternating list of preferences > which in pairs are worth 5 points. > > Scala code for the stack based approach (single test): > > val n =in.readLine() > val s = n.length > var i = 0 > var stack = collection.mutable.Stack[Char]() > var sum = 0 > while (i< s) { > if (stack.isEmpty) { > stack.push(n.charAt(i)) > } else { > if (stack.size + i >= s || stack.top == n.charAt(i)) { > val submit = stack.pop() > if (n.charAt(i) == submit) sum+=10 else sum+=5 > } else { > stack.push(n.charAt(i)) > } > } > i += 1 > } > > sum.toString > > > Problem B, We got some big hints in the problem definition, we saw only > small which can submitted multiple times. This leads to an approach which > is only probably correct, we have seen this in past competition. Also we > see the accuracy requirement is reduced. So as the analysis stub suggests > we need to randomly sample uniformly over possible orders. I don't have the > details worked out. Would be glad if someone added them. > > Problem C small. We have no motion so we can easily look at this as a > fully connected graph with N nodes. We are not looking for a shortest path > we are looking for a path which minimizes the maximal hop. So we are > looking for the minimal distance which if we take all shorter hops the > source and destination are connected. We can sort the edges and then do a > union merge starting with shortest hop stopping when the the source and > destination become in the same component. complexity O(N^2*long(N)) > > val Array(n,s) =in.readLine().split(" ").map(_.toInt) > val asteroids = (1 to n).map(x => in.readLine().split(" > ").map(_.toDouble)) > > val distMat = (0 until n).map {i => > (0 until n).map{j => > val dx = asteroids(i)(0) - asteroids(j)(0) > val dy = asteroids(i)(1) - asteroids(j)(1) > val dz = asteroids(i)(2) - asteroids(j)(2) > > val dist=(dx*dx+dy*dy+dz*dz) > math.sqrt(dist) > }.toArray > }.toArray > > val pairs = (for (i <- 0 until n; > j <- 0 until i) yield > (i,j,distMat(i)(j))).sortBy(_._3) > > val union = (0 until n).toArray > > def fetch(a: Int): Int = { > if (union(a) == a) a else { > val res = fetch(union(a)) > union(a) = res > res > } > } > > def merge(a: Int,b: Int) = { > union(fetch(a)) = fetch(b) > } > > pairs.find{case (a,b,d) => > merge(a,b) > fetch(0) == fetch(1) > }.get._3.toString > > > Problem D Small. > It is possible to create a set of programs which can output any string > with at least one zero and must output at least one zero. > So All the program does is check if the Bad string is in the good list, if > it is it outputs "IMPOSSIBLE" and otherwise it outputs > the first program with L-1 "?" and the second program with "10" repeated > 50 times followed by "?1". > Totally ignoring the good list beyond impossibility check. We also add > need an extra handling for the case of length 1 strings to make sure both > programs are non empty. > > val Array(n,l) =in.readLine().split(" ").map(_.toInt) > val good = in.readLine().split(" ") > val bad = in.readLine() > if (good.contains(bad)) "IMPOSSIBLE" else { > if (l == 1) "? 0" else > > "?"*(l-1) + " " + ("10"*50+ "?" + "1") > } > > Would love to see people continue this with threads with the problems I > did not cover. (Would also not mind seeing official GCJ analysis for round > 3, hint, hint). > > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/40047bde-b916-4ffc-8107-81e1591354b9%40googlegroups.com > . > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAECKw-Mc4_AgKiGky1Ki-iLntsZizzrvNLXJveMWB%2BmCRrizpg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
