4
\$\begingroup\$

I'm resolving a problem from CodeForces: C. Beautiful XOR. This is what the code is supposed to do:

You have two numbers a and b.

You must transform a into b using XOR operations (a = a ⊕ x) by choosing values for x ​​that lie between 0 and the current value of a.

You must find a valid sequence of 100 operations at most or declare it impossible.

This is my code implementing a BFS algorithm to look for numbers by importing collections and checking with something similar to two pointers.

from collections import deque

def transformar_xor(a, b): #is they  the same no worues no need to operation
    if a == b:
        return []

    cola = deque([(a, [])])   #this is the tail of the BFS basically
    visitados = {a}         #this is the visits numbers to avoid same number many times
    max_operacion = 100 #codeforce only acept 100 operations

    while cola:
        valor_actual, camino = cola.popleft()

        if len(camino) >= max_operacion:
            continue

        for x in range(1, valor_actual):
            siguiente_valor = valor_actual ^ x

            if siguiente_valor == b:
                return camino + [x]

            if siguiente_valor not in visitados:
                visitados.add(siguiente_valor)
                cola.append((siguiente_valor, camino + [x]))

    return None

#this last code is just because is the way codeforce read the logic
t = int(input())
for _ in range(t):
    a, b = map(int, input().split())
    secuencia = transformar_xor(a, b)

    if secuencia is None:
        print(-1)
    else:
        print(len(secuencia))
        if len(secuencia) > 0:
            print(*secuencia)

I think my BFS is checking for too much values in x but I'm not sure what change in this variable. I quit the + 1 but still having the same TLE issue.

for x in range(1, valor_actual + 1):

If someone could explain more and help me see where the infinite cycle is coming to produce TLE in my algorithm, I would be appreciative; I've been coding this for almost 2 hours and nothing comes to mind.

\$\endgroup\$
1
  • \$\begingroup\$ For time-limit-exceeded questions, it's helpful to demonstrate that your code works for smaller inputs, and give an indication of how the performance tails off as the input grows. \$\endgroup\$ Commented Oct 18 at 8:47

2 Answers 2

Reset to default
8
\$\begingroup\$

You can improve the performance by using an \$O(1)\$ algorithm.

  1. Turn all the bits on.

    a = 0b1010_1110
full = (1 << a.bit_length()) - 1
print(f"{a:b}\n{full:b}")
# 10101110
# 11111111

  2. Check b is less than or equal to full.

    a = 0b0_1111
b = 0b1_1111

    Here a can never become b because the xor needed is 0b1_0000 which is one more than a.

  3. Find out how to change from a to full to b.

    a = 0b1010_1110
b = 0b1111_0000
c = a ^ full
d = b ^ full
print(f"a: {a:b}\nc: {c:08b}\nf: {a ^ c:b}\nd: {d:08b}\n-: {a ^ c ^ d:b}\nb: {b:b}")
# a: 10101110
# c: 01010001
# f: 11111111
# d: 00001111
# -: 11110000
# b: 11110000
\$\endgroup\$
0
\$\begingroup\$

Here are some general coding style suggestions.

UX

When I run the code, it sits there waiting for input, but I have no idea what I should type at the prompt.

Instead of a bare input:

t = int(input())

you should add text to the prompt to guide the user:

t = int(input("Enter an integer: "))

You should enhance the message to be more specific about what the number means.

This also needs text:

a, b = map(int, input().split())

Something like:

a, b = map(int, input("Enter 2 integers separated by a space: ").split())

After I enter the required data, the code just quits without showing the user anything. Perhaps you could print the result.

Documentation

The comments in the code look helpful, but the PEP 8 style guide recommends adding docstrings for functions and at the top of the code.

You could convert this comment:

def transformar_xor(a, b): #is they  the same no worues no need to operation

into a docstring:

def transformar_xor(a, b):
    """
    Transform a into b using XOR operations (a = a XOR x)
    by choosing values for x that lie between 0 and the current value of a.
    """

It would be helpful to describe the return type for the function. Sometimes it returns None, other times an empty array, other times something else. This seems inconsistent.

Naming

PEP 8 recommends naming a constant:

max_operacion = 100

using upper case:

MAX_OPERACION = 100

The code is bilingual. It might be less distracting if all identifiers and comments were in English.

\$\endgroup\$
5
  • 3
    \$\begingroup\$ The program is meant to be submitted to a programming contest, not to be run interactively. It could be that the "main" program is part of the Codeforces submission template. \$\endgroup\$ Commented Oct 18 at 15:45
  • \$\begingroup\$ The "main" part of the code might still be in a main function. This can either be then simply called or wrapped in a main test. \$\endgroup\$ Commented Oct 18 at 17:07
  • \$\begingroup\$ @MartinR: I am aware the question relates to a contest (I added the programming-challenge tag to the question before I posted my answer). While I am unfamiliar with the mechanics of the CodeForces site, my review of the code as posted in the question still has value. All code posted in a question here is eligible for review, and I made several specific suggestions with the intention of helping the OP and any other readers. If there is something unclear about my answer, I would appreciate specific suggestions for improvement. \$\endgroup\$ Commented Oct 20 at 19:50
  • 2
    \$\begingroup\$ @toolic: I did not say that your review does not have value (and I did not vote on your answer). I wrote that comment because I assume that the code for reading the input data is written as it is for a reason, and adding an input prompt (as you suggested) might even prevent a successful submission on that site. I know that all parts and aspects of code can be reviewed, but (IMHO) there is also context to consider. Here the context is a submission to a programming challenge site, and not an interactive program. \$\endgroup\$ Commented Oct 20 at 20:11
  • \$\begingroup\$ @MartinR: I appreciate you taking the time to clarify your original comment. I wasn't quite sure what you were trying to convey, but I understand it better now. These TLE questions are always a bit tricky, and the answer is often to scrap the code and start with a new algorithm/approach. I leave that up to the smarter users, like the 1st answer, then I try to backfill with more straightforward advice. \$\endgroup\$ Commented Oct 20 at 20:33

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.