SEPTEMBER LUNCHTIME UNOFFICIAL EDITORIALS (FISRT TWO PROBLEMS)

editorial
,
1

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 :smiley: )

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

        if(i != i1 && !adj[i1][i]){		

            boolean[] v = new boolean[7]; // 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++){

                        if(!adj[i3][k] && !v[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[7];// 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
2

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

3

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?

4

It was just to rule out a few cases and run the brute force :smiley:

5

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… :smiley:

1 Like
6

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()));
    	if(!can)cout<<-1;//If valid permutation not found, print -1.
    	else for(int i = 1;i<=6;i++)
    		cout<<ans[i]<<" ";
    	cout<<endl;
    }
 
 
    return 0;
}
7

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

8

Nice one!!

But still, its always a tendency that one likes his own code :slight_smile:

1 Like
9

Haha yeah :stuck_out_tongue: