Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Tyrion's Choice

By nasif379 · Limits 2s, 512 MB

"One stone crumbles and another takes its place and the temple holds its form for a thousand years or more. And that's what the Iron Bank is, a temple. We all live in its shadow and almost none of us know it. You can't run from them, you can't cheat them, you can't sway them with excuses. If you owe them money and you don't want to crumble yourself, you pay it back."―Tywin Lannister.

Tyrion remembers his father’s words as he faces an impending threat from the Iron Bank.

As the new Hand of the King, Tyrion has formed a small council named RUET (Regulatory Union of Empirical Territory) appointing Monkey D. Luffy as the Master of Ships overseeing the RUET Poribohon Shakha, Dr. House as the Grand Maester overseeing the RUET Medical, Wonder Woman as the Lady Commander of the Kingsguard that protects the new castle, LH of RUET, Masud Rana as the Master of Whisperers overseeing DSW (Directorate of Security and Welfare), Sanju as the Master of Arms overseeing the Labs of RUET and Nasif as the Master of Coins overseeing the RUET treasury. Since formation, the small council has been working towards rebuilding the new empire.

However, their peaceful daily life did not remain so for very long. Soon after the new empire was formed, the Iron Bank sent Jalanta Jalil to remind them of the huge debt the Crown owes them which was incurred by the previous Crown, Queen Cersei.

Nasif reminded Tyrion that they are in no position to repay the debt. So, Tyrion expressed his wishes to Jalil for more time to repay the debt on his name as a Lannister. It is a common saying about House Lannister that, "A Lannister always pays his debts". Jalil is well familiar with the saying but the House Lannister essentially had only one surviving member remaining. So, he wants to test Tyrion.

Jalil gives Tyrion and the small council three arrays AB and C. The arrays’ lengths are XY, and Z respectively. The arrays hold tokens of different sizes. In other words, each element of the arrays represents the size of a different token. The test rules are as followed:

  1. Tyrion has to choose exactly one token of size V from A.
  2. Luffy takes tokens from B. He can take all the tokens that are strictly smaller than V.
  3. Sanju takes tokens from C. He can take all the tokens that are strictly bigger than V.

Tyrion’s task is to maximize the number of total tokens they (Tyrion, Luffy and Sanju) can get following the rules. Can you help him find what is the maximum number of tokens they can get?


The input will be described in four lines.

In the first line, there will be 3 integers X, Y and Z, the lengths of the arrays A, B and C. The next line will hold X space-separated integers denoting the array A. The following line will hold Y space-separated integers denoting the array B. The last line will hold Z space-separated integers denoting the array C.

  • 1 ≤ X, Y, Z ≤ 100000
  • 1 ≤ A[i], B[j], C[k] ≤ 1000000000
  • 1 ≤ i ≤ X
  • 1 ≤ j ≤ Y
  • 1 ≤ k ≤ Z


Print a single integer P in a line, the maximum number of tokens Tyrion can get.


5 5 5
6 2 7 10 3
5 8 3 1 11
4 10 2 11 9
5 3 5
29329 293 89579 30505 71597
2438 51041 27681
91717 63335 9076 85871 20485

In the first case, Tyrion can choose the token of size 6 from the array A. Then, Luffy can choose tokens of size 1, 3, 5 from the array B and Sanju can choose tokens of size 9, 10, 11 from the array C. Thus the maximum number of tokens they can get is 7. Tyrion can also choose the token of size 7 from the array A and they can still get a maximum of 7 tokens. No other choice of Tyrion will yield a better solution.



    80% Solution Ratio

    fsshakkhorEarliest, Aug '19

    CoU_return0Fastest, 0.0s

    fire_tornadoLightest, 1.3 MB

    Daiyan_DahyShortest, 422B


    Login to submit


    Binary Search

    Toph uses cookies. By continuing you agree to our Cookie Policy.