## 10103 - Karpovich blocks

Moderator: Board moderators

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

### 10103 - Karpovich blocks

I'm having a real hard time understanding what the problem description means exactly, and what we are required to answer
So please, people who solved it (5), help me out.

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

Alexander Denisjuk
New poster
Posts: 35
Joined: Sat Jan 05, 2002 2:00 am
Contact:
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.

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

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

Alexander Denisjuk
New poster
Posts: 35
Joined: Sat Jan 05, 2002 2:00 am
Contact:
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

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
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?

Alexander Denisjuk
New poster
Posts: 35
Joined: Sat Jan 05, 2002 2:00 am
Contact:
Shouldn't the answer be just G in that case?
Yes.
To my mind.

Sanghack
New poster
Posts: 16
Joined: Wed Jul 17, 2002 5:55 pm
Location: Seoul, Korea

### I found some different example

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

oriol78
New poster
Posts: 32
Joined: Mon Mar 31, 2003 7:39 pm
Bloks of NxNxN ....

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

but i think u r right in general

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Can anyone provide some more input?
This problem confuse me for a long time, I still don't know why I get WA
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
.. 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?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
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.........
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
It must be a challenge choosing an easy problem to solve when you only have 33 problems to choose from...

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

### Off topic :)

minskcity wrote:It must be a challenge choosing an easy problem to solve when you only have 33 problems to choose from...
No, I have 59 to choose, but everyone is also difficult/troueblesome/painful for me to solve.
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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?
If only I had as much free time as I did in college...

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
Your algorithm is correct. And yes, this problem is not hard.