twins (IATI junior)
Time limit: 0.5 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: bitmask, interactive, combinatorics, constructive, combinatorial search

# XV INTERNATIONAL ADVANCED TOURNAMENT IN INFORMATICS
## SHUMEN 2024

**Task 2. TWINS** ⏳0.5 s. 256 MB

Once again, the twins Reni and Nora managed to fool everybody by switching places. Alex was convinced that he had figured out a strategy for telling them apart. But it turns out he was wrong. Reni and Nora, knowing that he is hopelessly confused, decide to try one of their newly invented games. It consisted of the following:

They choose $N$ different pictures of themselves, numbered from 1 to $N$, one or two of which are of Reni and the rest are of Nora. Alex is allowed to ask questions like: "Among the pictures with numbers $p_1, p_2, ..., p_K$ ($1 \le K < N$), is there at least one picture of Reni?". However, to make it more interesting, he can submit a whole group with several such questions and receive the answers to each of them at the same time.

The purpose of the game for Alex is to guess which pictures are of Reni and which are of Nora after some finite number of questions (which in itself would be an achievement for him), but also to minimize both the number of question groups and the total number of questions in them. He needs your help for this. Write a program `twins` that finds the required one or two pictures.

## Task

Write a program `twins` that determines which of the pictures are of Reni and which are of Nora. It must contain the function `play` that will be compiled with the jury's program.

## Implementation details

Your function `play` must have the following format:

```cpp
std::vector<int> play (int N, int T);
```

It will be called only once during one execution of the program with two parameters: the number of pictures $N$ and the number of Reni's pictures - $T$ ($T \in \{1, 2\}$). The function should return the indices of the one or two Reni's pictures. Their order does not matter.

For communication with the jury's program you should use the following function:

```cpp
std::string guess (std::vector< std::vector<int> >& questions);
```

As a parameter, it receives a group of questions, each containing a set of picture numbers. For example, if Alex wants to ask 2 questions and the first one is about the pictures 1 and 2, and the second one is about the pictures 2 and 3, it should be given `{{1, 2}, {2, 3}}`. It is allowed to have "empty" questions that ask nothing (passing `{{ }, {2, 3} }` as a parameter). They **will not count** towards the total number of questions used.

The function returns a string composed of 0 and 1, indicating "no" and "yes" answers to the questions, respectively. Suppose you asked $M$ questions in a group. They are numbered with the numbers 0 through $M-1$ in the order in which you submitted them, and correspond to the indices of answers in the string.

You must submit to the system a file `twins.cpp` that contains the function `play`. It can also contain other code, functions, and global variables, but it must not contain the `main` function. Also, you should not read from the standard input or print to the standard output. Your program must include the header file `twins.h` by instruction to

![](_page_1_Picture_1.jpeg)

the preprocessor:

```cpp
#include "twins.h"
```

## Scoring

Each test receives a score that is a fractional number between 0 and 1 inclusive. If a test has a positive score, it is considered a successful test for your solution. Because Nora and Reni encourage even suboptimal games, they use the following scoring system.

Let $C$ be the number of calls to the function `guess`. The evaluation with respect to $C$ for **all tests** is as follows:

| Percentage $P_C$ | $C$      |
|------------------|----------|
| 100              | = 1      |
| 60               | $\le 3$  |
| 15               | $\le 17$ |
| 10               | $\le 34$ |
| 0                | $> 34$     |

Let $L$ be the total number of questions you used across all calls to the `guess` function.

## Scoring when $T = 1$

When $T = 1$ there are two types of tests. In the first $N \in [15, 30]$ (the first table), and in the second $N = 50\ 000$ (the second table). The evaluation with respect to $L$ in tests when $T = 1$ is as follows:

| Percentage $P_L$ | $L$    |
|------------------|------|
| 100              | $\le 10$ |
| 10               | $\le 30$ |
| 0                | $> 30$ |

| Percentage $P_L$                                   | $L$            |
|----------------------------------------------------|----------------|
| 100                                                | $\leq 16$      |
| $100 - \frac{L-16}{50-16} \times 20$               | $\leq 50$      |
| $80 - (\frac{L-50}{2000-50})^{0.4} \times 35$      | $\leq 2000$    |
| $45 - (\frac{L-2000}{50000-2000})^{0.3} \times 40$ | $\leq 50\ 000$ |
| 0                                                  | $> 50\ 000$    |

