This started when I was trying to solve 1982D - Beauty of the mountains — Beauty of the Mountains.
While working on it, I noticed something interesting about how a single operation changes the difference between the sums of snowy and non-snowy mountains. I started playing around with the coefficients I was getting, and eventually ended up with a completely different problem.
Looking back, I either overlooked that the operation allows a negative constant, or never thought about what that actually meant. I was treating every contribution as something that could only be used through non-negative multiples, and that sent me down a slightly different path.
But instead of throwing the idea away, I thought: why not see where it goes? I wanted to know whether the problem I'd accidentally created even had a solution, especially with such huge constraints.
The obvious approaches didn't look feasible, so I took some help from AI. (No one really helps an Expert, sad ;-;.) With its help I figured out that the problem is solvable after all, as long as the constraints are bounded properly if it's meant to run in 1–2 seconds as a CP problem.
And then I thought, why not turn it into a problem statement? It's fun. Larping maths is fun.
(Obvious disclaimer: the technique underneath is well known: the coin problem, numerical semigroups, Apéry sets. I'm not claiming to have invented anything. This post is about the detour.)
The problem
Non-Negative Representation
You are given an array of $$$n$$$ positive integers $$$a_1,a_2,\ldots,a_n$$$ and a positive integer $$$x$$$.
In one operation, you can choose an index $$$i$$$ ($$$1\leq i\leq n$$$) and a non-negative integer $$$k$$$, and subtract $$$k\cdot a_i$$$ from $$$x$$$, provided that the resulting value of $$$x$$$ is non-negative.
You can perform this operation any number of times, choosing indices and multipliers independently each time.
Determine whether it is possible to make $$$x$$$ exactly equal to zero. Equivalently: can $$$x$$$ be written as $$$k_1a_1+\cdots+k_na_n$$$ with all $$$k_i\ge0$$$?
Input
The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1\leq n\leq500$$$, $$$1\leq x\leq10^{18}$$$).
The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i\leq10^{12}$$$).
Let $$$g=\gcd(a_1,a_2,\ldots,a_n)$$$. It is guaranteed that
Output
Print YES if it is possible to make $$$x$$$ exactly equal to zero. Otherwise, print NO.
Examples
Example 1
Input
3 25
17 5 10
Output
YES
Example 2
Input
2 14
6 10
Output
NO
Example 3
Input
4 1000000000000
7 11 13 17
Output
YES
Example 4
Input
2 998999
1000 1001
Output
NO
Note. In the second example, dividing by $$$g=2$$$ gives $$${3,5}$$$ and $$$x=7$$$, which is exactly the largest number that can't be formed. In the fourth, $$$998999=1000\cdot1001-1000-1001$$$ is again the largest non-representable number, and $$$x=999000$$$ would give YES.
Hints
Final thoughts
I honestly don't know whether this exact formulation exists somewhere. It probably does, and the underlying techniques are definitely established. I'm not claiming to have invented anything. I just had fun getting there.
What started as an attempt to solve a Codeforces problem turned into a detour through a completely different one, and I ended up learning about a neat connection between number theory and shortest paths, all by following an idea that wasn't even relevant to the original solution.
What I liked most is how much one small restriction changes things:
versus
They look almost identical, but they need very different approaches.
Anyway, I enjoyed the process of finding this, and maybe someone else will find the problem or the observation interesting too.
Acknowledgement: I used AI assistance while exploring the non-negative version, and later to help formalize the solution, check the correctness proof, refine the constraints, and improve the wording of this post. The initial grid observation and the idea behind this whole detour came from my own attempt at 1982D. The mathematical techniques themselves are established ones.







