 # SEPTEMBER LUNCHTIME UNOFFICIAL EDITORIALS (FISRT TWO PROBLEMS)

Problem Chef and Cook-Off Contests

Problem

To find whether any subset of given problems can form a particular set.

Observation:All the different types of problems can be checked independently of each other…

So, for this problem, it is sufficient to check if given problem set contains atleast one cakewalk, one easy, one simple, one medium or easy-medium and one medium or medium hard…

You may have a look at my code here

Problem Chef and Dice

Following a set of turns, we have to find a valid dice configuration and output in the format

O(1) … where O(1) means Opposite side of 1 … (I wasted half an hour on this today )

Observation: Here, the number which appear on ith turn will never be opposite to the number which appear on (i-1)th turn as well as (i+1)th turn…

If Number at ith turn == Number at (i+1)th turn, ans is -1

So, This is all we need for this problem…

Using this information, we run the brute-force algorithm (Because sides of dice are 6 only, our solution won’t get TLE)

pseudocode

adj[i][j] is a boolean table where adj[i][j] = true if i and j are adjacent, else false

``````    int i1 = 1; // Select any vertex

for(int i = 1; i<=6; i++){

//condition for selecting a candidate for opposite vertex

boolean[] v = new boolean; // keeping track of sides visited

int i2 = i; 	//opposite of i1

v[i1] = true;	 //marked these two as visited

v[i2] = true;

for(int j = 1; j<= 6; j++){

if(!v[j]){ 		//Selecting another non-selected side

int i3 = j;

v[i3] = true;

//finding opposite in this loop
for(int k = 1; k<= 6; k++){

v[k] = true;

int i4 = k;

for(int l = 1; l<= 6; l++){

if(!v[l]){

int i5 = l;

v[i5] = true;

int i6 = 21 - i1-i2-i3-i4-i5;

if(i6>0 && i6 < 7 && !v[i6] && !adj[i6][i5]){

int[] opp = new int;// opp[i] = side opposite to i

opp[i1] = i2;

opp[i2] = i1;

opp[i3] = i4;

opp[i4] = i3;

opp[i5] = i6;

opp[i6] = i5;

String out = "";

for(int m = 1; m<= 6; m++)out += opp[m]+" ";

print(out);

break case;

}

v[i5] = false; // unmarking this side for next candidate

}

}

v[k] = false;

}

}

v[i3] = false;

}

}

}

}

print(-1); // in case no permutation satisfies the constraints
``````

Have a look at my solution here.

I didn’t get the full scores in last 2 problems, so, It’s better to refer to official editorial…

Hope you all find this helpful

1 Like

for t in range(input()):
n=input()
a=map(int,raw_input().split())
b=[0,6,5,4,3,2,1]
b1=1
c=[0,6,4,5,2,3,1]
c1=1
d=[0,5,4,6,2,1,3]
d1=1
e=[0,5,6,4,3,1,2]
e1=1
f=[0,4,5,6,1,2,3]
f1=1
g=[0,4,6,5,1,3,2]
g1=1
flag=1
for x in range(n-1):
if a[x]==a[x+1]:
flag=0
break
else:
if b[a[x]]==a[x+1]:
b1=0
if c[a[x]]==a[x+1]:
c1=0
if d[a[x]]==a[x+1]:
d1=0
if e[a[x]]==a[x+1]:
e1=0
if f[a[x]]==a[x+1]:
f1=0
if g[a[x]]==a[x+1]:
g1=0
if b1 and flag:
for x in range(1,7):
print b[x],
print

``````    elif c1 and flag:
for x in range(1,7):
print c[x],
print
elif d1 and flag:
for x in range(1,7):
print d[x],
print
elif e1 and flag:
for x in range(1,7):
print e[x],
print
elif f1 and flag:
for x in range(1,7):
print f[x],
print
elif g1 and flag:
for x in range(1,7):
print g[x],
print
else:
print -1
``````

my code goes something like this , i could not submit it , as the submission link of this problem is not there .
is this approach correct?

Keeping it short and simple, not a lot of casework but just STL.

``````#include <bits/stdc++.h>
using namespace std;
#define int long long int

main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector< vector<int> > poss(7, vector<int>(7, 1));//Poss stands for "Possible" poss[i][j]==1 if it is possible to keep i opposite to j
vector<int> v(n), ans(7, 0);//v stores the input and ans the output.
bool can = true;
for(int i = 0;i<n;i++)
cin>>v[i];
for(int i = 1;i<n;i++)
{
poss[v[i]][v[i-1]] = poss[v[i-1]][v[i]] = 0;//Faces appearing adjacent to each other in the input can never appear opposite to each other.
if(v[i]==v[i-1])can = false;//if same number appears twice, adjacent, then it is never possible.
}
if(!can)
{
cout<<-1<<endl;
continue;
}
for(int i = 1;i<=6;i++)
ans[i] = i, poss[i][i] = 0;//initialize poss[i][i] to 0 because a side cannot be opposite to itself, duh! Also initialize the answer to lexicographical smallest.
can = false;
do
{
bool cant = true;
for(int i = 1;i<=6;i++)
if((!(poss[i][ans[i]]))||i!=ans[ans[i]])
cant = false;
if(cant)//if no problem with the current permutation, then break and print.
{
can = true;
break;
}
}while(next_permutation(ans.begin(), ans.end()));
else for(int i = 1;i<=6;i++)
cout<<ans[i]<<" ";
cout<<endl;
}

return 0;
}``````

@taran_1407
thnx man, I was wondering about how to approach the second question.

It was just to rule out a few cases and run the brute force Mate, your idea was clever but u missed out cases

What if O(1) = 2 or 3 for some case

Your code may fail on following case

1 3 1 4 1 5 1 6

O(1) = 2 in this case which your solution will never get…

Hope that clarifies… 1 Like

oh shitty i missed out a lot of cases . your one was good

Nice one!!

But still, its always a tendency that one likes his own code 1 Like

Haha yeah 