Hi Vikram,
Thanks a lot for your answer, that explains what is wrong!
Indeed, the transform() cannot be that "greedy" as I thought.
On Wednesday, 22 April 2020 03:17:24 UTC+8, Aditya Vikram Jain wrote:
>
> 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 <alexande...@gmail.com
> <javascript:>> 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 googl...@googlegroups.com <javascript:>.
>> 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 google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/78819e88-5572-4a20-a58b-707ed2c590dd%40googlegroups.com.
