Internet Problem Solving Contest

IPSC 2018

Solution to Problem I – Incorrect expression

There is no clever idea here, just blood, sweat and tears. First you must parse the expression and create a syntax tree. For every node, you must compute its current value, and find a f(x)=ax + b function that can tell you how the whole expression’s final value changes if you change the value of this node. Then you compute all the prefix sums, suffix sums, prefix products and suffix products. This will allow you to try every possible character replacement in constant time.

We will add more details to the booklet soon.