These are the problems that I found while solving some other problems and some of them popped out of my head and guess what! Again I couldn't come up with a solution. So here I am, asking for your help. I heard you like solving new problems.
Problem 1
Problem 2
Problem 3
Problem 2 is just finding the order of $$$a$$$ mod $$$p$$$. It can be done in $$$O(\sqrt{p})$$$ with the baby-step giant-step algorithm.
Problem 3 is NP-hard, but of course has a solution in O(nK). We reduce it to subset sum. If we want to know if some subset of $$$v_{1}, \dots, v_{n}$$$ has sum $$$k$$$, set $$$s = 1 + n \max v_{i}$$$, and make the numbers $$$a_{i} = v_{i} + s 2^{i} + s 2^{n}$$$, $$$a_{i + n} = s 2^{i} + s 2^{n}$$$. Now some subset of the integers $$$a_{1}, \dots, a_{2n}$$$ has sum $$$k + sn 2^{n} + s(2^{n} - 1)$$$ iff some subset of $$$v_{1}, \dots, v_{n}$$$ has sum $$$k$$$.
I can solve Problem 3 in $$$O(n^2*\min{a_i})$$$.
I don't know whether you know it.It is called "Congruence shortest-path problem".
We can find minimum value of $$$a$$$.Then build a graph which has $$$\min{a_i}$$$ nodes numbered from 0.
We can find that if there exist a solution satisfies $$$\sum_{i=1}^na_i*x_i=M$$$, there must be a solution satisfies $$$\sum_{i=1}^na_i*x'_i=M+\min{a}$$$.So the only question is to find the minimum value $$$L$$$ satisfies $$$L \equiv K$$$ ($$$\mod \min{a_i}$$$).
We add edges $$$(t,(t+a_i)\mod min{a},a_i)$$$ for each $$$i$$$.
If the shortest path between $$$0$$$ to $$$x$$$ equals to $$$val$$$, $$$val$$$ is the minimum value $$$L$$$ for remainder $$$x$$$.
So we can use SPFA Algorithm now.I don't know if it's $$$O(n*\min{a_i})$$$, but it's fast, that's enough.XD
Here is a classical problem.
Interesting Idea! Thank you for this.
I solved the problem as per your instructions and ACed in 4000ms using Dijkstra. I tried Bellman_Ford and it TLEd. But some users solved it in 30ms. How to achieve this much efficient solution?
Maybe SPFA is faster than dijkstra.At least SPFA is faster in that classical problem.
can u provide link to the questions
some of them popped out of my head