wil93's blog

How to compute this in 10s ?
By wil93, 13 years ago, In English

An automatic machine has N coins inside, each one with a value. You should compute the smallest amount of money that the machine wouldn't be able to give.


In other words, given a set S of N positive integers, find the smallest integer wich cannot be expressed as a sum of one or more elements of S.

Example:

S: 10 2 14 1 13 2 3
Answer: 9

S: 1 16 2 1 23 18 1 4 3
Answer: 13

For N coins with maximum value MAX it's easy to find the answer in O(N2), for each new coin, I set its value as "avaible", then for all the older coins I set avaible the value coin[i] + new_coin

This would require an array of MAX booleans.

Now, I have 10 seconds for computing this answer for P machines.

Here's the hard part:
  • 1 ≤ P ≤ 1000
  • 1 ≤ Ni ≤ 10 000 (amount of coins per machine)
  • 1 ≤ Mj < 220 (value of a single coin)
  • For each machine, the sum of all coins is always smaller than 231
  • Vote: I like it
  • 0
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
You can solve this problem for one machine in O(NlogN). Try to sort all coins in ascending order of their values and iteratively build the set of all representable numbers. Then see what happens with this set after adding a new number.
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes, but how to build that set?

    S: 10 2 14 1 13 2 3

    We sort it: 1 2 2 3 10 13 14

    If I just do:

    sum = 0
    for i=1 to n
    ...sum += coin[i]
    ...set sum and coin[i] as avaible

    Then it wouldn't be correct, because it would set 1, 2, 3, (2), 5, 10, 15, ...

    But it is possible to give 4 !

    EDIT: Anyway, if I do it in O(n2) it works, but there's always the same problem: the set will become very large
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      You should set not only sum and coin[i] as available. For example, after adding the first three coins all numbers from 1 to sum (which is equal to 5) will be available. I don't want to reveal the whole solution now, try to figure it out by yourself using the hint I gave.
      → Reply
    • 13 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it
      It is not a good idea to add something new to the comment after it has been answered.

      You don't need to store the whole set directly. Just look on its structure and try to find a way to maintain it after adding new numbers into it.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Thanks, but if I have "1, 100, 101, 102" then the first number that isn't avaible would be 2, how can I say that numbers from 1 to sum are all avaible? (note: you can use each coin only one time)

        Anyway, maybe I updated my post before refreshing the page. Sorry I didn't see your post.

        What is RPC call... ?
        → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Yep, I just noticed that the set size will be 10.000 at most (not 231)... So the O(n2) should work...
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          It won't work for 10000 machines, that's why I told you about O(NlogN) solution. After figuring out how to solve it in O(NlogN) for one machine, you'll be able to solve the whole problem in O(P*N*logN).

          Btw, it is better to continue the discussion in private messages.
          → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Each time adding a number , i see that the set is still a consecutive sequence .Is it right ? 
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it
      Partially true. It may happen that after adding some number set stops being a consecutive sequence and this case is the most important in this problem.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Wow, nice solution! If the sequence is not consecutive anymore, then we would have found our answer! =D
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Can you explain what is a "consecutive sequence" ?
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            After you sorted the sequence of coints (lets call this C), let Ai be the sequence of values you can make using the set of coints from C1 to Ci.

            Then we consider two cases.

            1) Ai is a consecutive sequence of values from 1 to some value X, where X is the sum of coins from C1 to Ci. Then we know that the answer is not in the range [1,X].

            2) Ai is not a consecutive sequence. Suppose there exist some value Y in A such that Y+1 is not in the sequence and Y is minimal. Then Y+1 is your answer.

            So when you loop through the sorted sequence of coins, all you need to do is to keep track of the value X. The moment the sequence becomes disjoint, you have your answer.
            → Reply
            • 13 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              X = 0
              sort C
              for i=1 to n-1
              ...X+=C[i]
              ...Y=X+C[i+1]
              ...// if not consecutive...
              ...if (Y-X > 1) output : X+1
              end for
              output : Y+1

              Is it right?

              If i have "1 2 2 5 5" then the values of X Y would be:

              X Y
              1 3 (not consecutive)
              3 5 (not consecutive)
              ...

              So the output would be 2, obviously wrong...
              → Reply
              • 13 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                If you have coins "1 2 2 5 5 100", then what happens to the set of representable numbers after adding each coin? Here C is the current set of coins and S is the current set of representable numbers.
                1) C={1}, S={1}
                2) C={1,2}, S={1,2,3}
                3) C={1,2,2}, S={1,2,3,4,5}
                4) C={1,2,2,5}, S={1,...,10}
                5) C={1,2,2,5,5}, S={1,...,15}
                After adding the last coin set S stops being consecutive, so the answer is 16.
                → Reply
                • 13 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  Ok, but am I supposed to update the set in constant time? I understood how to do it in O(n) where n is the current set size... For each S[i], add to it the new coin and insert this new value to the set (if it isn't already there).

                  But this leads to O(n2) solution with no need of sorting... You said O(nlogn) that is: sorting + O(n) for the creation of set.

                  Is this your approach? how to do that?
                  → Reply
                • 13 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  set = {0} // set size is 1
                  for i=1 to n
                  ...read new_coin
                  ...for j=1 to set.size
                  ......set.insert(new_coin+s[j])

                  With this approach also checking if the sequence is consecutive needs time...
                  → Reply
                  • 13 years ago, # ^ |
                      Vote: I like it 0 Vote: I do not like it
                    =============================================
                    Suppose that after some step the set S is equal to {1...X}. You want to add a new coin with the value of C. If C<=X+1, then it can be proven that after adding this coin the set S becomes {1...X+C}, otherwise the number X+1 is not representable so the algorithm outputs it and stops.

                    You don't need to maintain the whole set, it is sufficient to remember only one number X.
                    → Reply
                    • 13 years ago, # ^ |
                      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                      =====================================
                      << If C<=X+1 it can be proven that after adding this coin the set S becomes {1...X+C} >>

                      This is the part I was missing :D
                      Thanks a lot for your time :)

                      I really have to improve my math eye... I will also try to prove that statement

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


      → Reply