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

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
3

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:

4

#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;
}

    }
}

}

5

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

6

It’s correct.

7

MY SIMPLE THAT GOT AC

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL)
#define cin(a) scanf("%d",&a)
#define cin2(a,b) scanf("%d%d",&a,&b);
#define ifor(st,lim) for(long i=st;i<lim;i++)
#define jfor(stt,llim) for(int j=stt;j<llim;j++)
#define blank printf("\n")
#define cout(a) printf("%d",a)
void solve()
{
int n; cin>>n;
cout<<n<<’\n’;
int j=1;
int s = n/2;
int s1 = (n/2)+1;
if(n%2==0)
{
while(s–)
{
ifor(0,2)
{
cout<<n<<’\n’;
for(int i=1;i<=n;i++)
{
cout<<i<<" “<<j<<” “<<j+1<<’\n’;
}
}
j=j+2;
}
}
else
{
for(int x=0;x<n;x++)
{
ifor(0,1)
{
cout<<n<<’\n’;
if(x==n-1)
{
for(int i=1;i<=n;i++)
{
cout<<i<<” “<<n<<” “<<“1”<<’\n’;
}
}
else
{
for(int i=1;i<=n;i++)
{
cout<<i<<” “<<j<<” "<<j+1<<’\n’;
}
}
}
j=j+1;
}
}

}

int main()
{
#ifndef ONLINE_JUDGE
freopen(“input.txt”,“r”,stdin);
freopen(“output.txt”,“w”,stdout);
#endif
FIO;
int t; cin>>t;
while(t–)
{
solve();
}
}

9

If we can choose the same recipes from different dishes then for example if n=2, we print r=2 then for each round r print r1-1 1 1,2 2 2and r2- 1 2 2,2 1. Why this answer gives wa? I’m confused please correct me.

10

I believe this question has some issues. I got the correct answer only when I tried to print the answer in the pattern as used by the author. For n=odd I use the same order and for n=even,
eg n==4, I tried to print the pattern:
1 1 2
2 1 2
3 3 4
4 3 4.
Correct code:
https://www.codechef.com/viewsolution/38001923
Incorrect code:
https://www.codechef.com/viewsolution/38001575
Can someone please crosscheck as well?