You are not logged in. Please login at www.codechef.com to post your questions!

×

RIO1 - Editorial

PROBLEM LINK:

Practice

Author: Vishal Khopkar

DIFFICULTY:

EASY

PREREQUISITES:

Graphs, sorting

PROBLEM:

RIO Olympics 2016 is hosting a team event where n teams are segregated into k groups such that n%k=0 and each group contains n/k teams. You've been given a partial schedule of the tournament and job is to segregate the teams into k different groups. However, neither n nor k has been directly given to you. What has been given is the partial schedule of x matches. With the help of this schedule, you need to print the teams segregated into different groups in alphabetical order. Also print the two groups by printing the group which contains the alphabetically first team first. Although the schedule is partial, it contains at least one match of each team.

EXPLANATION:

Read each line of the schedule and form a graph accordingly. Draw an edge between two teams if there is a match between them. For example, if the first match is BRAZIL vs ARGENTINA, there would be an edge between Brazil and Argentina in the graph. For more explanation, you can see the image in the link :

Image

Hence, just see the number of connected components in that graph. However, you need to see that there are equal number of teams in each group. Hence, you may need to merge a few connected components to make a group.

SOLUTION

Thanking Mr. Manas Kumar Varma for the solution

Solution

asked 02 Nov '16, 17:29

abhirajphadnis's gravatar image

0★abhirajphadnis
42
accept rate: 0%

edited 29 Mar '17, 12:50

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,719
×1,228
×368
×1

question asked: 02 Nov '16, 17:29

question was seen: 579 times

last updated: 29 Mar '17, 12:50