[Solution] Median Sort Solution Code Jam 2021

Median Sort Solution Codejam 2021

Problem

You want to sort NN distinct items, x1,x2,…,xNx1,x2,…,xN. Unfortunately, you do not have a way of comparing two of these items. You only have a way to, given three of them, find out which one is the median, that is, which one is neither the minimum nor the maximum among the three.

For example, suppose N=5N=5 and you know that:

x1x1 is the median of {x1,x2,x3}{x1,x2,x3}
x2x2 is the median of {x2,x3,x4}{x2,x3,x4}
x3x3 is the median of {x3,x4,x5}{x3,x4,x5}

Median sort solution codejam 2021

Then, it is guaranteed that the sorted order of the elements is either x4,x2,x1,x3,x5x4,x2,x1,x3,x5 or its reverse x5,x3,x1,x2,x4x5,x3,x1,x2,x4. Notice that by knowing only medians, it is impossible to distinguish the order of any list from its reverse, since the median question has the same result for any three elements in both cases.

Your program will have to find the order of TT lists of NN elements using at most QQ median questions in total (or Q/TQ/T queries per list on average). In each case, finding either the right order or its reverse is considered correct. The order for each case is generated uniformly at random from all possible orders, and independently of any other information.

Input and output

Initially, the judge will send you a single line containing three integers TT, NN, and QQ: the number of test cases, the number of elements to sort within each test case, and the total number of questions you are allowed across all test cases, respectively. Then, you must process TT test cases. Each test case consists of a series of question exchanges plus an additional exchange to provide the answer.

For a question exchange, your program must print a single line containing three distinct integers i,j,ki,j,k all between 11 and NN, inclusive, which corresponds to asking the judge “which element is the median of the set {xi,xj,xk}{xi,xj,xk}?” The judge will respond with a single line containing a single integer LL, meaning that the median of that set is xLxL (LL is always equal to one of ii, jj, or kk). If you try to perform a (Q+1)(Q+1)-th question exchange, the judge will simply output -1.

Once you are ready to state the result, print a line containing NN integers representing the indices of the elements in sorted or reverse sorted order. The judge will respond with a single integer 1 if your answer is correct or -1 if it is not. After receiving the judge’s answer for the TT-th case, your program must finish in time in order to not receive a Time Limit Exceeded error. In addition, if you print additional information after receiving the result for the TT-th case, you will get a Wrong Answer judgment.

If the judge receives an invalidly formatted line or invalid values from your program at any moment, the judge will print a single number -1. After the judge prints -1 for any of the reasons explained above, it will not print any further output. If your program continues to wait for the judge after receiving a -1, your program will time out, resulting in a Time Limit Exceeded error. Notice that it is your responsibility to have your program exit in time to receive a Wrong Answer judgment instead of a Time Limit Exceeded error. As usual, if the memory limit is exceeded, or your program gets a runtime error, you will receive the appropriate judgment.

Limits

Time limit: 40 seconds.
Memory limit: 1 GB.
T=100T=100.

Test Set 1 (Visible Verdict)

N=10N=10.
Q=300⋅TQ=300⋅T. Median sort solution codejam 2021

Test Set 2 (Visible Verdict)

N=50N=50.
Q=300⋅TQ=300⋅T.

Test Set 3 (Hidden Verdict)

N=50N=50.
Q=170⋅TQ=170⋅T.

You can use this testing tool to test locally or on our platform. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. For more information, read the instructions in comments in that file, and also check out the Interactive Problems section of the FAQ.

Instructions for the testing tool are included in comments within the tool. We encourage you to add your own test cases. Please be advised that although the testing tool is intended to simulate the judging system, it is NOT the real judging system and might behave differently. If your code passes the testing tool but fails the real judge, please check the Coding section of the FAQ to make sure that you are using the same compiler as us.

2 5 600

Judge provides TT, NN, QQ

Case 1

1 2 3

Solution asks for the median of {x1,x2,x3}{x1,x2,x3}

Judge responds that the median is x2x2

4 2 3

Solution asks for the median of {x4,x2,x3}{x4,x2,x3}

Judge responds that the median is x3x3

5 4 3

Solution asks for the median of {x5,x4,x3}{x5,x4,x3}

Judge responds that the median is x4x4

5 4 3 2 1

Solution outputs the sorted list

Judge confirms that the answer is correct

Case 2

1 2 3

Solution asks for the median of {x1,x2,x3}{x1,x2,x3}

Judge responds that the median is x3x3

2 3 4

Solution asks for the median of {x2,x3,x4}{x2,x3,x4}

Judge responds that the median is x4x4

3 4 5

Solution asks for the median of {x3,x4,x5}{x3,x4,x5}

Judge responds that the median is x5x5

1 3 5 4 2

Solution outputs the sorted list

Judge confirms that the answer is correct

Solution:

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main()
{
ll t,n,q;
cin>>t>>n>>q;
while(t– !=0){
vector<ll> a;

cout<<“1 2 3″<<endl;

ll size=3;
ll p;
cin>>p;
if(p==2){
a.push_back(1);
a.push_back(2);
a.push_back(3);

}
else if(p==3){
a.push_back(1);
a.push_back(3);
a.push_back(2);
}
else{
a.push_back(2);
a.push_back(1);
a.push_back(3);
}
for(ll i=4;i<=(n);i++){
ll u=0;
ll v=size-1;
while(u<v){
ll mid=u+((v-u)/2);
cout<<a[mid]<<” “<<a[mid+1]<<” “<<(i)<<endl;
cin>>p;
if(p==a[mid]){
v=mid;
}
else if(p==a[mid+1]){

u=mid+1;
}
else{
a.insert(a.begin()+mid+1,i);
size++;
break;
}
}
if(size!=i){
if(u==0){
a.insert(a.begin(),i);
}
else{
a.push_back(i);
}
size++;
}
}
for(auto zzz: a){
cout<<zzz<<” “;
}
cout<<endl;
cin>>p;
if(p==-1){
break;
}
}
}