Page 1 of 2

10103 - Karpovich blocks

Posted: Fri Jul 12, 2002 3:13 pm
by xenon
I'm having a real hard time understanding what the problem description means exactly, and what we are required to answer :evil:
So please, people who solved it (5), help me out.

[quote]From the unit blocks of three kinds one creates a cube N

Posted: Wed Sep 04, 2002 11:23 am
by Alexander Denisjuk
so the following 'crate' is illegal:

Code: Select all

RB 
BR 

GG 
GG 
Am I right?
Yes, as I can see.

(R should precede G, G precedes B).

My most plausible explanation of this literary masterpiece (out of many) kan be formalised as:

Code: Select all

try if the R-detail comes lose;
..................
No, the remark in parentheses shoud be interpreted only as the order od kinds (RGB) in output line, not in the separation procedure. As I understand, you can try to separate any detal, then any other, then you can turn back tothe first , etc.
But I have equal valid reasonings leading to:
RGB, RGB, R, G
RGB, GRB, R, G
No, GRB is not valid, since in output
(R should precede G, G precedes B).
Your question is really long, so excuse, if I did not answer all the questions.

I know the author of the problem, so if you suggest an impovement of the problem description, you can discuss it with him. And, perhaps, you will submit a new one.

Posted: Thu Sep 05, 2002 7:43 am
by xenon
Thank you for your answer!

So let me sum up to see if I understand the question now:

- After the glueing there are exactly three details, one R, one G and one B. The unitblocks of which they are made of are all interconnected and every kind is present.
- The order in which the details come lose is irrelevant.

This means that there are 5 possible answers: "NO", "R", "G", "B" and "RGB", right? (if two details come lose, the third is lose automatically).

Well, this is what I implemented, but I still get WA. So either I still don't understand the problem or my programming is wrong.

Perhaps someone can supply more input cases?

-xenon

Posted: Sat Sep 07, 2002 10:22 am
by Alexander Denisjuk
Everything is right, but
xenon wrote: if two details come lose, the third is lose automatically.
-xenon
You can imagine two details that cannot lose and one more unit blok, OK?

For instance,

RRG
RRR
RRR

RRR
RBR
RRR

RRR
RRR
RRR

Posted: Tue Sep 10, 2002 5:46 pm
by Yarin
Alexander Denisjuk wrote:Everything is right, but
For instance,

RRG
RRR
RRR

RRR
RBR
RRR

RRR
RRR
RRR
Shouldn't the answer be just G in that case?

Posted: Thu Sep 12, 2002 11:32 am
by Alexander Denisjuk
Shouldn't the answer be just G in that case?
Yes.
To my mind.

I found some different example

Posted: Thu Aug 07, 2003 5:36 am
by Sanghack
RRR
RRR
RRR
RRR

RRR
RGR
RBB
RRR

RRR
RRR
RRR
RRR

In this case, only detail 'B' can be separated first,

and then, G can move down (in this view), right and right.
(or R move up, left, and left.

Did you test this thing? (I'm programming now so I test nothing.)

Posted: Fri Sep 26, 2003 1:18 pm
by oriol78
Bloks of NxNxN ....

your input is a bad input

(sorry my english is poor, i know my answer is poor too :-P)

but i think u r right in general

Posted: Sun Feb 15, 2004 9:29 am
by ..
Can anyone provide some more input?
This problem confuse me for a long time, I still don't know why I get WA :(

Posted: Fri Mar 26, 2004 4:04 am
by minskcity
.. wrote:Can anyone provide some more input?
This problem confuse me for a long time, I still don't know why I get WA :(
Do you try to rotate the pieces?

Posted: Wed Mar 02, 2005 9:08 pm
by ..
After a long long time, I get AC at last.
Actually the algorithm is not so complicate(only do translation of the blocks, no rotation is needed), but it needs careful implementation.

My algorithm has a stupid bug, say, when I move a detail to right, I will delete the part which is out of the range [0,N). But I forget to forbid moving the detail back towards left, this will make the detail smaller than its original and lead to false positive case......... :oops:

Posted: Wed Mar 02, 2005 9:41 pm
by minskcity
It must be a challenge choosing an easy problem to solve when you only have 33 problems to choose from... :wink:

Off topic :)

Posted: Wed Mar 02, 2005 9:53 pm
by ..
minskcity wrote:It must be a challenge choosing an easy problem to solve when you only have 33 problems to choose from... :wink:
No, I have 59 to choose, but everyone is also difficult/troueblesome/painful for me to solve.

Posted: Thu Apr 28, 2005 12:39 am
by Abednego
I don't think this question has been answered yet: Are these the only valid outputs: "NO", "R", "G", "B", "RGB"?

I don't think this problem is very hard (anymore). First, I simply check if I can move any piece. If yes, then I completely erase that piece - it can be removed along a straight line. Then I only have 2 pieces to worry about, and I run DFS to see which of the configurations are acceptable. If I can find a reachable position that is at least 10 units away in one dimension, then the two pieces can be separated, and I print "RGB".

Is there something wrong with the algorithm? Or did I simply make a dumb coding mistake somewhere?

Posted: Thu Apr 28, 2005 7:47 pm
by minskcity
Your algorithm is correct. And yes, this problem is not hard.