passworld's blog

a problem on math (hard)
By passworld, 10 years ago, In English

Here is a hard problem for me:

time limit per test4 seconds memory limit per test256 megabytes

Given a,b (1<a<b<1000,integer) and (a,b)=1

Try to find an array P[ ] (size unknown)so that:

  • there exist a positive integer k so that:
  • ( Sum of P[i] )== k * a
  • For all i : ( k*b ) % P[i]==0 and then we note A[i]=k*b/P[i]

We want to output A[].

NOTE: elements in P[ ] are(is) positive integer and size of P[ ] should be as small as possible and if it is tied for some possible arrays with equal minimal size, choose one array that elements ofA[ ] are as small as possible. (not element of P[],where I typoed before ,I am so sorry for that!)

Thank you in advance!

sample in a=3 b=10 ; sample out A={5,10}

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What do you mean by stating 'elements of P[] are as small as possible'?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I mean if there are equal minimal size array, you should output one array with smaller number inside the array.something like lexicographical order... for example:

    if array 20 10 (10) 5 and 20 10 (5) 5 are both anwser(after sorted from big to small), then choose the second one to output. Thank you so much for your response!

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are you sure the first sample is correct? Sum of P[i] is here 52499 (an odd number), which cannot be a multiple of 732 (which is even).

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah :) Note that here we have k. And the k in the statement only shows that we can multiply the same positive integer k both on a and b to find an array.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Really? What kind of positive integer k that k * 732 is a odd number?

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is this problem from? And what is the time limit?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry but there is no English form of this problem.time limit is 4 second .

    → Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

second sample : p = {1,2}

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I am so sorry for that!After edited the statement ,here we calculate A[i]=k*b/P[i], under the condition that for all i k*b can be divided by P[i]. We want to minimize A.

    → Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Here is something appeared in my mind so far:

i) P[1]+P[2]+...P[n]=k*a;

ii) for all i=1..n, A[i]=k*b/P[i].

Hence, 1/A[1]+1/A[2]+...+1/A[n] = (P[1]+P[2]+...+P[n]) / (k*b) = (k*a) / (k*b) = a/b.

So what we are discussing here is pretty similar to the problem finding the shortest Egyptian Fraction representation of a/b. I still have no idea how to solve it yet, however I hope my thoughts can help you a little bit. Thanks again for such an interesting problem :)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yep. And there is a corresponding problem at UVa: (link). It seems that for a<b<=876 we can use at most 5 terms in P[] — hope, it will simplify a little bit more.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +6 Vote: I do not like it

      Not really I'm afraid. For example, in the first sample test case (which was deleted by some reasons) where a=722, b=723, the optimal array P has 7 elements. I hope it is the only exception anyway :)

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        According to your hint I find that the true understanding of the original sample is that 732/733=1/2+1/3+1/7+1/45+1/7330+1/20524+1/26388 where the input is 732 , 733 and the output is 2 3 7 45 7330 20524 26388

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Sorry, I misunderstood problem statement... There are at most k restricted denominators in that problem. But I have also found one old forum link. There are only few exceptions that need more than six terms.

        → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Yeah.I agree with your idea! Thank you for that hint:Egyptian Fraction .In the story of the original statement it also mentioned a Egyptian guy!

    → Reply