SNACKUP - Editorial

general
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Alei Reyes
Primary Tester: Hussain Kara Fallah
Secondary Tester: Kacper Walentynowicz
Editorialist: Hussain Kara Fallah

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

We have n recipes and n judges to taste them. Each judge must try every recipe exactly twice.

You have to organize tasting rounds. A round is is structured as follows:

You will choose distinct k recipes and for each one of them prepare 2 identical dishes.
You will choose distinct k judges and each of them must try 2 different recipes from the ones we chose (1 dish of each of them in particular). Two different judges may try the same recipe (but they may not share a common dish).

After each round all prepared dishes must be eaten by judges.

You can arbitrarily decide the number of rounds, and the structure of each one (number of invited judges), but as a rule of the contest at the end of all round each judge must have tasted every recipe exactly twice.

EXPLANATION:

This is a constructive problem, which can be solved by different ways. I will describe mine which is quite simple.

Let’s organize n rounds. You can imagine the recipes aligned in a circle. At the 1st round the ith judge is standing beside the ith recipe. In each round each judge tries the recipe he is standing beside and the next one in front of him. After each round our judges move 1 step around the circle. Check this solution for n = 4 :

Round Judge 1st Recipe 2nd recipe
1 1 1 2
1 2 2 3
1 3 3 4
1 4 4 1
2 1 2 3
2 2 3 4
2 3 4 2
2 4 1 1
3 1 3 4
3 2 4 1
3 3 1 2
3 4 2 3
4 1 4 1
4 2 1 2
4 3 2 3
4 4 3 4

By scheduling rounds this way, it’s guaranteed that every recipe would be tasted by every judge exactly twice by the end of the nth round.

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution: [Here] 444
TESTER’s solution: [Here] 555

1 Like
2

That moment when your solution matches the Editorial’s :smiley:

3

Is this a correct solution for n=4

4 rounds

Rnd 1: (1 1 2) (2 2 3) (3 3 4) (4 1 4)

Rnd 2: (1 2 3) (2 3 4) (3 1 4) (4 1 2)

Rnd 3: (1 3 4) (2 1 4) (3 1 2) (4 2 3)

Rnd 4: (1 1 4) (2 1 2) (3 2 3) (4 3 4)

If it isn’t correct, pls correct me!! Thank you :slight_smile:

1 Like
4

It’s correct.

5

In the problem statement, it is written that x and y should not be same. So, in the explanation, (2 3 4 2) should be (2 3 4 1);
and (2 4 1 1) should be (2 4 1 2).
Correct me if I’m wrong. Thanks :slight_smile:

6

#include<bits/stdc++.h>
#define on(x , y) ((x) & (1<<(y)))
using namespace std;
int T , n , B;
int main(){
int T;
cin>>T;
while(T–){
cin>>n;
vector < pair < int , int > >v ;
for(int j = 1 ; j < n ; j++)
v.push_back({j , j + 1});
v.push_back({n , 1});
int sz = v.size();
cout<<sz<<endl;
for(int r = 0 ; r < n ; r++){
int pos = r;
cout<<n<<endl;
for(int j = 0 ; j < n ; j++){
cout<<j + 1 <<’ ’ << v[pos].first<<’ '<<v[pos].second<<endl;
pos++; pos %= n;
}

    }
}

}