CHCUBE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Antoniuk Vasyl
Tester: Mugurel Ionut Andreica
Editorialist: Lalit Kundu

DIFFICULTY:

CakeWalk

PREREQUISITES:

implementation, basic visualisation

PROBLEM:

One day Chef found a cube which has its each side painted in some color out of black, blue, red, green, yellow or orange colors. Now he asks you to check if he can choose three sides such that they are pairwise adjacent and painted in the same color.

EXPLANATION:

================
Most basic thing to be observed is that three sides in a cube can pairwise share an edge if they also share an corner. For example, in the following image sides 1, 2 and 3 are pairwise adjacent because they are sharing a corner.
Smiley face

So, there are only 8 possible triplets which can give us our answer. Now, easiest way is to hard code these triplets in your program. So, if we follow the indexing method where \textrm{front}: 0, \textrm{back}: 1, \textrm{left}: 2, \textrm{right}: 3, \textrm{top}: 4, \textrm{botton}: 5(note that we follow the indexing method given in problem so that coding is simpler), following 8 triplets denote the corners. Three elements in a triplet denotes the indexes of sides that share this corner.

int adj[8][3] = {
{0, 2, 4},
{0, 3, 4},
{0, 2, 5},
{0, 3, 5},
{1, 2, 4},
{1, 3, 4},
{1, 2, 5},
{1, 3, 5},
};

Now, for each query of cube, we just have to take input and then check for all 8 corners if there exists a triplet in which all these indexes have same color.

Following pseudo code provides the solution:

ans = "NO"     //initialise answer to NO first
color[6];     //color[i] denotes the color of the side denoted by index i

for i = 0 to 5:
     scan color[i]

for i=0 to 7:
     if color[adj[i][0]] == color[adj[i][1]] == color[adj[i][2]]:
          ans = "YES"    

print ans

ALTERNATE SOLUTION:

You can also notice that if we follow the indexing as defined above, then faces i, j and k share a corner for all 0 \le i \lt 2 and 2 \le j \lt 4 and 4 \le k \lt 6. Now, this is even more easy to code.

COMPLEXITY:

For each test case, complexity is O(8 + string comparison$)$ which can be assumed as constant time.

AUTHOR’S, TESTER’S SOLUTIONS:

setter
tester

1 Like

What is wrong with my code …PLease help me out…I was getting runtime error during submission…??
Thanks for your kind attention…

 import java.io.*;
 class ChefAndCube {
 public static void main(String[] args) throws IOException {
    BufferedReader inp=new BufferedReader(new InputStreamReader(System.in));
    int T=Integer.parseInt(inp.readLine());
    for(int x=0;x<T;x++){
        String[] Sa=new String[6];
        int k=0;
        for(int i=0;i<Sa.length;i++){
            Sa[i]=inp.readLine();
        }
        for(int y=0;y<Sa.length;y++){
            for(int z=y;z<Sa.length;z++){
                if(Sa[y].equals(Sa[z])){
                    k++;
                }
            }
            if(k>=3)
                break;
            k=0;
        }
        if(k>3){
            System.out.println("YES");
        }
        else if(k==3){
            if(((Sa[4].equals(Sa[2]))&&(Sa[4].equals(Sa[0])))||((Sa[4].equals(Sa[2]))&&(Sa[4].equals(Sa[1])))||((Sa[4].equals(Sa[3]))&&(Sa[4].equals(Sa[0])))||((Sa[4].equals(Sa[3]))&&(Sa[4].equals(Sa[1])))||((Sa[5].equals(Sa[2]))&&(Sa[5].equals(Sa[0])))||((Sa[5].equals(Sa[2]))&&(Sa[5].equals(Sa[1])))||((Sa[5].equals(Sa[3]))&&(Sa[5].equals(Sa[0])))||((Sa[5].equals(Sa[3]))&&(Sa[5].equals(Sa[1]))))
                System.out.println("YES");
        }
        else
            System.out.println("NO");
    }
}

}

What is wring with following code?:-

include < bits/stdc++.h>

using namespace std;

int main(){

int tc;

string s[6];

cin>>tc;

while(tc–){

int flag=0;

for(int i=0;i<6;i++){
	cin>>s[i];
}

while(1){

if(s[0]==s[2] &&s[0]==s[4]){
flag=1;
break;
}
if(s[0]==s[2] &&s[0]==s[5]){
flag=1;
break;
}if(s[0]==s[3] &&s[0]==s[4]){
flag=1;
break;
}if(s[0]==s[3] &&s[0]==s[5]){
flag=1;
break;
}if(s[1]==s[3] &&s[0]==s[4]){
flag=1;
break;
}if(s[1]==s[3] &&s[0]==s[5]){
flag=1;
break;
}if(s[1]==s[2] &&s[0]==s[4]){
flag=1;
break;
}if(s[1]==s[2] &&s[0]==s[5]){
flag=1;
break;
}
if(flag==0)
break;

}
if(flag)
cout<<“YES\n”;
else
cout<<“NO\n”;
}
return 0;
}

