Блог пользователя hashlife

Southern Subregional Programming Contest 2012 Problem B
Автор hashlife, 12 лет назад, По-английски

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

Thanks a lot :)

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 ;)

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    maybe we split all numbers to 2 and 3 first?

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

      → Ответить