Ramen (RMI contest)
Time limit: 1.5 seconds | Memory limit: 512 MB | Task type: interactive
Algorithms: greedy, permutation, optimization, interactive, sorting

# Problem Ramen

| Input file  | stdin  |
|-------------|--------|
| Output file | stdout |

There are $N$ friends $F_0, ..., F_{N-1}$ and $N$ types of ramen $R_0, ..., R_{N-1}$ at the ramen restaurant.
Each friend $F_i$ has a certain affinity $A_{ij}$ for ramen type $j$ — the greater the affinity, the more friend $F_i$ likes ramen $R_j$. The affinities of each friend are distinct — i.e., $A_{ij} \ne A_{ij'}$ for $j \ne j'$. Of course, it is possible that $A_{ij} < 0$.

Suppose the friends visit the ramen restaurant multiple times. During each visit, no two friends can eat the same type of ramen (the supply would be insufficient). Suppose that the friends take their ramen in order $F_{\pi_0}, \dots, F_{\pi_{N-1}}$, for some permutation $\pi_0, \dots, \pi_{N-1}$ of $0, \dots, N-1$. Then, friend $F_{\pi_0}$ will take their favorite ramen (i.e., the one for which they have the highest affinity), friend $F_{\pi_1}$ will take their favorite ramen *except the one taken by* $F_{\pi_0}$, and so on. In other words, $F_{\pi_i}$ will take their favourite ramen among those not taken by $F_{\pi_0}, \dots, F_{\pi_{i-1}}$.

The *goodness* of a certain permutation $\pi$ is the sum of the affinities of the friends for the types of ramen they take. In other words, if friend $i$ takes ramen of type $\sigma(i)$, then the goodness of $\pi$ is given by $\sum_{i=0}^{N-1} A_{i, \sigma(i)}$.

Your goal is to find a permutation $\pi$ with maximum goodness. You can do this by experimenting with different orders in which the friends take their ramen (i.e., different visits to the restaurant). The goal is to find an optimal permutation without needing too many visits to the restaurant.

## Interaction protocol

You have to implement the following function:

```cpp
std::vector<int> find_order(int N);
```

Here, $N$ is the number of friends. The function should return a permutation $\pi$ of $0, \dots, N - 1$ with maximum goodness. To implement it, you may repeatedly call the following function at most 750 times:

```cpp
std::vector<std::pair<int, int>> query(const std::vector<int>& order);
```

The function takes as input a permutation $\pi$ of $0, \dots, N - 1$ (denoted by the parameter `order`) and returns a list of pairs $(\sigma(i), A_{i,\sigma(i)})$, where $\sigma(i)$ is the type of ramen that friend $i$ takes if the friends take their ramen in the order given by $\pi$.

## Restrictions

*   $1 \le N \le 75$
*   $|A_{ij}| \le 2\,000\,000$
*   The model solution of the scientific committee requires at most $cN^k$ queries for some constants $c, k \ge 1$. To not overburden the testing infrastructure, you may call `query` at most 750 times, which generously reflects the practical performance of the model solution.

| #   | Points | Restrictions |
| --- | ------ | ------------ |
| 1   | 5      | $N = 5$      |
| 2   | 15     | $N = 15$     |
| 3   | 20     | $N = 30$     |
| 4   | 20     | $N = 45$     |
| 5   | 20     | $N = 60$     |
| 6   | 20     | $N = 75$     |

## Examples

| Competitor behaviour          | Committee behaviour  |
|-------------------------------|----------------------|
|                               | Calls `find_order(2)`. |
| `query({0, 1})`                 |                      |
|                               | `{{0, 9}, {1, 0}}`     |
| `query({1, 0})`                 |                      |
|                               | `{{1, 5}, {0, 5}}`     |
| `find_order(2)` returns `{1, 0}`. |                      |

In this example, there are $N = 2$ friends, with the following affinities $A_{i,j}$ for the $N = 2$ types of ramen:

| A   | 0   | 1   |
| --- | --- | --- |
| 0   | 9   | 5   |
| 1   | 5   | 0   |

The interaction begins with the committee calling your function: `find_order(2)`. Your function then queries the two possible permutations: `{0, 1}` and `{1, 0}`. The former achieves a goodness of 9, while the latter achieves a goodness of 10. The function then returns the better of the two, which is `{1, 0}`. The returned permutation has the maximum possible goodness, as required.

Starter code:
ramen.h: #include <cstdio>
#include <cassert>
#include <cstdlib>
#include <vector>

std::vector<int> find_order(int N);

std::vector<std::pair<int, int>> query(const std::vector<int>& order) {
    printf("?");
    for (int i = 0; i < (int)order.size(); i++) {
        printf(" %d", order[i]);
    }
    printf("\n");
    fflush(stdout);
    int len;
    assert(scanf("%d", &len) == 1);
    std::vector<std::pair<int, int>> assignments(len);
    for (int i = 0; i < len; i++) {
        assert(scanf("%d %d", &assignments[i].first, &assignments[i].second) == 2);
    }
    return assignments;
}

int main() {
    int N;
    scanf("%d", &N);
    std::vector<int> pi = find_order(N);
    printf("!");
    for (int i = 0; i < (int)pi.size(); i++) {
        printf(" %d", pi[i]);
    }
    printf("\n");
    fflush(stdout);
    return 0; 
}

interactor.cpp: #include "testlib.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>

using namespace std;

const int INF = 2000000001;
int N; 
int MAX_QUERIES;
vector<vector<int>> affinities;
int queryCount = 0;

bool isValidPermutation(const vector<int>& perm) {
    if ((int)perm.size() != N) return false;
    
    vector<bool> used(N, false);
    for (int x : perm) {
        if (x < 0 || x >= N || used[x]) return false;
        used[x] = true;
    }
    return true;
}

vector<pair<int, int>> processQuery(const vector<int>& order) {
    vector<bool> takenRamen(N, false);
    vector<pair<int, int>> result(N);
    
    for (int i : order) {
        int bestRamen = -1;
        int bestAffinity = -INF;
        
        for (int j = 0; j < N; j++) {
            if (!takenRamen[j] && affinities[i][j] > bestAffinity) {
                bestRamen = j;
                bestAffinity = affinities[i][j];
            }
        }
        
        takenRamen[bestRamen] = true;
        result[i] = {bestRamen, bestAffinity};
    }
    
    return result;
}

int calculateGoodness(const vector<pair<int, int>>& assignments) {
    int goodness = 0;
    for (const auto& p : assignments) {
        goodness += p.second;
    }
    return goodness;
}

int main(int argc, char* argv[]) {
    registerInteraction(argc, argv);
    
    N = inf.readInt();
    MAX_QUERIES = inf.readInt(); 
    int optimalGoodness = inf.readInt();
    
    affinities.resize(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            affinities[i][j] = inf.readInt();
        }
    }
    
    for (int i = 0; i < N; i++) {
        vector<int> values = affinities[i];
        sort(values.begin(), values.end());
        for (int j = 1; j < N; j++) {
            if (values[j] == values[j-1]) {
                quitf(_fail, "Affinities for friend %d are not distinct", i);
            }
        }
    }
    
    cout << N << "\n";
    cout.flush();
    
    while (true) {
        string command = ouf.readToken();
        
        if (command == "?") {
            if (++queryCount > MAX_QUERIES) {
                quitf(_wa, "Too many queries: %d (limit: %d)", queryCount, MAX_QUERIES);
            }
            
            vector<int> order(N);
            for (int i = 0; i < N; i++) {
                order[i] = ouf.readInt(0, N - 1);
            }
            
            if (!isValidPermutation(order)) {
                quitf(_wa, "Invalid permutation in query");
            }
            
            vector<pair<int, int>> assignments = processQuery(order);
            
            cout << assignments.size() << "\n";
            for (const auto& p : assignments) {
                cout << p.first << " " << p.second << "\n";
            }
            cout.flush();
        }
        else if (command == "!") {
            vector<int> finalOrder(N);
            for (int i = 0; i < N; i++) {
                finalOrder[i] = ouf.readInt(0, N - 1);
            }
            
            if (!isValidPermutation(finalOrder)) {
                quitf(_wa, "Final answer is not a valid permutation");
            }
            
            vector<pair<int, int>> finalAssignments = processQuery(finalOrder);
            int finalGoodness = calculateGoodness(finalAssignments);
            
            if (finalGoodness < optimalGoodness) {
                quitf(_wa, "Final answer with goodness %d is worse than optimal goodness %d", 
                      finalGoodness, optimalGoodness);
            }
            
            quitf(_ok, "Correct! Goodness: %d, Queries used: %d", 
                  finalGoodness, queryCount);
        }
        else {
            quitf(_pe, "Unknown command: %s", command.c_str());
        }
    }
    
    return 0;
}


