ICPC NERC 2023, Evaluate it and back again(1912E)

Basic Description

Codeforces link to problem statement:  https://codeforces.com/problemset/problem/1912/E

basic gist is:

given an input l and r, generate a string of an expression which equals l when read left to right, and equals to r when read in reverse (right to left).  + - *  (less than 1000 characters)

Solution

observations and general idea:

first observation: numbers in expression, that are not palindromic change values, numbers like 199 read 991 in reverse, thus it will be more simple if we stick to palindromic numbers that just change the order of operations in reverse. it is also quite clear that digits won't change values.

second observation: we can easily deconstruct any expression in sums of palindromic numbers, especially represented as multiple of digits.  for example 100 = 99+1 , or 324 = 222 + 99 + 3

now we can start thinking how to structure the expression, if we take some expression g-m = x, notice that their reverse m-g = -x, now we can structure a basic idea around this, lets take a third variable called bias b, now structure of our expression can look like the following: g - m + b, and their reverse b + m - g, basically with this we can choose some point b on a number line and either subtract or add some distance value x, so main idea is l = b + x and r = b - x, where b = (l+r)/2.

Palindromic Decomposition:

In order to express numbers, where reversing them doesn't affect the expression, we need to deconstruct a sum of numbers as palindromes, where number N can be expressed as:

where p[i] is a number that's a palindrome (222, 111 , 9999 ...etc).

here's a pseudocode that decomposes numbers x as palindromes:

In case of even distance:

take the bias as b = (l+r)/2 and distance as x = max(l,r) - b , afterwards define expression, let's construct a simple general expression:

where q[i] is the palindromic deconstruction of bias (b) and p[i] is palindromic deconstruction of distance (x).

LR is read (Left to Right) and RL is read (Right to Left).

In case of odd distance:

In case of odd distance, it's bit trickier, as from bias b the distances should differ by one, we must somehow try to adhere to general structure of the expression we constructed and to modify it slightly.

Observations:

We can construct numbers where in reverse they give different expressions and express asymmetry, problem in the case of odd distance is precisely that, we don't know how to introduce asymmetry to the expression.

observation: notice how first non-palindromic number 12, gives us 21 in reverse, which gives us the asymmetry of 9 , let's somehow incorporate this into our structure.

for example, expression 4+8+12-8-4 gives us 12, while in reverse it gives us -13. we can use this asymmetry, let's define this expression as a = 4+8+12-8-4. now we can go on and modify the bias and distance calculation to include the asymmetry. let's work on an example, lets take l = 67  and r = -30. let's define our bias now as (67-30)/2 = 18.5., now we take ceil((l+r)/2) which will be 19. now we just modify the distance by adding 13 to the existing distance (x). thus the expression in case of odd distance looks like the following:

in case of negative bias, encase it with 0s: 0-q1-q2-q3...qk-0.

C++ code:

https://pastebin.com/s135XStc