Generating solutions to unanticipated problems is the second nature of human intelligence – the product of experience-fueled critical thinking. The machine learning community has made tremendous progress in generating and analyzing textual information, however, advances in problem-solving are still largely limited to relatively basic math and programming problems or retrieving and replicating already existing solutions. AlphaCode is a system that writes computer programs at a competitive level, as part of DeepMind’s mission to solve intelligence. It has been ranked in the top 54% of programming contests by solving new challenges that require a mix of critical thinking, logic, algorithms, coding, and natural language understanding.

Example of problem-solving using an AlphaCode model

Problem

# RATING: 1200⤶
# TAGS: sortings⤶
# LANGUAGE IS python3⤶
# CORRECT SOLUTION⤶
# It is the easy version of the problem. The only difference is that in this⤶
# version n = 1.⤶
# ⤶
# In the cinema seats can be represented as the table with n rows and m columns.⤶
# The rows are numbered with integers from 1 to n. The seats in each row are⤶
# numbered with consecutive integers from left to right: in the k-th row from m⤶
# (k - 1) + 1 to m k for all rows 1 ≤ k ≤ n.⤶
# ⤶
# 1| 2| ⋅⋅⋅| m - 1| m⤶
# ---|---|---|---|---⤶
# m + 1| m + 2| ⋅⋅⋅| 2 m - 1| 2 m⤶
# 2m + 1| 2m + 2| ⋅⋅⋅| 3 m - 1| 3 m⤶
# \vdots| \vdots| \ddots| \vdots| \vdots⤶
# m (n - 1) + 1| m (n - 1) + 2| ⋅⋅⋅| n m - 1| n m⤶
# The table with seats indices⤶
# ⤶
# There are nm people who want to go to the cinema to watch a new film. They are⤶
# numbered with integers from 1 to nm. You should give exactly one seat to each⤶
# person.⤶
# ⤶
# It is known, that in this cinema as lower seat index you have as better you⤶
# can see everything happening on the screen. i-th person has the level of sight⤶
# a_i. Let's define s_i as the seat index, that will be given to i-th person.⤶
# You want to give better places for people with lower sight levels, so for any⤶
# two people i, j such that a_i < a_j it should be satisfied that s_i < s_j.⤶
# ⤶
# After you will give seats to all people they will start coming to their seats.⤶
# In the order from 1 to nm, each person will enter the hall and sit in their⤶
# seat. To get to their place, the person will go to their seat's row and start⤶
# moving from the first seat in this row to theirs from left to right. While⤶
# moving some places will be free, some will be occupied with people already⤶
# seated. The inconvenience of the person is equal to the number of occupied⤶
# seats he or she will go through.⤶
# ⤶
# Let's consider an example: m = 5, the person has the seat 4 in the first row,⤶
# the seats 1, 3, 5 in the first row are already occupied, the seats 2 and 4 are⤶
# free. The inconvenience of this person will be 2, because he will go through⤶
# occupied seats 1 and 3.⤶
# ⤶
# Find the minimal total inconvenience (the sum of inconveniences of all⤶
# people), that is possible to have by giving places for all people (all⤶
# conditions should be satisfied).⤶
# ⤶
# Input⤶
# ⤶
# The input consists of multiple test cases. The first line contains a single⤶
# integer t (1 ≤ t ≤ 100) — the number of test cases. Description of the test⤶
# cases follows.⤶
# ⤶
# The first line of each test case contains two integers n and m (n = 1, 1 ≤ m ≤⤶
# 300) — the number of rows and places in each row respectively.⤶
# ⤶
# The second line of each test case contains n ⋅ m integers a_1, a_2, ..., a_{n ⋅⤶
# m} (1 ≤ a_i ≤ 10^9), where a_i is the sight level of i-th person.⤶
# ⤶
# It's guaranteed that the sum of n ⋅ m over all test cases does not exceed⤶
# 10^5.⤶
# ⤶
# Output⤶
# ⤶
# For each test case print a single integer — the minimal total inconvenience⤶
# that can be achieved.⤶
# ⤶
# Example⤶
# ⤶
# Input⤶
# ⤶
# ⤶
# 4⤶
# 1 3⤶
# 1 2 3⤶
# 1 5⤶
# 2 1 5 3 3⤶
# 1 2⤶
# 2 1⤶
# 1 6⤶
# 2 3 2 1 1 1⤶
# ⤶
# ⤶
# Output⤶
# ⤶
# ⤶
# 3⤶
# 6⤶
# 0⤶
# 1⤶
# ⤶
# Note⤶
# ⤶
# In the first test case, there is a single way to arrange people, because all⤶
# sight levels are distinct. The first person will sit on the first seat, the⤶
# second person will sit on the second place, the third person will sit on the⤶
# third place. So inconvenience of the first person will be 0, inconvenience of⤶
# the second person will be 1 and inconvenience of the third person will be 2.⤶
# The total inconvenience is 0 + 1 + 2 = 3.⤶
# ⤶
# In the second test case, people should sit as follows: s_1 = 2, s_2 = 1, s_3 =⤶
# 5, s_4 = 4, s_5 = 3. The total inconvenience will⤶

Solution