Grader code:
ramen.h: #include <cstdio>
#include <cassert>
#include <cstdlib>
#include <vector>

std::vector<int> find_order(int N);

std::vector<std::pair<int, int>> query(const std::vector<int>& order) {
    printf("?");
    for (int i = 0; i < (int)order.size(); i++) {
        printf(" %d", order[i]);
    }
    printf("\n");
    fflush(stdout);
    int len;
    assert(scanf("%d", &len) == 1);
    std::vector<std::pair<int, int>> assignments(len);
    for (int i = 0; i < len; i++) {
        assert(scanf("%d %d", &assignments[i].first, &assignments[i].second) == 2);
    }
    return assignments;
}

int main() {
    int N;
    scanf("%d", &N);
    std::vector<int> pi = find_order(N);
    printf("!");
    for (int i = 0; i < (int)pi.size(); i++) {
        printf(" %d", pi[i]);
    }
    printf("\n");
    fflush(stdout);
    return 0; 
}

interactor.cpp: #include "testlib.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>

using namespace std;

const int INF = 2000000001;
int N; 
int MAX_QUERIES;
vector<vector<int>> affinities;
int queryCount = 0;

bool isValidPermutation(const vector<int>& perm) {
    if ((int)perm.size() != N) return false;
    
    vector<bool> used(N, false);
    for (int x : perm) {
        if (x < 0 || x >= N || used[x]) return false;
        used[x] = true;
    }
    return true;
}

