C# – CodeForces – Table Tennis

The Table Tennis problem in CodeForces was looking actually easier than the Borya’s Diagnosis. However, I have decided to publish it, because I have managed to “lie or cheat” the CodeForces system with it in a cool way.

Currently, I am reading the Clean C++ book and sometimes, when you read about “clean” code the ideas to make a dirty solution is somehow really lucrative. Furthermore, in the clean book there are plenty of examples of what we should not do, thus I am getting really enthusiastic to try some of them.

So, a big disclaimer – DO NOT CODE LIKE THIS anywhere. But it was fun, because it passed all the tests of CodeForces – 43 in total and was granted with full points.

 

This is how the problem looks like:

n people are standing in a line to play table tennis. At first, the first two players in the line play a game. Then the loser goes to the end of the line, and the winner plays with the next person from the line, and so on. They play until someone wins k games in a row. This player becomes the winner.

For each of the participants, you know the power to play table tennis, and for all players these values are different. In a game the player with greater power always wins. Determine who will be the winner.

Input

The first line contains two integers: n and k (2 ≤ n ≤ 5002 ≤ k ≤ 1012) — the number of people and the number of wins.

The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ n) — powers of the player. It’s guaranteed that this line contains a valid permutation, i.e. all ai are distinct.

Output

Output a single integer — power of the winner.

So, what is the problem with this quite easy task? Well, first 10^12 is a big number and second, I needed some time to realize that there is a difference between the first player and everyone else. E.g., the first player needs to win N matches vs other players, the second player has to win one less, because he has obviously won his match with the first player (in order to be allowed to win). The second note is easily implemented, but for the first I did not want to use BigInteger, thus I have decided to build a small cheat – I have noticed that the n is up to 500, thus if more than 500 matches are required, the answer is simply the player with the biggest number for power. Thus, I have left integers everywhere and I have tried to embed it with try-catch. And it worked!

Here is the code:

Definitely not a clean code, but quite good enough to get what I was fighting for. Cheers!