All Tracks Algorithms Searching Binary Search Problem

Simple Game
Tag(s):

Algorithms, Binary Search, Data Structures, Easy-Medium, Sorting, approved

Problem
Editorial
Analytics

Monk and !Monk decided to play a simple number game. Each of them had a set of numbers (may contain a number more than once) to play with. Lets denote by $$A[]$$ the set belonging to Monk, and by $$B[]$$, the set belonging to !Monk.

They defined three functions $$f(x)$$ , $$g(x)$$ and $$V(x)$$ :

$$f(x)$$ : Returns count of numbers strictly smaller than $$x$$ in opponent's set

$$g(x)$$ : Returns count of numbers strictly greater than $$x$$ in opponent's set

$$V(x)$$ : $$f(x) \times g(x)$$

Score of a player is defined to be the $$ \sum_ {} V(x) $$ for each element $$x$$ present in the players set.

The player with $$higher$$ score wins the game.

Input:

  • The first line contains two positive integers N and M where N and M represent the number of elements present in Monk and !Monk's sets respectively.
  • The second line contains N space separated integers - elements present in Monk's set
  • The third line contains M space separated integers - elements present in !Monk's set

Output:

  • If Monk wins, print "Monk" (without quotes) followed by a space and the score difference between him and !Monk
  • If !Monk wins, print "!Monk" (without quotes) followed by a space and the score difference between him and Monk
  • If both players have equal scores, then print "Tie" (without quotes).

Constraints:

$$ 1 \le N,M \le 10^5 $$

$$ 0 \le A[i],B[i] \le 10^9 $$

SAMPLE INPUT
2 2
1 3
0 5
SAMPLE OUTPUT
Monk 2
Explanation

Monk's Set : {1,3}
!Monk's Set : {0,5}

Score of Monk :

    f(1) = 1,    There is one element {0}     
    f(3) = 1,    There is one element {0}

    g(1) = 1,    There is one element {5}
    g(3) = 1,    There is one element {5}

    Score = f(1) * g(1) + f(3) * g(3) = 1 + 1 = 2

Score of !Monk :

    f(0) = 0,    There are no elements smaller than 0 with Monk     
    f(5) = 2,    There are two elements {1,3}

    g(0) = 2,    There are two elements {1,3}
    g(5) = 0,    There are no elements greater than 5 with Monk

    Score = f(0) * g(0) + f(5) * g(5) = 0 + 0 = 0

Score of Monk > Score of !Monk
Difference = 2 - 0 = 2

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

ION

Challenge Name

ION Core Java Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications