You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFDICE - Editorial

2
2

PROBLEM LINK

Practice
Contest

Author: Hanlin Ren
Tester: Jakub Safin
Editorialist: Jakub Safin

DIFFICULTY

SIMPLE

PREREQUISITIES

none

PROBLEM

Given the sequence of numbers on the top face of a die rolled $90^\circ$ at a time, find one possible configuration of numbers on the faces of the die or determine that it doesn't exist.

QUICK EXPLANATION

Bruteforce all possible answers, check if no step corresponds to rotation to the same face or the opposite face.

EXPLANATION

This problem can be misleading, since it may seem at first that the orientation of the die matters. Actually, it doesn't, since if the number on the top of the die is $x$ and the number on the bottom face is $y$, then it's possible to get any of the remaining 4 numbers can be on top after exactly one step; of course, it's impossible to get $y$ on top after one step and we can't keep $x$ on top either.

We don't actually know the pairs of numbers on opposite faces, but there aren't many choices, so we can bruteforce them - pick three unordered pairs and ensure they contain each number 1 through 6 exactly once. There are only $\frac{1}{3!}\frac{6\cdot5}{2}\frac{4\cdot3}{2}\frac{2\cdot1}{2}=15$ such triples of disjoint pairs.

Therefore, all we need to do is try all possible configurations of numbers on the die and for each of them, check if the conditions $A_i \neq A_{i+1}$, $A_i \neq o(A_{i+1})$ hold for all $1 \le i < N$. We actually found all possible configurations this way, not just one.

There are $O(1)$ configurations, so the time complexity is $O(N)$, same with memory complexity. We can improve this to $O(1)$ memory either by checking which configurations satisfy the constraints as we read the input, or by remembering only how many times each pair $(A_i,A_{i+1})$ appeared.

AUTHOR'S AND TESTER'S SOLUTIONS

Setter's solution
Tester's solution

asked 30 Sep '17, 18:55

xellos0's gravatar image

7★xellos0
5.9k54394
accept rate: 10%

edited 01 Oct '17, 22:49

admin's gravatar image

0★admin ♦♦
19.8k350498541

1

solutions are not opening please resolve the problem

(30 Sep '17, 23:47) vinaycr73★

Why practice problem and submitted solutions of this problem are not visible? also other lunchtime problems are not visible

(01 Oct '17, 02:15) luvk14124★

solutions not visible and problem is not available in practice section :/

(01 Oct '17, 10:49) sandeep_0075★

We know that the next number coming on the top will never be the opposite of the previous number , for eg, if the input is, 1 3 4 ,then opp(1) will not be eq to 3 . opp(3) will not be equal to 4 and 1 . opp(4) will not be equal to 3. So this is what is done in the 2D array g, Here we are denoting 1 to show that the numbers will not be opposite to each other .[ for the above example g[1][3]=1 ,g[3][1]=1.... etc ]. next_permutation gives the next lexographic combination. if there is an array a=[1,2,3,4,5] ,next_permutation(a,a+5) will give me [2,1,3,4,5] and in next iteration will give [2,3,1,4,5 ] and so on. In this array p we will have the final result. So we keep on shuffling untill all elements index pos is not equal to that number itself . the next thing is , if opp[x]=y then opp[y] will be x. So that what we are checking using the condition (p[p[i]]==i) , if this condition is satisfied then i will be greater than 6, now atlast we will check if the array p is legit by cross-checking it with the 2D array 'g' ,

link

answered 02 Oct '17, 00:15

rishav007's gravatar image

3★rishav007
212
accept rate: 0%

I did this question trying all possible position reccursively. It passed the first sub task case but showed wrong ans for the 2nd subtask.Please tell me where I went wrong.

Link to my ans is: https://www.codechef.com/viewsolution/15568740

Can anybody please tell me the test case for where it went wrong.

Thankx in advance.

link

answered 01 Oct '17, 09:55

ayushi09's gravatar image

1★ayushi09
325
accept rate: 0%

edited 01 Oct '17, 09:56

your algorithm is too slow to pass the second subtask

link

answered 01 Oct '17, 10:02

soheb17's gravatar image

5★soheb17
602
accept rate: 0%

can someone explain the setter's soln briefly??

link

answered 01 Oct '17, 18:13

batti_q1w2's gravatar image

2★batti_q1w2
11
accept rate: 0%

In the setter's solution, in the worst case it will enumerate all the permutations whose complexity is 6! = 720. Am i right?

link
This answer is marked "community wiki".

answered 05 Oct '17, 11:15

jainy6's gravatar image

2★jainy6
11
accept rate: 0%

Yes, but checking each takes O(1) and the total time complexity is O(N) regardless.

(05 Oct '17, 19:21) xellos07★

Here is the explanation for the setter's code : #include <bits stdc++.h=""> using namespace std;

int N, A[2333], g[7][7], p[7];
int doit() {
  int i;
  memset(g, 0, sizeof g);
  scanf("%d", &N);
  for (i = 1; i <= N; i++) {
    scanf("%d", &A[i]);
    if (i > 1) g[A[i]][A[i - 1]] = g[A[i - 1]][A[i]] = 1;       //checking when solution isnt possible
  }
  for (i = 1; i <= 6; i++) p[i] = i;    // Create for next_permutation
  for (i = 1; i <= 6; i++) if (g[i][i]) return printf("-1\n");
  do {
    for (i = 1; i <= 6; i++) if (p[i] == i) break;          // index and number must not be the same
    if (i > 6) {                                                                                // When this has happened
      for (i = 1; i <= 6; i++) if (p[p[i]] != i) break; // When solution will be arrived , p[p[2]] = p[1] == 2 ;must be equal to 2
      if (i > 6) {
        for (i = 1; i <= 6; i++) if (g[i][p[i]]) break; // If in matrix we have 1 for any , then try new
                if (i > 6) {
                for (i = 1; i <= 6; i++) printf("%d ", p[i]);   // If all the obstacles are overcome, print the final array
            return printf("\n");
                }
      }
    }
  } while (next_permutation(p + 1, p + 7));
  printf("-1\n");
}

int main() {int t; scanf("%d", &t); while (t--) doit(); return 0;}
link

answered 06 Oct '17, 01:22

niteshx2's gravatar image

4★niteshx2
414
accept rate: 0%

The problem can also be solved using backtracking and recursion.

Here is a recursive implementation of the same.

https://www.codechef.com/viewsolution/15596365

link

answered 06 Oct '17, 20:57

shivam2296's gravatar image

3★shivam2296
173
accept rate: 0%

edited 06 Oct '17, 20:58

The setters should comment their code for readability.

link

answered 28 Jun '18, 13:02

da_grt_aru's gravatar image

2★da_grt_aru
0
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,191
×44
×9

question asked: 30 Sep '17, 18:55

question was seen: 2,614 times

last updated: 28 Jun '18, 13:02