Problem Sort

This problem just required 1 thing, that's implementation... this is what I had thought earlier and this took me 1 hour to understand that I was wrong with what I had to output in this Problem Statement, instead of just printing the Problem Indices, I took this to a different level and also found the Ranks of the Problems in 2 different ways, well, the problem seemed easy to the brim at last when I got my error but I just couldn't understand how I misunderstood the Statement. 

When you pass all the Test Cases in the first submission ;)

Well, go for the Problem on your own first and see if you get it in the first go, if you do...you are awesome!

Problem Statement:-

Chef is organising a contest with $�$ problems (numbered $1$ through $�$). Each problem has $�$ subtasks (numbered $1$ through $�$).

The difficulty of a problem can be calculated as follows:

• Let's denote the score of the $�$-th subtask of this problem by $�{�}_{�}$ and the number of contestants who solved it by $�{�}_{�}$.
• Consider the subtasks sorted in the order of increasing score.
• Calculate the number $�$ of valid indices $�$ such that $�{�}_{�}>�{�}_{�+1}$.
• For problem $�$, the difficulty is a pair of integers $(�,�)$.

You should sort the problems in the increasing order of difficulty levels. Since difficulty level is a pair, problem $�$ is more difficult than problem $�$ if the number $�$ is greater for problem $�$ than for problem $�$, or if $�>�$ and $�$ is the same for problems $�$ and $�$.

Input

• The first line of the input contains two space-separated integers $�$ and $�$ denoting the number of problems and the number of subtasks in each problem.
• $2�$ lines follow. For each valid $�$, the $2�-1$-th of these lines contains $�$ space-separated integers $�{�}_1,�{�}_2,\dots ,�{�}_{�}$ denoting the scores of the $�$-th problem's subtasks, and the $2�$-th of these lines contains $�$ space-separated integers $�{�}_1,�{�}_2,\dots ,�{�}_{�}$ denoting the number of contestants who solved the $�$-th problem's subtasks.

Output

Print $�$ lines containing one integer each — the indices of the problems in the increasing order of difficulty.

Constraints

• $1\le �\le 100,000$
• $2\le �\le 30$
• $1\le �{�}_{�}\le 100$ for each valid $�$
• $1\le �{�}_{�}\le 1,000$ for each valid $�$
• in each problem, the scores of all subtasks are unique

Subtasks

Subtask #1 (25 points): $�=2$

Subtask #2 (75 points): original constraints

Sample 1:

Input

Output

3 3
16 24 60
498 861 589
14 24 62
72 557 819
16 15 69
435 779 232

Code Implementation:-

p,s=map(int,input().split())

problems=[]

for p_no in range(1,p+1):

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

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

               

    # Will contain the current problem

    pr=sorted(list(zip(scores,subs)),key=lambda x:x[0])

    n=0

   

    for i in range(s-1):

        if(pr[i][1]>pr[i+1][1]):

            n+=1

   

    # At this point we will have the n with us, so we'll just put in with the Problem number

    problems.append( [p_no,n] )

   

# Now here I'll have problems list with p_no(problem nos.) associated to their n value

# Sorting on the basis of n value

problems.sort(key=lambda x:x[1])

for prob_number,n_value in problems:

    print(prob_number)

'''

Warning!!

Ignore the below code if you don't wanna get Confused

'''

''' In the below approach also I was calculating the ranks, but on a different basis, if the problems have same n value,so I was taking the problem that was the last(in the equal n value problems) as the next RankHolder

'''

# print(problems)

# ans=[0]*(p+1)

# ind=0

# rank=1

# last_changed=False

# while(ind<p-1):

#     if(problems[ind][1]!=problems[ind+1][1]):

#         ans[problems[ind][0]]=rank

#         rank+=1

#         ind+=1

#     else:

#         ''' Just for Debugging(below 2 lines) '''

#         # ind+=1

#         # print("Stucking HERE?")

       

#         # print("Next problem's rank is Equal!!")

#         # Will store the count of problems having the same n value

#         ct=1

#         temp_ind=ind

#         while(temp_ind<p-1 and problems[temp_ind][1]==problems[temp_ind+1][1]):

#             ct+=1

#             temp_ind+=1

#         # Here we will have the no. of problems that have the same n value, that is 'ct'

#         ct-=1

#         temp_rank=rank+ct

#         rank=temp_rank+1

#         ct+=1

#         # print(f'temp_rank is {temp_rank}')

#         while(ct>0):

#             # print(f"{problems[ind][0]} problem's rank is changed to {temp_rank}")

#             ans[problems[ind][0]]=temp_rank

#             if(ind==p-1):

#                 last_changed=True

#             temp_rank-=1

#             ct-=1

#             ind+=1

#         # ind=ind+ct+1

# if(last_changed!=True):

#     ans[p]=p

   

# # for elem in ans[1:]:

# for ind in range(1,len(ans)):

#     elem=ans[ind]

#     if(ind==p):

#         print(elem,end="")

#     else:

#         print(elem)

# print(*ans[1:],sep="\n")

''' The below code was the 1st Approach, my mistake was that I was thinking we have to output the Ranks of the Problem Statements, So I was getting the Ranks for the Problem Statements and then Outputting that

'''

# rank=1

# for ind,p_n,n_val in enumerate(problems[:-1]):

#     index=ind

#     if(problems[ind+1][1]!=n_val):

#         ans[p_n]=rank

#         rank+=1

#     else:

       

#         # Will have to handle equal n_vals

#         while(index)

       

# # print(ans)

# print(*ans[1:],sep="\n")

# print(t_scores)

# print(t_subs)

Explanation:-

So, this problem is just requiring you to have the implementation skills, firstly the input is a little bit tricky but you can do that if you are confident in the language that you are using. Secondly you just have to sort the problems on the basis of their scores and then get the count k, that tells the Difficulty level of a problem, if this count k is less then that means that the problem is difficult , so the difficulty of the problem will depend on this count k. Now, we just have to sort the problems on the basis of this count k and then get the indices( 1 based indexing here, don't confuse indices with the 0 based indices ) and output them in order. Like if there are 3 problems and the 1st Problem has the count as 1, 2nd Problem as 0 and 3rd Problem as 2, this means that the most easy problem is Problem 2 so output 2, then comes Problem 1 so output that and the lastly 3rd Problem so output 3.