hashlife's blog

Southern Subregional Programming Contest 2012 Problem B
By hashlife, 14 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

»
14 years ago, hide # |
← 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
»
14 years ago, hide # |
 
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
  • »
    »
    14 years ago, hide # ^ |
     
    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
    • »
      »
      »
      14 years ago, hide # ^ |
       
      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
  • »
    »
    14 years ago, hide # ^ |
     
    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