ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1878. Rubinchik's Cube

WA3
Posted by morbidel 22 Oct 2011 16:05
Any hint for WA3?
Re: WA3
Posted by Anil Kishore 22 Oct 2011 16:21
'm stuck with WA5 :(
Re: WA3
Posted by ZARHANE 22 Oct 2011 17:41
I have WA40 !
Re: WA3
Posted by Strekalovsky Oleg [Vologda SPU #1] 23 Oct 2011 23:43
Anil Kishore wrote 22 October 2011 16:21
'm stuck with WA5 :(
Don't forget rotate clockwise and anticlockwise at one step!
Re: WA3
Posted by morbidel 24 Oct 2011 16:20
Yes, rotating just 90 degrees in either directions takes one step. What's the trick here?
Re: WA3
Posted by MOPDOBOPOT (USU) 25 Oct 2011 13:49
This test helped me to overcome WA3:

4 2 2 3
3 1 4 1
3 2 3 1
1 4 4 2

The answer is 4. Because collect '4' needs 5 steps, but collect '1' needs only 4 steps.
Re: WA3
Posted by morbidel 25 Oct 2011 15:15
I made a classic backtracking which gets WA3 and also a Greedy who also gets WA3, which works as follows:
- assume the square is solved with 1 in the upper left corner, compute the orientation of each of the layers (0 if ok, 1 or 3 if with a rotation we reach 1 in the corner, 2 if with 2 rotations).
- now try to rotate the layers to achieve the color i in the upper left corner
- so for each layer determine the minimal nr. of steps to move the color i from layer j in its correct position
- compute the minimal number of moves to reach the solution with color i in upper-left
- print the minimum out of those values

Edited by author 25.10.2011 15:22
Re: WA3
Posted by morbidel 26 Oct 2011 00:00
I figured out the test #3, it has T[0][0] = 2, T[0][1] = T[1][0] = 1, T[1][1] = 3, "if (...) while(1);" did the trick.
So the whole table I assume is
2 1 2 4
1 3 1 2
3 4 2 4
1 3 4 3
My program outputs 2 as a minimum (rotate layer 4 clockwise with 90, rotate layer 3 anti-clockwise with 90), resulting a solved cube with 1 in its left corner. The judge answer is 3, but I don't understand why.
Am I missing something?

Edited by author 26.10.2011 00:04
Re: WA3
Posted by morbidel 27 Oct 2011 01:13
AC at last! The problem in my solution was that I assumed always that the colors were 1-red, 2-yellow, 3-green, 4-blue, but they say that one number is one color so they could be permuted in any way.

Edited by author 27.10.2011 01:55
Re: WA3
Posted by Lucian Ilea 7 Nov 2011 21:37
My AC program gives 2 as the answer for:
2 1 2 4
1 3 1 2
3 4 2 4
1 3 4 3
Re: WA3
Posted by Soucup Adrian 29 Jun 2012 20:52
Lucian Ilea wrote 7 November 2011 21:37
My AC program gives 2 as the answer for:
2 1 2 4
1 3 1 2
3 4 2 4
1 3 4 3

Strange. Mine gives 3. (Also AC).

Edited by author 29.06.2012 20:52
Re: WA3
Posted by Squire [Lviv NU] 29 Aug 2012 23:21
Soucup Adrian wrote 29 June 2012 20:52
Lucian Ilea wrote 7 November 2011 21:37
My AC program gives 2 as the answer for:
2 1 2 4
1 3 1 2
3 4 2 4
1 3 4 3

Strange. Mine gives 3. (Also AC).

Edited by author 29.06.2012 20:52
Re: WA3
Posted by Squire [Lviv NU] 29 Aug 2012 23:31
MOPDOBOPOT (USU) wrote 25 October 2011 13:49
This test helped me to overcome WA3:

4 2 2 3
3 1 4 1
3 2 3 1
1 4 4 2

The answer is 4. Because collect '4' needs 5 steps, but collect '1' needs only 4 steps.
You're wrong. The answer is equal for every colour cause you cann't collect only one colour but all the colours together.
To collect '4' you must turn left inner square and turn right two outer squares each for 1 time. So we have 3 steps in sum.
P. S. Sorry for bad english (

Edited by author 29.08.2012 23:31

Edited by author 29.08.2012 23:31

Edited by author 29.08.2012 23:33
Re: WA3
Posted by MOPDOBOPOT (USU) 30 Aug 2012 00:09
If we turn squares as you said we will get this situation:

4 3 3 3
4 4 3 2
4 1 2 2
1 1 1 2
Re: WA3
Posted by Squire [Lviv NU] 30 Aug 2012 01:16
MOPDOBOPOT (USU) wrote 30 August 2012 00:09
If we turn squares as you said we will get this situation:

4 3 3 3
4 4 3 2
4 1 2 2
1 1 1 2
Yes, you're right )))
We need one more step - turn right the square which includes element table[3][1]. So, the answer is 4.
Re: WA3
Posted by inatial_D 5 Mar 2013 16:55
ac is reached just using 4 elements in inputs.
Re: WA3
Posted by tepamid 2 Jul 2019 19:32
Mine gives 2 and I got AC for this input:

2 1 2 4
1 3 1 2
3 4 2 4
1 3 4 3

Edited by author 02.07.2019 19:33
Re: WA3
Posted by maslowmw 17 May 2020 00:33
But this test incorrect, because always colours order 1-2-3-4
IN this tet 1-2-4-3.
My AC solution also gives 3.