Hackerrank – Problem Statement
A description of the problem can be found on Hackerrank.
Solution
I will create all posible pairs of players. That means I will try to combine every possible combination of player pairs. The topics are given in binary way. I will use OR operation on binaries. It is enough that one of the players knows the topic.
I will find all teams (pairs) with most known topics and count them.
I created solution in:
All solutions are also available on my GitHub profile.
Scala
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
import java.math.BigInteger import java.util.Scanner object Solution extends App { val scanner = new Scanner(System.in) val players = scanner.next.toInt val topics = scanner.next.toInt val teamTopics = new Array[BigInteger](players) var i = 0 while ( { i < players }) { val input = scanner.next val binary = new BigInteger(input, 2) teamTopics(i) = binary { i += 1; i - 1 } } val knownTopicsPerTeam = for { i <- 0 until players j <- i until players } yield { val commonTopics = teamTopics(i).or(teamTopics(j)) knownTopics(commonTopics, topics) } val maxTopics = knownTopicsPerTeam.toList.max val teams = knownTopicsPerTeam.count(_ == maxTopics) println(maxTopics) println(teams) private def knownTopics(binary: BigInteger, topics: Int): Int = { (0 until topics).map(binary.testBit).count(_ == true) } } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
import java.math.BigInteger; import java.util.Scanner; public class AcmIcpcTeam { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int players = Integer.parseInt(scanner.next()); int topics = Integer.parseInt(scanner.next()); BigInteger[] teamTopics = new BigInteger[players]; for (int i = 0; i < players; i++) { String input = scanner.next(); BigInteger binary = new BigInteger(input, 2); teamTopics[i] = binary; } int teams = 0; int maxKnownTopics = 0; for (int i = 0; i < players; i++) { for (int j = i + 1; j < players; j++) { BigInteger commonTopics = teamTopics[i].or(teamTopics[j]); int knownTopics = knownTopics(commonTopics, topics); if(knownTopics > maxKnownTopics) { teams = 1; maxKnownTopics = knownTopics; } else if(maxKnownTopics == knownTopics) { teams++; } } } System.out.println(maxKnownTopics); System.out.println(teams); scanner.close(); } private static int knownTopics(BigInteger binary, int topics) { int result = 0; for (int i = 0; i < topics; i++) { if(binary.testBit(i)) { result++; } } return result; } } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
'use strict'; const processData = input => { const lines = input.split('\n'); const players = parseInt(lines[0].split(' ')[0]); const topics = parseInt(lines[0].split(' ')[1]); const teamTopics = lines.slice(1); let teams = 0; let maxKnownTopics = 0; for (let i = 0; i < players; i++) { for (let j = i + 1; j < players; j++) { const knownTopics = knownTopicsFunc(teamTopics[i], teamTopics[j], topics); if(knownTopics > maxKnownTopics) { teams = 1; maxKnownTopics = knownTopics; } else if(maxKnownTopics == knownTopics) { teams++; } } } console.log(maxKnownTopics); console.log(teams); } const knownTopicsFunc = (binary, binary2, topics) => { let result = 0; for (let i = 0; i < topics; i++) { if(binary[i] === '1' || binary2[i] === '1') { result++; } } return result; } process.stdin.resume(); process.stdin.setEncoding("ascii"); let _input = ""; process.stdin.on("data", input => _input += input); process.stdin.on("end", () => processData(_input)); |