## Scoring when $T = 2$

When $T = 2$ in all tests $N = 50\ 000$. The evaluation with respect to $L$ in tests when $T = 2$ is as follows:

![](_page_2_Picture_1.jpeg)

| Percentage $P_L$                                   | $L$           |
|----------------------------------------------------|---------------|
| 100                                                | $\le 152$     |
| $100 - (\frac{L-152}{260-152})^{0.5} \times 15$    | $\le 260$     |
| $85 - \frac{L-260}{290-260} \times 10$             | $\le 290$     |
| $75 - (\frac{L-290}{550-290})^{0.3} \times 10$     | $\le 550$     |
| $65 - (\frac{L-550}{2000-550})^{0.6} \times 20$    | $\le 2000$    |
| $45 - (\frac{L-2000}{50000-2000})^{0.3} \times 40$ | $\le 50\ 000$ |
| 0                                                  | $> 50\ 000$   |

If you make an invalid action or do not guess the pictures correctly, you will get score 0 for the test. Otherwise, the score is equal to $P_C \times P_L$. For example, on a test with $T = 2$, if $L = 2000$ and $P = 3$, your score will be 45% × 60% = 0.27.

## Constraints

- $15 \le N \le 50\ 000$
- $1 \le T \le 2$

## Subtasks

| Subtask | Points | Required subtasks | $T$   | Additional constraints                                             |
|---------|--------|-------------------|-------|--------------------------------------------------------------------|
| 1       | 40     | -                 | = 1   | -                                                                  |
| 2       | 10     | 1                 | = 2   | The indices of the two Reni's pictures are consecutive numbers. |
| 3       | 50     | 1 - 2             | $\le 2$ | -                                                                  |

*The points for a given subtask are obtained only if all the tests provided for it and the required subtasks are successfully passed, and the points are equal to the minimum test score in it, multiplied by the points of the subtask.*

## Example Communication

| Participant's function      | Jury's program |
|-----------------------------|----------------|
|                             | `play(6, 1)`     |
| `guess({ {1,2,3}, {4,5,6} })` | `10`             |
| `guess({ {1}, {2}, {3} })`    | `010`            |
| `return {2}`                  | `Correct!`       |

| Participant's function         | Jury's program |
|--------------------------------|----------------|
|                                | `play(6, 2)`     |
| `guess({ {1,2}, {3,4}, {5,6} })` | `011`            |
| `guess({ {3}, {5} })`            | `01`             |
| `return {5,4}`                   | `Correct!`       |

## Explanation

![](_page_3_Picture_1.jpeg)

Let's look at the first example. After the first two questions which are asked at once, we know that the requested picture is among the first 3. Similarly, with the last 3 questions, we find out exactly which one it is.

## Local Testing

The file `Lgrader.cpp` is provided for local testing. Put your `twins.cpp` file together with `Lgrader.cpp` and `twins.h` into one folder and compile the three files together. This will give you a program to check the correctness of your function. The program will require two numbers on the first line - $N$ and $T$. On the next line the program requires the numbers of the pictures that are of Reni. The program will display in detail the steps when performing this test. To change this, you can change the value of the `DETAILS` constant at the beginning of the code. You can modify this file as you wish.

Starter code:
twins.h: #include<vector>
#include<string>

std::vector<int> play(int N,int T);

std::string guess(std::vector< std::vector<int> >& questions);



Grader code:
grader.cpp: #include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>

#include "twins.h"

#define MAXN 50007

using namespace std;

static int n,m,t,pos[4],P,x,y,vis[MAXN],tim,r;
static bool special[MAXN],in[200][200];
static string result,keyhesh;

static vector< pair<int,int> > sol;
static vector<int> ans;

static long double authorL,B,pointsL,pointsP,L;

static void prnt(double points,const char message[]){
    cout<<keyhesh<<" "<<message<<" "<<points<<"\n";
    exit(0);
}

static int randnum(){
    r=(r*2469+289)%2531;
    return r;
}

static void changepic(pair<int,int> z){
    if(randnum()%2==0)swap(z.first,z.second);

    special[pos[1]]=false;
    pos[1]=z.first;
    special[pos[1]]=true;
}

