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.
