CareerCup

object Solution {
  
  import scala.collection._

  type Email = String
  
  def readInput(): List[Email] = {
    val sc = new java.util.Scanner (System.in)
    var n = sc.nextInt()
    var emails = new Array[String](n)
    for(i <- 0 until n) {
      emails(i) = sc.next()
    }

    emails.toList
  }

  def isSimilar(email1: Email, email2: Email): Boolean = {
    val maxDistance = 2
    
    def countify(str: String): Map[Char, Int] = {
      str.groupBy(identity).mapValues(_.length)
    }

    def distance(str1: String, str2: String): Int = {
      val (c1, c2) = (countify(str1), countify(str2))
      val (s1, s2) = (c1.keySet, c2.keySet)
      val all = (s1 | s2).toList

      all.map(x => math.abs(c1.getOrElse(x, 0) - c2.getOrElse(x, 0))).sum / 2
    }
    
    distance(email1, email2) <= maxDistance
  }

  def groupBySimilarity(emails: List[Email], similarFunc: (Email, Email) => Boolean): List[Set[Email]] = {
    
    val res = emails.foldLeft(Map.empty[Email, mutable.Set[Email]])( (map, email) => {
      val key = map.keys.filter(k => similarFunc(k, email)).headOption
      if (key.isDefined) {
        map(key.get) += email
        map
      } else {
        val set = new mutable.HashSet[Email]()
        set += email
        map + (email -> set)
      }
    })

    res.mapValues(_.toSet).values.toList
  }
  
  def main(args: Array[String]) {
    val emails = readInput()
    val grouped = groupBySimilarity(emails, isSimilar)
    grouped.foreach(g => println(g.mkString(" ")))
  }

}

object Solution {

  def readInput(): Array[Int] = {
    val sc = new java.util.Scanner(System.in)
    val n = sc.nextInt
    val array = new Array[Int](n)
    for (i <- 0 until n) {
      array(i) = sc.nextInt
    }

    array
  }

  def rearrange(array: Array[Int]): Int = {
    var z = array.length - 1
    var i = 0

    def swap(array: Array[Int], left: Int, right: Int) = {
      if (left < right && array(left) == 0) {
        array(left) = array(right)
        array(right) = 0
      }
    }

    def findRightMostNonZero(array: Array[Int], right: Int): Int = {
      var r = right
      while (r >= 0 && array(r) == 0) r -= 1
      r
    }
    
    while (i <= z) {
      if (array(i) == 0) {
        z = findRightMostNonZero(array, z)
        swap(array, i, z)
      } 
      
      if (i <= z) i += 1
    }
    
    i
  }

  def main(args: Array[String]) {
    val array = readInput()

    println(rearrange(array))
    println(array.mkString(" "))
  }

}

object Solution {

  def readInput(): String = {
    val sc = new java.util.Scanner(System.in)
    sc.next
  }

  def getDerangements(str: String): List[String] = {
    def getIndex(str: String): Set[(Char, Int)] = {
      str.zipWithIndex.toSet
    }

    def permutate(ch: Char, str: String): List[String] = {
      (for (i <- 0 to str.length) yield {
        val (first, second) = str.splitAt(i)
        first + ch + second
      }).toList
    }

    def permutations(s: String): List[String] = {
      if (s.isEmpty) Nil
      else {
        val ch = s.head
        val rest = s.tail
        permutations(rest) match {
          case Nil => List(ch.toString)
          case d: List[String] => d.flatMap(permutate(ch, _))
        
        }
      }
    }

    def isDerangement(s: String, index: Set[(Char, Int)]): Boolean = {
      val ind = getIndex(s)
      !(ind & index).isEmpty
    }
    
    val index = getIndex(str)

    permutations(str).filter(!isDerangement(_, index)).toSet.toList
   
  }

  def main(args: Array[String]) {
    val str = readInput()
    getDerangements(str).foreach(println(_))
  }

}

object Solution {

  case class Meeting(start: Long, end: Long, weight: Int) extends Ordered[Meeting] {
    def isOvelappedBy(meeting: Meeting) = {
      val (min, max) = if (this <= meeting) (this, meeting) else (meeting, this)
      (min.end > max.start && min.end < max.end) || (min.end >= max.end)
    }

    override def compare(that: Meeting) = Meeting.ordering.compare(this, that)
  }

  object Meeting {
    def parse(sc: java.util.Scanner) = Meeting(sc.next().toLong, sc.next().toLong, sc.nextInt())

    implicit val ordering: Ordering[Meeting] = Ordering.by(_.start)
  }

  def readInput(): List[Meeting] = {

    val sc = new java.util.Scanner(System.in)
    val n = sc.nextInt
    val meetings = collection.mutable.ListBuffer.empty[Meeting]
    for (i <- 0 until n) meetings += Meeting.parse(sc)
    meetings.toList
  }

  def schedule(meetings: List[Meeting]): Int = {
    val sorted = meetings.sorted
    

    def partitionOverlappings(meeting: Meeting, meetings: List[Meeting]): (List[Meeting], List[Meeting]) = {
      (meetings.filter(meeting.isOvelappedBy(_)), meetings.filter(!meeting.isOvelappedBy(_)))
    }

    def scheduleHelper(meetings: List[Meeting], weight: Int): Int = {
      meetings match {
        case meeting::rest => {
          val (overlappings, notOverlappings) = partitionOverlappings(meeting, meetings)
          math.max(
            scheduleHelper(notOverlappings, weight + meeting.weight),
            overlappings.map(o => scheduleHelper(rest, weight)).max
            )
        }

        case _ => weight
      }
    }

    scheduleHelper(meetings, 0)

  }

  def main(args: Array[String]) {
    val meetings = readInput
    println(schedule(meetings))
  }
}