string guess(vector< vector<int> >& questions){
    m=questions.size();
    L+=m; P++;

    if(m==0)prnt(0.0,"#4");

    result.clear();
    result.resize(m);

    for(int i=0;i<m;i++){
        if(questions[i].size()==0)L--;

        tim++;
        for(int f=0;f<questions[i].size();f++){
            if(questions[i][f]<1 or questions[i][f]>n)prnt(0.0,"#5");

            if(vis[questions[i][f]]==tim)prnt(0.0,"#6");
            vis[questions[i][f]]=tim;
        }
    }

    if(L>n)prnt(0.0,"#7");

    if(n<=30 and t==1 and P==1){
        for(int i=0;i<m;i++){
            for(int f:questions[i])in[i][f]=true;
        }

        for(int i=1;i<=n;i++){
            for(int f=i+1;f<=n;f++){
                for(int p=0;p<m;p++){
                    if(in[p][i] and !in[p][f])break;
                    if(!in[p][i] and in[p][f])break;

                    if(p==m-1)sol.push_back({i,f});
                }
            }
        }

        if(!sol.empty()){
            changepic(sol[randnum()%int(sol.size())]);
        }
    }

    for(int i=0;i<m;i++){
        result[i]='0';

        for(int f=0;f<questions[i].size();f++){
            if(special[questions[i][f]])result[i]='1';
        }
    }

    return result;
}

static string gethesh(int n,int x){
    string res="";

    while(n>0){
        res.push_back(n%7+'0');
        n/=7;
    }
    reverse(res.begin(),res.end());

    while(x>0){
        res.push_back(x%9+'0');
        x/=9;
    }
    reverse(res.begin(),res.end());

    return res;
}

int main(){

    cin>>n>>t;

    if(t==1)authorL=16;
    if(t==2)authorL=152;

    for(int i=1;i<=t;i++){
        cin>>pos[i];
        special[pos[i]]=true;
    }
    keyhesh=gethesh(n,pos[1]);
    r=pos[1];

    ans=play(n,t);

    if(t==1 and ans.size()!=1)prnt(0.0,"#1");
    if(t==1 and (ans[0]<1 or ans[0]>n))prnt(0.0,"#2");
    if(t==1 and !special[ans[0]])prnt(0.0,"#3");

    if(t==2 and ans.size()!=2)prnt(0.0,"#1");
    if(t==2 and (ans[0]<1 or ans[0]>n))prnt(0.0,"#2");
    if(t==2 and (ans[1]<1 or ans[1]>n))prnt(0.0,"#2");
    if(t==2 and ans[0]==ans[1])prnt(0.0,"#3");
    if(t==2 and (!special[ans[0]] or !special[ans[1]]))prnt(0.0,"#3");

    if(n<=30){
        if(L<=10)pointsL=100.0;
        else if(L<=30)pointsL=10.0;
        else pointsL=0.0;
    }else{
        if(t==1){
            if(L<=authorL)pointsL=100.0;
            else if(L<=50)pointsL=100.0-( (L-authorL)/(50-authorL) )*20.0;
            else if(L<=2000)pointsL=80.0-pow( (L-50)/(2000-50) , 0.4 )*35.0;
            else if(L<=n)pointsL=45-pow( (L-2000)/(n-2000) , 0.3 )*40;
            else L=0.0;
        }else{
            if(L<=authorL)pointsL=100.0;
            else if(L<=260)pointsL=100.0-pow( (L-authorL)/(260-authorL) , 0.5 )*15.0;
            else if(L<=290)pointsL=85.0-(L-260)/(290-260)*10.0;
            else if(L<=550)pointsL=75.0-pow( (L-290)/(550-290) , 0.3 )*10.0;
            else if(L<=2000)pointsL=65-pow( (L-550 )/( 2000-550 ) , 0.6 )*20.0;
            else if(L<=n)pointsL=45-pow( (L-2000)/(n-2000) , 0.3 )*40;
            else L=0.0;
        }
    }

    if(P==1)pointsP=1.0;
    else if(P<=3)pointsP=0.6;
    else if(P<=17)pointsP=0.15;
    else if(P<=34)pointsP=0.1;
    else if(P>34)pointsP=0.0;

    prnt(pointsL/100.0*pointsP,"#8");

    return 0;
}

twins.h: #include<vector>
#include<string>

std::vector<int> play(int N,int T);

std::string guess(std::vector< std::vector<int> >& questions);



Setup script:

Evaluation script: