Tri-Hexagonal Puzzle

@Anurag The vertex labelling is "top-down, left to right". If you list the vertices in order, then all the vertices that are at the same height appear together. Vertices that are higher appear earlier. Among vertices at the same height, vertices that are more to the left appear earlier.

The figure, input and output given in the problem statement all refer to the same test case.

is it possibl that at some intermediate stage, some of the points r overlapping so that < 4 pts r visibl?

Your question makes no sense. Read the problem statement again.

I havent been able to understand the qn (apologies if this is very silly)...

suppose we take the case given in input

0000000101011

In the first step, suppose we perform the operation  1 0 i.e. rotate hex 1 counter clockwise. Then do we get 0000100101011? Or can we get both 0000100001011 and 0000100100011?

Thank you

@Vivek

imagine the "tri-hexagon" as a framework of 13 cups. and there are 4 balls placed in these cups.

when a particular hexagon needs to be "rotated" then the balls on the perimeter of the hexagon are shifted.

hope this helps.

is the test i/o alrite?

Yes, the test I/O is alright.

I think the input should be 0000000101101.Does anyone else think so?

if moves should be minimum or any number of moves?

@ shreyas - the input is correct.

@ Pankaj - read the problem statement.

@shreyas, @Stephen If the given labelling is “top-down, left to right”, then shreyas is using a labelling scheme that could be described as “left-right, top to bottom”. shreyas is looking at all the vertices in each column, then moving on to the next column; you should be looking at all the vertices in each row, then moving on to the next row.

What is memory usage limit??

@piyush Like I said at Traffic jam, “There is no fixed upper memory limit, but 64K is the lower limit for available memory.”

Little Johny may like to solve this himself

#venkat.....hehe

can anybody explain the numbering of tst case with diagram ....

it is dificult to understand because there are 15 vertex and 13 digit code..

1           2

3            4            5

6            7            8

9            10

11          12

13

@amritpal hope this helps

The formatting got  completely changed  in the previous post . 

         1                2

3               4                 5

6               7                 8

        9               10

        11              12

                13

Hi

My code works perfectly on my system, but here it is showing runtime error SIGSEV. What could be the reason? I used C++

i m new to coding can someone help me how to approach this problem!!

i hav understood the ques.

thanx

I need another test case that doesn't involve 3 black vertices on the same hexagon,just the input and the output is enough

It is your job to come up with your own test cases.

finally ... i was almost going to give up when i realized i was printing the result in wrong order :/

Check if my output format was right for each test case

line-1:Number of rotations

next lines:single space seperated H and C in each line in order giving the corresponding rotation

my code is working fine with some warnings in g++ 4.3 (fedora),but here its shows those warnings as error

any idea ?

You could try fixing them?

What is the Judge computers configuration?

I'm getting a TLE. On my comp, I can execute >100 test cases in under .5s.