vector<pair<int, int>> processQuery(const vector<int>& order) {
    vector<bool> takenRamen(N, false);
    vector<pair<int, int>> result(N);
    
    for (int i : order) {
        int bestRamen = -1;
        int bestAffinity = -INF;
        
        for (int j = 0; j < N; j++) {
            if (!takenRamen[j] && affinities[i][j] > bestAffinity) {
                bestRamen = j;
                bestAffinity = affinities[i][j];
            }
        }
        
        takenRamen[bestRamen] = true;
        result[i] = {bestRamen, bestAffinity};
    }
    
    return result;
}

int calculateGoodness(const vector<pair<int, int>>& assignments) {
    int goodness = 0;
    for (const auto& p : assignments) {
        goodness += p.second;
    }
    return goodness;
}

int main(int argc, char* argv[]) {
    registerInteraction(argc, argv);
    
    N = inf.readInt();
    MAX_QUERIES = inf.readInt(); 
    int optimalGoodness = inf.readInt();
    
    affinities.resize(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            affinities[i][j] = inf.readInt();
        }
    }
    
    for (int i = 0; i < N; i++) {
        vector<int> values = affinities[i];
        sort(values.begin(), values.end());
        for (int j = 1; j < N; j++) {
            if (values[j] == values[j-1]) {
                quitf(_fail, "Affinities for friend %d are not distinct", i);
            }
        }
    }
    
    cout << N << "\n";
    cout.flush();
    
    while (true) {
        string command = ouf.readToken();
        
        if (command == "?") {
            if (++queryCount > MAX_QUERIES) {
                quitf(_wa, "Too many queries: %d (limit: %d)", queryCount, MAX_QUERIES);
            }
            
            vector<int> order(N);
            for (int i = 0; i < N; i++) {
                order[i] = ouf.readInt(0, N - 1);
            }
            
            if (!isValidPermutation(order)) {
                quitf(_wa, "Invalid permutation in query");
            }
            
            vector<pair<int, int>> assignments = processQuery(order);
            
            cout << assignments.size() << "\n";
            for (const auto& p : assignments) {
                cout << p.first << " " << p.second << "\n";
            }
            cout.flush();
        }
        else if (command == "!") {
            vector<int> finalOrder(N);
            for (int i = 0; i < N; i++) {
                finalOrder[i] = ouf.readInt(0, N - 1);
            }
            
            if (!isValidPermutation(finalOrder)) {
                quitf(_wa, "Final answer is not a valid permutation");
            }
            
            vector<pair<int, int>> finalAssignments = processQuery(finalOrder);
            int finalGoodness = calculateGoodness(finalAssignments);
            
            if (finalGoodness < optimalGoodness) {
                quitf(_wa, "Final answer with goodness %d is worse than optimal goodness %d", 
                      finalGoodness, optimalGoodness);
            }
            
            quitf(_ok, "Correct! Goodness: %d, Queries used: %d", 
                  finalGoodness, queryCount);
        }
        else {
            quitf(_pe, "Unknown command: %s", command.c_str());
        }
    }
    
    return 0;
}


Setup script:

Evaluation script: