Thanks Branyine,
your idea works!
I missed a simple trick of "extending" the base of binary system with -1 :)
With this and continuation the process until both numbers doesn't have both
0s in the middle I managed to code and got all 3 PASS. Unfortunately in
"Practice mode", but still happy.
Haven't checked your code as the purpose of the exercise includes "code
myself", but appreciate anyway
On Thursday, 23 April 2020 04:00:50 UTC+8, branyine.s...@gmail.com wrote:
>
>
> > one more check for IMPOSSIBLE before output is that (a&b) + 1 is the
> power of 2 to avoid
> > cases like 101 and 1000010,
>
> I think that you missed the possibility not only convert two overlapping
> bits, but also covering missing bits. You can change e.g. 010001 to 0 -1 -1
> -1 1 1.
>
> ===
> My solution is based on the same bitwise approach, but a bit different way:
> 1. Impossible, if a%2==b%2. [Only the last bit can cause this!]
>
> 2. Suppose we are processing (i+1)-th bit, and we know that the i-th bit
> is different, 0 and 1 after previous steps applied. Consider following
> cases:
>
> a) you get 0 and 1 or 1 and 0 as next bits respectively: you are done.
> b) you get 0 and 0 for the bits: you change the i-th and (i+1)th bit of
> the one which had 1 on the i-th to -1, 1. Sum of bits so the value of the
> number is the same.
> c) you get 1 and 1 for the bits: you change the one which had 1 on the
> i-th to -1,0 _and_ while you find 1-bits on i+2, i+3, ... bits, set them to
> 0, and set the first 0 to 1. Value is still the same.
>
> As you only wrote -1 in the "past" bits, and you result always 0 and 1 in
> the current bit for the next step, this algorithm will always end with a
> valid result.
> [In a very abstract level actually this is the same as the explanation
> has.]
>
> I don't know whether my python code helps or not.
>
> Axioma / Kata
>
>
> T = int(input())
> bits = [2 ** i for i in range(64)]
> for tst in range(T):
> X, Y = map(int, input().split())
> absX, absY = abs(X), abs(Y)
> mx=len(bin(max(absX,absY)))-2
> ok=absX%2!=absY%2
> if ok:
> dir1 = "EW" if X == absX else "WE"
> dir2 = "NS" if Y == absY else "SN"
> aX = [1 if absX & bits[i] != 0 else 0 for i in range(64)]
> aY = [1 if absY & bits[i] != 0 else 0 for i in range(64)]
> for i in range(1,64):
> if i>=mx:
> break
> if aX[i-1]==0:
> if aX[i]==0:
> if aY[i]==0: # else all OK
> aY[i]=1
> aY[i-1]=-1
> else:
> if aY[i]!=0:
> aY[i]=0
> aY[i-1]=-1
> j=i+1
> while aY[j]==1:
> aY[j]=0
> j+=1
> aY[j]=1
> if j>=mx:
> mx=j+1
> else: # means aY[i-1]==0:
> if aY[i]==0:
> if aX[i]==0: # else all OK
> aX[i]=1
> aX[i-1]=-1
> else:
> if aX[i]!=0:
> aX[i]=0
> aX[i-1]=-1
> j=i+1
> while aX[j]==1:
> aX[j]=0
> j+=1
> aX[j]=1
> if j>=mx:
> mx=j+1
> if not ok:
> print("Case #" + str(tst + 1) + ": IMPOSSIBLE")
> else:
> res=""
> for i in range(mx+1):
> if aX[i]!=0:
> res+=dir1[0] if aX[i]==1 else dir1[1]
> else:
> if aY[i]!=0:
> res += dir2[0] if aY[i] == 1 else dir2[1]
> print("Case #" + str(tst + 1) + ": " + res)
>
> 2020. 04. 21. 19:19 keltezéssel, Alexander Iskhakov írta:
>
> 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
>
>
>
--
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/c8556ad3-9c4f-49b0-b086-6a893e558bcb%40googlegroups.com.