1. #include<iostream>
2. #include<cstring>
3. #include<cstdio>
4. using namespace std;
5. #define MAXSTATES 70000
6. #define N 15
7. #define MAX_D 8
8.  
9. int state[N]={0},tmp;
10.  
11. int tmp_depth,cur_depth=0;
12. int MAXDEPTH = MAX_D;
13.  
14. struct blk {
15. int id;
16. int clk_mov;
17. }tmp_path[10],soln[10];
18.  
19. blk dp_sols[MAXSTATES];
20.  
21. void move_one_step(int mov_id,int clk_mov){
22. if(clk_mov) {
23. switch(mov_id) {
24. case 0://rotate hexagon0
25. tmp=state[1];
26. state[1]=state[3];
27. state[3]=state[6];
28. state[6]=state[9];
29. state[9]=state[7];
30. state[7]=state[4];
31. state[4]=tmp;
32. break;
33. case 1://rotate hexagon1
34. tmp=state[2];
35. state[2]=state[4];
36. state[4]=state[7];
37. state[7]=state[10];
38. state[10]=state[8];
39. state[8]=state[5];
40. state[5]=tmp;
41. break;
42. case 2://rotate hexagon2
43. tmp=state[7];
44. state[7]=state[9];
45. state[9]=state[11];
46. state[11]=state[13];
47. state[13]=state[12];
48. state[12]=state[10];
49. state[10]=tmp;
50. }
51. }
52. else {
53. switch(mov_id) {
54. case 0://rotate hexagon0
55. tmp=state[1];
56. state[1]=state[4];
57. state[4]=state[7];
58. state[7]=state[9];
59. state[9]=state[6];
60. state[6]=state[3];
61. state[3]=tmp;
62. break;
63. case 1://rotate hexagon1
64. tmp=state[2];
65. state[2]=state[5];
66. state[5]=state[8];
67. state[8]=state[10];
68. state[10]=state[7];
69. state[7]=state[4];
70. state[4]=tmp;
71. break;
72. case 2://rotate hexagon2
73. tmp=state[7];
74. state[7]=state[10];
75. state[10]=state[12];
76. state[12]=state[13];
77. state[13]=state[11];
78. state[11]=state[9];
79. state[9]=tmp;
80. }
81. }
82. }
83.  
84. void com_back_one_step(int mov_id,int clk_mov){
85. if(!clk_mov) {
86. switch(mov_id) {
87. case 0://rotate hexagon0
88. tmp=state[1];
89. state[1]=state[3];
90. state[3]=state[6];
91. state[6]=state[9];
92. state[9]=state[7];
93. state[7]=state[4];
94. state[4]=tmp;
95. break;
96. case 1://rotate hexagon1
97. tmp=state[2];
98. state[2]=state[4];
99. state[4]=state[7];
100. state[7]=state[10];
101. state[10]=state[8];
102. state[8]=state[5];
103. state[5]=tmp;
104. break;
105. case 2://rotate hexagon2
106. tmp=state[7];
107. state[7]=state[9];
108. state[9]=state[11];
109. state[11]=state[13];
110. state[13]=state[12];
111. state[12]=state[10];
112. state[10]=tmp;
113. }
114. }
115. else {
116. switch(mov_id) {
117. case 0://rotate hexagon0
118. tmp=state[1];
119. state[1]=state[4];
120. state[4]=state[7];
121. state[7]=state[9];
122. state[9]=state[6];
123. state[6]=state[3];
124. state[3]=tmp;
125. break;
126. case 1://rotate hexagon1
127. tmp=state[2];
128. state[2]=state[5];
129. state[5]=state[8];
130. state[8]=state[10];
131. state[10]=state[7];
132. state[7]=state[4];
133. state[4]=tmp;
134. break;
135. case 2://rotate hexagon2
136. tmp=state[7];
137. state[7]=state[10];
138. state[10]=state[12];
139. state[12]=state[13];
140. state[13]=state[11];
141. state[11]=state[9];
142. state[9]=tmp;
143. }
144. }
145. }
146.  
147. void bb() {
148. int i , j , p , m;
149.  
150. if(cur_depth>=MAXDEPTH)
151. return;
152.  
153. if ( state[4] && state[7] && state[9] && state[10]) {
154.  
155. MAXDEPTH=cur_depth;
156. for(p=0;p<cur_depth;p++)
157. {soln[p].id=tmp_path[p].id , soln[p].clk_mov=tmp_path[p].clk_mov;}
158. for( m = 0 ; m < cur_depth ; m++ )
159. cerr<<"("<<tmp_path[i].id<<" "<<tmp_path[i].clk_mov<<") ";cerr<<endl;
160. tmp_depth=cur_depth;
161. }
162. for(i=0;i<3;i++) {
163. for(j=0;j<2;j++) {
164. move_one_step(i,j);
165. tmp_path[cur_depth].id=i,tmp_path[cur_depth].clk_mov=j;
166. cur_depth++;
167. bb();
168. com_back_one_step(i,j);
169. cur_depth--;
170. }
171. }
172. }
173.  
174.  
175. int main()  {
176.  
177. int t;
178. char inp[N];
179.  
180. scanf("%d",&t);
181. while(t--) {
182. cur_depth=0;
183. MAXDEPTH=MAX_D;
184. scanf("%s",inp);
185. for(int i=0;i<13;i++)
186. state[i+1]=inp[i]-'0';
187.  
188. /*for( i = 0 ; i < 13; i ++)
189. cerr<<"state[i]="<<state[i];*/
190. bb();
191. //cerr<<"tmp_depth="<<tmp_depth<<endl;
192. printf("%dn",tmp_depth);;
193. for(int i=0;i<tmp_depth;i++) {
194. printf("%d %dn",soln[i].id,soln[i].clk_mov);
195. }
196. //copy to dp_sols[]?
197. }
198. return 0;
199. }