CHCUBE - Editorial

darkshadows · June 20, 2015, 12:02pm

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.

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

kislaya123 · July 13, 2015, 4:22pm

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");
    }
}

}

sinha_u · July 13, 2015, 7:01pm

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

konfused · July 13, 2015, 7:24pm

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

jaksparo · July 14, 2015, 7:20am

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

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

monodeep_1215 · July 15, 2015, 10:34am

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 ?

arun_chauhan · July 15, 2015, 12:05pm

Hi, Can you check what’s wrong with this code CodeChef: Practical coding for everyone… Please help me with this one …

gaming30 · July 16, 2015, 7:26pm

What’s wrong with my code? I was getting wrong answer during submission…Please Help!!

#include <bits/stdc++.h>
#include <vector>
using namespace std;
class Cube
{
public:
    void getColors();
    void Test();

private:
    string ptr[6];
};
void Cube::getColors()
{
    cin>>ptr[0]>>ptr[1]>>ptr[2]>>ptr[3]>>ptr[4]>>ptr[5];
    for(int i=0;i<6;++i)
    {
        if(ptr[i]=="black"||ptr[i]=="blue"||ptr[i]=="red"||ptr[i]=="green"||ptr[i]=="yellow"||ptr[i]=="orange");
        else
        {
            cout<<"Wrong Colour, Exiting....";
            exit(1);
        }
    }
}
void Cube::Test()
{
    if((ptr[0]==ptr[2])||(ptr[0]==ptr[3]))
    {
        if((ptr[0]==ptr[4])||(ptr[0]==ptr[5]))
            cout<<"YES";
    }
    else if((ptr[1]==ptr[2])||(ptr[1]==ptr[3]))
    {
        if((ptr[1]==ptr[4])||(ptr[1]==ptr[5]))
            cout<<"YES";
    }
    else
            cout<<"NO";
}
int main()
{
    int T; vector<Cube> ch(1); Cube a;
    cin>>T;
    if(T<1 || T>50000)
    {
        cout<<"Number of test cases are out of available limits, exiting....";
        exit(0);
    }
    for(int i=0;i<T;++i)
    {
        if(i>0)
            ch.push_back(a);
        ch[i].getColors();
    }
    for(int j=0;j<T;++j)
    {
        cout<<endl;
        ch[j].Test();
    }
    return 0;
}

harry30 · August 27, 2015, 8:47pm

Help , I still can’t figure out why my solution still WA even I have already tested it on ideone and the output is same with the problem statement

Here is the link to the code : http://ideone.com/mDoLO0

ksharma377 · August 27, 2015, 9:56pm

@harry30

You have written check = false outside the test cases loop. So once the check flag is set to true (in some test case), there is no way it can go false and will always be true for all the test cases afterwards.

So your output would be something like:

NO
NO
NO
.
.
.
YES
YES
YES
YES
.
.
.
YES

Write that line inside the test cases loop. That would solve the problem.

vijju123 · January 28, 2017, 11:30am

@apurva_121

Try this test case-

1
blue blue green blue black green

jaksparo · July 14, 2015, 7:20am

@sinha_u use strcmp to compare strings…

arcticblue · July 14, 2015, 8:49am

@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

avmnusng · July 14, 2015, 8:50am

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

kislaya123 · July 14, 2015, 1:42pm

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”);

arcticblue · July 14, 2015, 2:04pm

@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.

kislaya123 · July 14, 2015, 6:42pm

Link are as :–>

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

kislaya123 · July 14, 2015, 11:28pm

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

arcticblue · July 15, 2015, 5:10am

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.

arcticblue · July 15, 2015, 10:47am

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.