> 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)
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 [email protected].
To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/165b625c-1491-ff4d-43f4-07c577748563%40kata.branyi.hu.
