please wait
- Forum
- General C++ Programming
- Flowers Problem
Flowers Problem
Mar 14, 2011 at 10:38pm
We have n children that have gathered k flours each.The flours are numbered from 0 to 100.One girl can join a group if she has at least one flour of the same type with at least one girl in the group.
On the first line of the input file we have the number n followed by k.
Then we have n lines with k numbers on each line representing the flower types.
In the output file file we have on each line one group composed of the girls order numbers.(ascending order)
Determine the groups that can be formed.
Example:
Input:
5 4
1 2 3 4
5 6 9 6
1 1 1 1
2 4 4 3
7 7 7 7
Output:
1 2 3
2
5
Please help, my i struggled for 3 hours and I found no way of making the groups.
On the first line of the input file we have the number n followed by k.
Then we have n lines with k numbers on each line representing the flower types.
In the output file file we have on each line one group composed of the girls order numbers.(ascending order)
Determine the groups that can be formed.
Example:
Input:
5 4
1 2 3 4
5 6 9 6
1 1 1 1
2 4 4 3
7 7 7 7
Output:
1 2 3
2
5
Please help, my i struggled for 3 hours and I found no way of making the groups.
Mar 14, 2011 at 11:03pm1 2 3 2 5 |
This doesn't even make any sense, at least not according to the definition above.
If the input is:
5 girls have gathered 4 flowers each girl 1: 1 2 3 4 girl 2: 5 6 9 6 girl 3: 1 1 1 1 girl 4: 2 4 4 3 girl 5: 7 7 7 7 |
According to the definition, a girl is a set numbers. A group is a set of girls, where the intersection of one girl with another of the group is not the empty set. This definition isn't consistent with the example output you gave us, because either intersections of a girl with itself are allowed to form a group, which would sort of make the definition of a group pointless- because that would mean any girl can join any group - or one-member groups aren't possible (because there aren't any other girls you could form intersections with). Of course you could also say that all girls that do not qualify for a group according to the first definition make a new group with only themselves as the member (useful, because that clears the question how a group is formed in the first place), however that doesn't explain why girl 2 is in a one person group AND in a 3 person group...
Unless I am misunderstanding your task, it doesn't really make any sense.
Mar 15, 2011 at 1:07amclosed account (D80DSL3A)
Is the given output correct? I think I understand the problem, but I don't get this result.
Almost though, I see:
1 3 4 because girl1 has a flower in common with both girl3 (flower1) and girl4 (flower2)
2 no one else has flowers 5,6 or 9
5 no one else has flower 7
Almost though, I see:
1 3 4 because girl1 has a flower in common with both girl3 (flower1) and girl4 (flower2)
2 no one else has flowers 5,6 or 9
5 no one else has flower 7
Mar 15, 2011 at 1:16am
@fun: Yep, I got the same result. Let's see what the OP says to this.
Mar 15, 2011 at 8:46am
oh I'm terribly sorry I messed up the output.The output is:
1 3 4
2
5
And yes if a girl does not qualify for a group she forms her own.
1 3 4
2
5
And yes if a girl does not qualify for a group she forms her own.
Mar 15, 2011 at 12:11pm
Looks like creating a proper graph and finding all connected components of the graph.
Can be done efficiently in O(n) time with less than 20 short lines of high level code.
Can be done efficiently in O(n) time with less than 20 short lines of high level code.
Last edited on Mar 15, 2011 at 12:16pm
Mar 16, 2011 at 9:44amclosed account (D80DSL3A)
Why not ask rapidcoder about his idea instead of ignoring it?
Were you able to see how the sample output makes sense? If so and you can put how you figured it out in writing then you will be well on the way.
Were you able to see how the sample output makes sense? If so and you can put how you figured it out in writing then you will be well on the way.
Topic archived. No new replies allowed.