hashlife's blog

Southern Subregional Programming Contest 2012 Problem B
By hashlife, 12 years ago, In English

Can someone tell me how to solve this problem? http://acm.sgu.ru/problem.php?contest=0&problem=543

Thanks a lot :)

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

»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Greedy? My approach:

First, for each index, decrease the number a(i-th) by r x times until the a(i-th) number is less than r. If a(i-th) is equal to 1, add 1 to a(i-th). Add x to the total number of tables needed.

For first sample inpuT, After this step, it should be like a[]=[2,2,3] and total number of tables=3 Then,sort the a[] in accending order. Followed by filling in the rest of the people, we match the index with a for-loop. For each for-loop, if the number is 0, simply ignore it.

if the number >= (r/2+1), we break the loop and check the number of indexes with is not equal to 0 and output(number oF table+number of indexes)

iF the number,say x, > 0 but < (r/2+1), we find the minimum matching index, say y, so that (x+y)<=r and y is not equal to 0.

if y does not exist, we break the loop and output as mentioned above.

if y exists, we set y=0, and set x=x+y, and find out more minimum matching indexes y' so that (x+y')<=r. If we find more y', set all y' to 0 and add it to x. If we cannot find more, we continue the for-loop.

if the for-loop runs til the end,output as mentioned above

Complexity: O(n^2)

But I think that the algorithm is not correct. Anyway at least for some cases it works ;)

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

Thanks a lot for replying. Interesting idea you have there, but I think it will fail for this case:

6 4 6 4 4 4

The correct output is 3, but I think your algorithm would produce 4 (please correct me if I'm wrong).

I tried n^2 dp with a greedy heuristic, but found some cases for which my code fails after getting Wrong Answer.

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

    I see it. More spliting can be done so to reduce the size.

    maybe we split all numbers to 2 and 3 first?

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

      Hmm..that's a nice idea :). I haven't thought of that before. Splitting all the numbers to 2 and 3 and recording their frequency. I think if we can split the numbers appropriately a greedy algorithm would work. But the question is how do you split the numbers appropriately. Say in one group there are 6 people. So do you split them in 3 2's or 2 3's? One would produce optimal result and the other may not.

      I think the only method for solving this is greedy, but can't figure out a proper greedy algorithm which passes all the cases I thought of. I tried to solve this with dp, but it seems impossible.

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

    If the number is odd, we express it as 2n+3, where n>=0, and split the number into n 2s and one 3.

    If the number is even, we express it as 2n, where n>=1, and split the number into n 2s

    then combination

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

      Doesn't work if we split like that. For example 1 3 6

      You would get 2,2,2 after splitting and this would require 3 tables. But this can be done in 2 (3, 3)

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

        emm we can do reduction first followed by spliting

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

          What do you mean? Reduction doesn't always work. Can you simulate this test case?

          4 6

          6 3 3 3

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

            3 tables?

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

              Yes, but will your algorithm output 3? I think it will output 4.

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

                4 6

                Reduction

                0 3 3 3

                Spliting

                0 3 3 3 (3=0*2+3)

                Combination

                0 6 3 0

                → Reply