Overall idea seems fine, but transformation logic seems incomplete. You
haven't computed it recursively.
Submission returns "WA", and it doesn't provide the example on which it
failed. It's a known difficulty with CodeJam problems.
As you ignored recursion, finding bugs should be easy. Try (rand(-10^9,
10^9), rand(-10^9, 10^9)) and compare your answer against scored submission
results.
I used a similar logic, and scored full.
xy = abs(x) | abs(y)
MSB (a) = nextPowerOf2GreaterThenX/2
NextSB(a) = MSB (a ^ MSB(a))
1. drop MSB(xy) from abs(x),abs(y)
ie. if ((-x) & MSB(xy)) then result="W"+"b timesE"+result , -x = -x ^
MSB(xy)
2. b = MSB(xy)-NextSB(xy)-1
3. xy = abs(x) | abs(y)
Jump to 1
Regards, Atif Hussain
On Tue, 21 Apr, 2020, 10:52 PM Alexander Iskhakov, <
alexander.iskha...@gmail.com> wrote:
> 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 google-code+unsubscr...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/google-code/91b4b78d-40fb-4f82-9457-e0828ed905fb%40googlegroups.com
> <https://groups.google.com/d/msgid/google-code/91b4b78d-40fb-4f82-9457-e0828ed905fb%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 google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/CAHri%2BDwRo%2B3FacinQvOARnixRPr5Sm%2BsDem5efsfV5G2X7Peqw%40mail.gmail.com.
