mighty friend

 This problem was a good one according to me and test many concepts, that you have in your bucket of skills, overall it was a medium level problem, you can try first by looking the Problem Statement and think about how you can approach this problem. Try to solve by making assumptions and making sample test cases of your own, it helps a lot. Before coding, understand the problem and decide your approach that you are going to use.

The explanation of the problem is below the Statement.

Problem Statement:-

Motu and Tomu are very good friends who are always looking for new games to play against each other and ways to win these games. One day, they decided to play a new type of game with the following rules:

• The game is played on a sequence ${�}_0,{�}_1,\dots ,{�}_{�-1}$.
• The players alternate turns; Motu plays first, since he's earlier in lexicographical order.
• Each player has a score. The initial scores of both players are $0$.
• On his turn, the current player has to pick the element of $�$ with the lowest index, add its value to his score and delete that element from the sequence $�$.
• At the end of the game (when $�$ is empty), Tomu wins if he has strictly greater score than Motu. Otherwise, Motu wins the game.

In other words, Motu starts by selecting ${�}_0$, adding it to his score and then deleting it; then, Tomu selects ${�}_1$, adds its value to his score and deletes it, and so on.

Motu and Tomu already chose a sequence $�$ for this game. However, since Tomu plays second, he is given a different advantage: before the game, he is allowed to perform at most $�$ swaps in $�$; afterwards, the two friends are going to play the game on this modified sequence.

Now, Tomu wants you to determine if it is possible to perform up to $�$ swaps in such a way that he can win this game.

Input

• The first line of the input contains a single integer $�$ denoting the number of test cases. The description of $�$ test cases follows.
• The first line of each test case contains two space-separated integers $�$ and $�$ denoting the number of elements in the sequence and the maximum number of swaps Tomu can perform.
• The second line contains $�$ space-separated integers ${�}_0,{�}_1,\dots ,{�}_{�-1}$.

Output

For each test case, print a single line containing the string "YES" if Tomu can win the game or "NO" otherwise (without quotes).

Constraints

• $1\le �\le 100$
• $1\le �\le 10,000$
• $0\le �\le 10,000$
• $1\le {�}_{�}\le 10,000$ for each valid $�$

Subtasks

Subtask #1 (20 points): $1\le �\le 100$

Subtask #2 (80 points): original constraints

Sample 1:

Input

Output

2
6 0
1 1 1 1 1 1
5 1
2 4 6 3 4

NO
YES

Explanation:

Example case 1: At the end of the game, both Motu and Tomu will have scores $1+1+1=3$. Tomu is unable to win that game, so the output is "NO".

Example case 2: If no swaps were performed, Motu's score would be $2+6+4=12$ and Tomu's score would be $4+3=7$. However, Tomu can swap the elements ${�}_2=6$ and ${�}_3=3$, which makes Motu's score at the end of the game equal to $2+3+4=9$ and Tomu's score equal to $4+6=10$. Tomu managed to score higher than Motu, so the output is "YES".

Explanation:-

So, this problem took quite a lot of thinking, but today I passed all the TC's in one go. So, I think I can easily explain this.

Basically, ignore the game stuff and all, and come to the main part that is, Tom needs to win, and he can win only if he has greater score than Mot. Now... firstly you should understand that, we need to first separate the values that they both have got into 2 arrays, bcz in a single array comparing values would be a headache, maybe we can do that but it's just not required bcz of the contraints, so DON'T GO FOR IT'. Now we get the values that they got, as 2 separate arrays.

Firstly, let's find their scores, and if tom is having greater, then he wins just continue for the next Test Case, otherwise move forward.

The second condition says that if Tom is not winning and we have k=0, that means we cannot make any swaps so, he cannot win at all, just print no and continue.

Lastly, we will check if Tom can make swaps to get his score higher than that of Mot.

Just iterate through the values of Tom, and compare the first val with the last one of Mot and so on, we just find the difference between these values and we can understand that this value will be decreased from Mot score and added to Tom score, not to mention that we will do this only when the value of Tom is less than that of Mot, otherwise just ignore...

After every change in the scores check if Tom's score is greater than that of Mot, if yes then print and break out of loop, so the else block won't get executed, and the last condition will also be false. The first condition in the For loop will break the loop when we will make k number of swaps, and so we are saying that nada is True, means, we got nothing. So after the break the last condition will be true and will print No to the output.

That's if for this one, I took this problem Yesterday and couldn't pass some Test Cases and today I used the Ballmer Peak Method and maybe that helped me, xd.

Peace Out!

Code Implementation:-

from math import fsum

for _ in range(int(input())):

    n,k=map(int,input().split())

    nums=list(map(int,input().split()))

    mot,tom=[],[]

    for i,val in enumerate(nums):

        if(i%2==0):

            mot.append(val)

        else:

            tom.append(val)

    tom.sort()

    mot.sort()

    mot_score1=fsum(mot)

    tom_score1=fsum(tom)

    diff=tom_score1-mot_score1

    if(diff>0):

        print("YES")

        continue

    diff=abs(diff)

    # If k is 0 then tom cannot win at any scenarion

    if(k==0):

        print("NO")

        continue

    # At this point, tom may win which will be seen after iterating through his score

    # If we get out of the loop with nada as True, then this means that we didn't

# get a YES, so we will print NO after the loop

    nada=False

    for i in range(len(tom)):

        if(i==k):

            nada=True

            break

        t=tom[i]

        m=mot[len(mot)-1-i]

        if(t<m):

            d=m-t

            tom_score1+=d

            mot_score1-=d

            if(tom_score1>mot_score1):

                print("YES")

                break

    else:

        print("NO")

    if(nada==True):

        print("NO")