YouKn0wWho's blog

By YouKn0wWho, 5 years ago, In English

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
  • Vote: I like it
  • +16
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +46 Vote: I do not like it

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   Vote: I like it +29 Vote: I do not like it

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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Maybe SPFA is faster than dijkstra.At least SPFA is faster in that classical problem.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can u provide link to the questions

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    some of them popped out of my head