Hi Alexander, I used similar approach and I think I found out why it is wrong, basically the solution just assumes that we need to convert the solution into two numbers which on xored give 0 and and the or operation between the two gives 2^(n-1), but this approach marks many possible answers impossible. For instance take the the example you posted which is (3,66) which your algo would have marked impossible
The sequence which lands us in this position is ENWWWEN. Upfront I don't think it is easy to transform 101 to (100000-11100+1) and there really are too many ways to transform. Thanks, Aditya On Wed, Apr 22, 2020 at 12:38 AM Alexander Iskhakov < [email protected]> wrote: > Quickly refactored the code: >> > > 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 >> 1L > result = result << 1L > } > result > } > > private def transform(a: Long) = { > val xNextPowerOf2 = nextPowerOf2GreaterThenX(a) > val x1 = xNextPowerOf2 - a > xNextPowerOf2 | x1 > } > > 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, xWasNegative, y, yWasNegative) = 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 xTransformed = transform(x) > if ((xTransformed & y) == 0L) { > xTransformed -> y > } else { > val yTransformed = transform(y) > if ((x & yTransformed) == 0L) { > x -> yTransformed > } else { > if ((xTransformed & yTransformed) == 0L) > xTransformed -> yTransformed > else > 0L -> 0L > } > } > } > > if (resultX == 0L && resultY == 0L || !isPowerOf2((resultX | resultY) + > 1L)) { > outputWriter.write(s"Case #$caseNum: IMPOSSIBLE\n") > } else { > val isXTransformed = resultX != x > val isYTransformed = resultY != y > > val result = StringBuilder.newBuilder > var (xP, yP) = resultX -> resultY > while (xP > 0L || yP > 0L) { > if ((xP & 1L) == 1L) { > if (xP == 1L || !isXTransformed) > result.append(if (xWasNegative) "W" else "E") > else > result.append(if (xWasNegative) "E" else "W") > } else if ((yP & 1L) == 1L) { > if (yP == 1L || !isYTransformed) > result.append(if (yWasNegative) "S" else "N") > else > result.append(if (yWasNegative) "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/a6af3268-eefa-46d4-b284-80fdb2acd666%40googlegroups.com > <https://groups.google.com/d/msgid/google-code/a6af3268-eefa-46d4-b284-80fdb2acd666%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- 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/CACxPqYfxkbCyR-E0JEpPFWznwuS_Nq%2BpwRMGbqYYSQwvBXmNtA%40mail.gmail.com.
