Inversions Retrieval CodeChef Solution


Inversions Retrieval CodeChef Solution

Inversions Retrieval CodeChef Solution

There is a hidden vector FF, which initially has NN values F0,F1,,FN1F0,F1,…,FN−1, which are a permutation of {0,1,,N1}{0,1,…,N−1}. You want to find the number of inversions in FF, that is, the number of pairs (i,j)(i,j) with 0i<jN10≤i<j≤N−1 and Fi>FjFi>Fj.

By calling some functions defined later, you can append some values to the end of FF. Say, currently F=[F0,F1,,Fk1]F=[F0,F1,…,Fk−1]At any instant, any value in FF must be in the range [0,109][0,109], otherwise you get a wrong answer verdict. You can call the following functions, each of which appends some value to FF:

  • put ii: This function appends ii to the end of FF.
  • compose ii (0i<k,0Fi<k0≤i<k,0≤Fi<k) : This function appends FFiFFi to the end of FF.
  • add ii jj (0i,j<k0≤i,j<k) : This function appends Fi+FjFi+Fj to the end of FF.
  • subtract ii jj (0i,j<k0≤i,j<k) : This function appends FiFjFi−Fj to the end of FF.
  • multiply ii jj (0i,j<k0≤i,j<k) : This function appends Fi×FjFi×Fj to the end of FF.
  • xor ii jj (0i,j<k0≤i,j<k) : This function appends FiFjFi⊕Fj to the end of FF, where  denotes the bitwise exclusive-or operator.
  • compare ii jj (0i,j<k0≤i,j<k) : This function appends 11 to the end of FF, if Fi<FjFi<Fj and 00 otherwise.

You are only given the value of NN. You need to make at most 106106 function calls such that in the end, the last value in FF contains the number of inversions in the original permutation, i.e, the number of inversions in [F0,F1,,FN1][F0,F1,…,FN−1].

Note that to get the points for a subtask, your output for that subtask should be able to provide the correct answer for every possible permutation of {0,1,,N1}{0,1,…,N−1} that satisfies the constraints of that subtask. See the explanation of the sample provided below for an example.

Input Format

  • Each test case consists of two lines of input.
  • The first line of the input will contain a single integer NN, denoting the size of the hidden permutation.
  • The second line of the input will contain a single integer with the value 11 if the test case belongs to subtask 11 and 00 otherwise.

Inversions Retrieval CodeChef Solution

Output Format

  • In the first line, output the number of function calls you to want to make. This number should not exceed 106106.
  • In each of the following lines, output the function call as described in the problem statement.




  • Subtask 1 (25 points):
    • N7000N≤7000
    • There exist at most two indices 0i<N0≤i<N with FiiFi≠i.
  • Subtask 2 (4 points): N1000N≤1000.
  • Subtask 3 (13 points): N1400N≤1400.
  • Subtask 4 (27 points): N4000N≤4000.
  • Subtask 5 (16 points): N5000N≤5000.
  • Subtask 6 (9 points): N6000N≤6000.
  • Subtask 7 (4 points): N6500N≤6500.
  • Subtask 8 (2 points): N7000N≤7000.

Sample Input 1 


Sample Output 1 

put 1
multiply 0 2


Inversions Retrieval CodeChef Solution

In the beginning, the vector is [F0,F1][F0,F1]. After the first call, it would be [F0,F1,1][F0,F1,1]. After the second call, it would be [F0,F1,1,F0][F0,F1,1,F0]. So, if the original vector was [0,1][0,1] the final value would be 00 and if the original vector was [1,0][1,0], the final value would be 11.

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here ScishowEngineer   Then Follow US HERE and Join Telegram.

If You Want To Learn Something New Then Visit Our Official Channel YOUTUBE

Related Posts

Leave a Reply

Your email address will not be published.