Submission returns "WA", and it doesn't provide the example on which it
failed. Cannot find a bug: tried lots of my examples, all work.
We immediately reduce the problem to considering both inputs as positive
(if negative we use Abs() and just remember which one or both during
reading, and then simply mirror output W <-> E and N <-> Sat the very end)
The idea is as following.
Let's consider (2, 5) in binary:
(2,5):
2 = 010 = _E_
5 = 101 = N_N
as soon as there is no 1 in the same position, the answer is NEN.
Let's now consider (6, 11):
6 = 0110
11 = 1011
unfortunately, there is an overlap in 2nd bit. So it cannot be translated
to output directly. But we can observe the following simple transformation:
6 = 8 - 2
11 = 16 - 5 = 16 - 4 - 1
where 8 and 16 is next Power of 2 for 6 and 11 correspondingly
with this transformation we se that all the numbers participated are
DIFFERENT powers of 2 placed in NON-INTERRUPTING sequence of our jumps: 1,
2, 4, 8, 16.
with this observation, we can transform our inputs into
8 | 2 = 01010
16 | 5 = 10101
this can be output directly as for simple (2, 5) case, with one small
change: we remember which coordinate was transformed (in this case both),
and we use opposite letter for all 1 except the leftmost:
8 | 2 = 01010 = _W_E_
16 | 5 = 10101 = S_S_N
so the output is SWSEN
To sum up this step, to determine which coordinate to transform we simply
do 4 consequent checks
1. x and y immediately nice
2. transformed(x) and y is nice
3. x and transformed(y) is nice
4. both transformed(x) and transformed(y) is nice
5. IMPOSSIBLE if none of checks match
some a and b "is nice" is when (a & b) == 0
one more check for IMPOSSIBLE before output is that (a&b) + 1 is the power
of 2 to avoid cases like 101 and 1000010, resulted after bitwise OR into
1000111 which falls under 1-4
Could somebody check if I am right in my solution?
code throws "WA" and I cannot find why
import java.io.{BufferedReader, BufferedWriter, InputStreamReader,
OutputStreamWriter}
import java.util.Scanner
object Solution {
private def isPowerOf2(x: Long) = (x & (x - 1L)) == 0L
/**
* returns next power of 2 greater then x.
* Example: nextPowerOf2GreaterThenX(11) = 16
* @param x
* @return
*/
private def nextPowerOf2GreaterThenX(x: Long): Long = {
var result = 1L
var arg = x
while (arg > 0L) {
arg = arg >> 1
result = result << 1
}
result
}
def main(args: Array[String]): Unit = {
val outputWriter = new BufferedWriter(new OutputStreamWriter(System.out))
val in = new Scanner(new BufferedReader(new InputStreamReader(System.in)))
val t = in.nextLine().toInt
for (caseNum <- 1 to t) {
val (x, inverseX, y, inverseY) = in.nextLine().split(' ').map(_.toLong)
match {
case Array(x, y) => (Math.abs(x), x < 0, Math.abs(y), y < 0)
}
val (resultX: Long, resultY: Long) =
if ((x & y) == 0L) {
x -> y
} else {
val xNextPowerOf2 = nextPowerOf2GreaterThenX(x)
val x1 = xNextPowerOf2 - x
val xRes = xNextPowerOf2 | x1
if ((xRes & y) == 0L) {
xRes -> y
} else {
val yNextPowerOf2 = nextPowerOf2GreaterThenX(y)
val y1 = yNextPowerOf2 - y
val yRes = yNextPowerOf2 | y1
if ((x & yRes) == 0L) {
x -> yRes
} else {
if ((xRes & yRes) == 0L)
xRes -> yRes
else
0L -> 0L
}
}
}
if (resultX == 0L && resultY == 0L || !isPowerOf2((resultX | resultY) +
1L)) {
outputWriter.write(s"Case #$caseNum: IMPOSSIBLE\n")
} else {
val isXnegFirst = resultX != x
val isYnegFirst = resultY != y
val result = StringBuilder.newBuilder
var (xP, yP) = resultX -> resultY
while (xP > 0L || yP > 0L) {
if ((xP & 1L) == 1L) {
if (xP == 1L || !isXnegFirst)
result.append(if (inverseX) "W" else "E")
else
result.append(if (inverseX) "E" else "W")
} else if ((yP & 1L) == 1L) {
if (yP == 1L || !isYnegFirst)
result.append(if (inverseY) "S" else "N")
else
result.append(if (inverseY) "N" else "S")
}
xP = xP >> 1L
yP = yP >> 1L
}
outputWriter.write(s"Case #$caseNum: ${result.mkString}\n")
}
}
outputWriter.close()
}
}
--
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 view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/91b4b78d-40fb-4f82-9457-e0828ed905fb%40googlegroups.com.