Can anyone help me to find where I have gone wrong?
http://www.codechef.com/viewsolution/7360732

@sinha_u use strcmp to compare strings…

@konfused just remove “else”, only keep two if’s… I did the same mistake :smiley:

Tell me if you didn’t get it

Reason - what if col1==(col3||col4) but (col3||col4)!=(col5||col6) at the same input, col1==(col3||col4) but (col3||col4)!=(col5||col6)

 A test case to give WA for your answer -
 green green green blue green yellow

@kislaya123 In your second for loop you try to read six lines, one for each side of the cube. However the problem provides this information on a single line. This is causing an exception to be thrown. Try something like:

String input;

input = inp.readLine();

String[] Sa = input.split(" ");

Also I think you will then get WA because I believe the following case will fail for your code. This should return NO.
1
blue blue green green blue blue

@jaksparo string comparison is perfectly fine.
@sinha_u for the last four conditions replace s[0] by s[1]

Thanks arcticblue …
I changed my code … Could you help me to figure out (why I am getting runtime error as now I am not using string …)Please…

CODE IS AS :---->
/…Above same as previous…/

if(count==3){
if(sum==420||sum==421||sum==430||sum==431||sum==520||sum==521||sum==530||sum==531)
System.out.println(“YES”);
else
System.out.println(“NO”);

@kislaya123 I’m not certain how your code matches up with the original code. Have a look at my submission, it gets accepted. It’s based off your code with my suggested change. It also includes a change to fix the bug I mentioned.

http://www.codechef.com/viewsolution/7478436

If the code still doesn’t make sense then can you post a link to your failing submission and I can have a look at it.

Link are as :–>

Please check it out…
http://www.codechef.com/viewsolution/7363393

I think my code is quite same as yours …Please Check it out…

Your code is different in one important place. You are still assuming each face is input on a separate line. See your code below, this is trying to read a whole line for each face.

String[] Sa=new String[6];

int count=0,sum=0,j;

for(int i=0;i<Sa.length;i++){

Sa[i]=inp.readLine();

}

You need to read in a single line and then split the line into the six faces. Replace the four lines above with the four lines below.

int count=0,sum=0,j;

String input;

input = inp.readLine();

String[] Sa = input.split(" ");

This should fix your run time error.

If we just count the number of times eachh color exists and check if it is 3 then isnt that condition enough tto prove that the cube has pairwise adjacent sides ?

1 Like

No. It is possible for there to be three faces with the same colour that aren’t pairwise adjacent. Try both of the test cases below.

2

blue blue green green blue black

blue blue green green blue blue

You can have the top, bottom and front the same colour but then the top and bottom aren’t pairwise adjacent. Every pair must be adjacent and there are three pairs.

Hi, Can you check what’s wrong with this code http://www.codechef.com/viewsolution/7388212… Please help me with this one …

Unfortunately there are a number of things wrong with your code. Probably the most confusing one for you is that the example test cases don’t work. The following code is incorrect. You need to account for the null terminator at the end of the string (\0).

char color_array[6],first_color[6],second_color[6];

This is causing the testcases variable to be overwritten with a zero. So when I tried to run the two example test cases your code stopped after the first one.

The second issue is that you only sometimes print out a “YES” or “NO” every line test case needs a yes or no.

Also your logic is incorrect. It’s not enough to check there are three or less colours. The following two test cases have less than three colours but both should give NO as the correct answer.

2

blue blue green green blue black

blue blue green green blue blue

You need to check that the adjacent faces are the same colour.

Have a look at my answer. http://www.codechef.com/viewsolution/7348299 If the front is one colour then the top and one side need to be the same colour or the bottom and one side need to be the same colour. If this is true then print YES. The same for back.

Hi articblue, Thank you for your reponse… How about this one… http://www.codechef.com/viewsolution/7483828 This runs fine for the two testcases that you gave. I understand the null terminator issue but isn’t the logic correct for this one? What you have said I have tried to program the same logic i.e

“If the front is one colour then the top and one side need to be the same colour or the bottom and one side need to be the same colour. If this is true then print YES. The same for back.”

Try:

1

blue blue orange blue blue orange

You code gives NO when the correct answer is YES.

//