deinier's blog

Help in Abbyy Cup B problem.

By deinier, 12 years ago, In English

Hello community:

I am trying to solve B task in Abbyy Cup and I would like to know how can I build all the possible sums in an array of integers.

I am making all the components in the graph using dfs and I am using the PosF() function to get the position of X in its component.

At the end, I have a vector with the size of each component but I need to get all possible sums. Maybe it would be solved either by dp or by two pointers but right now I do not know how solve it.

It is something like this: Array of Components (I do not add the component that include X) = {3 8 1} and X is in the first position in its component -> Possible positions in the queue: 1, 1 + 1, 3 + 1, 4 + 1, 8 + 1, 9 + 1, 11 + 1, 12 + 1.

Here is my solution.

Thanks in advance.

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

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
    sol[posx] = 1;
    ncomp = comp.size();
    for(i=0;i<ncomp;i++)
     {
		for(j=n;j>=0;--j)
			if(sol[j])
				sol[j+comp[i]] = 1;
     }
→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    Thank you very much, I was so close ... Thanks, Thanks, Thanks. Here my AC solution. I copied and pasted your code. Great!!!!! I understood the dp, it is awesome.

    → Reply