CRICTOUR - Editorial

PROBLEM LINK:

**https://www.codechef.com/RSC2017/problems/CRICTOUR

**
Author: spraveenkumar

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Math

PROBLEM:

Chef wants to organise a cricket tournament in CodeLand. There are N teams taking part in the tournament. Now Chef has to prepare the schedule for the tournament. For that he needs to know what will be the number of matches in the tournament(excluding finals and semifinals). When each team plays with other team exactly once, what is the number of matches?

QUICK EXPLANATION:

There are n teams where each team plays with every other team once. So every n teams play (n-1) matches. So n(n-1). But wait, each match is played by 2 teams, so n(n-1)/2 matches is the solution.

EXPLANATION:

There are indeed multiple approaches to solve this problem. But the end result is always the same. Some common approaches are:

  1. Let’s consider 4 teams - A, B, C and D. A plays with the next 3 teams. B having already played with A, plays with C and D and C having played with A and B plays with D. You notice, the number of matches is 3 + 2 + 1 = 6. For n teams, it is (n-1)+(n-2)+(n-3)+…+1 which is [(n-1)(n-1+1)]/2 = (n-1)(n)/2
  2. Let’s consider n teams playing with every other team. So n teams play with (n-1) teams. So (n)(n-1) matches. This is exactly playing every match twice, where A playing with B and B playing with A are considered separately. Dividing this by 2, gives the number of matches when each match is played once. So (n)(n-1)/2

There are obviously more approaches that lead to the same solution.

COMPLEXITY:

O(1)

AUTHOR’s SOLUTION:

import java.util.Scanner;
class Match{
    public static void main(String args[]){
	Scanner sc = new Scanner(System.in);
	int t = sc.nextInt();
	while(t-- !=0){
		int n = sc.nextInt();
		int matches = (n*(n-1))/2;
		System.out.println(matches);
	}
	sc.close();
    }
}