Problem 1883. GJam 2013 China Event: Happy Teams 100 Pairs

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This Challenge is derived from</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://code.google.com/codejam/contest/2933486/dashboard#s=p0\"><w:r><w:t>GJam 2013 China Bad Horse</w:t></w:r></w:hyperlink><w:r><w:t> partial of data set #2. Cody appears to have a testsuite size limit so only 32 of 100 cases are loaded. Brute force of 2^100 permutations may time out. The problem is codified using a cell array of names.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The Challenge involves creating two teams with no pair of individuals on either team having a conflict. The input is a list of pairs of individuals who can not be placed on the same team. The Challenge is to determine if two teams can be created that do not have any players with conflicts.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> conflicted name pairs (cell array of pairs of names)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> TF (TF=1 if two Good teams are possible, 0 if Happy teams are non-producible)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Competition Summary:</w:t></w:r><w:r><w:t> Best Time of 11 minutes, 707 out of 776 correct</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

39 Solutions
9 Solvers

Last Solution submitted on Sep 22, 2020

Last 200 Solutions

Problem Comments

4 Comments

4 Comments

Show 1 older comment

Richard Zapor on 19 Sep 2013

I tried to put in all 100 cases but the testsutie clipped. Had similar problem on my 3900 test cases of Cannon Ball.

Alfonso Nieto-Castanon on 20 Sep 2013

If I am not mistaken several of the current solutions would fail the following test: names={{'a','b'}, {'c','d'}, {'d','e'}, {'e','c'}}; (they should return 0)

Richard Zapor on 21 Sep 2013

I will run the solutions against the full Google Set to find a more robust subset of test cases. I may also add your suggested case. Thank for the feedback.

Rafael S.T. Vieira on 22 Sep 2020

Good example from Alfonso. I had to fix my code. The problem is pretty much about trying to create a tree. Alfonso's example creates a small forest: a case that seems to be lacking from the test suite.

Solution Comments

Solution 321492

1 Comment

1 Comment

Alfonso Nieto-Castanon on 20 Sep 2013

note: this solution is not correct (e.g. {{'a','b'},{'b','c'},{'c','a'},{'d','e'}} should return 0)

Solution 320975

1 Comment

1 Comment

Tobias Schäfer on 19 Sep 2013

Elapsed time is 0.047208 seconds.
:-D

Solution 320964

1 Comment

1 Comment

Alfonso Nieto-Castanon on 19 Sep 2013

0.087544s

Solution 320941

1 Comment

1 Comment

Alfonso Nieto-Castanon on 19 Sep 2013

going for speed here (6 problems in 0.168566s)

Problem Recent Solvers9

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 1883. GJam 2013 China Event: Happy Teams 100 Pairs

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers9

Suggested Problems

More from this Author255

Problem Tags

Community Treasure Hunt

Problem 1883. GJam 2013 China Event: Happy Teams 100 Pairs

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers9

Suggested Problems

More from this Author255

Problem Tags

Community Treasure Hunt

Players