### YouKn0wWho's blog

By YouKn0wWho, 5 years ago,

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
• +16

| Write comment?
 » 5 years ago, # |   +46 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$.
 » 5 years ago, # | ← Rev. 3 →   +29 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.XDHere is a classical problem.
•  » » 5 years ago, # ^ |   +8 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?
•  » » » 5 years ago, # ^ |   +3 Maybe SPFA is faster than dijkstra.At least SPFA is faster in that classical problem.
 » 5 years ago, # |   0 can u provide link to the questions
•  » » 5 years ago, # ^ |   +5 some of them popped out of my head