10103 - Karpovich blocks

[xenon]

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]

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]

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

[Alexander Denisjuk]

Everything is right, but

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]

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]

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

Yes.
To my mind.

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

[oriol78]

Bloks of NxNxN ....

your input is a bad input

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

but i think u r right in general

[..]

Can anyone provide some more input?
This problem confuse me for a long time, I still don't know why I get WA

[minskcity]

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?

[..]

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

[minskcity]

It must be a challenge choosing an easy problem to solve when you only have 33 problems to choose from...

[..]

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.

[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?

[minskcity]

Your algorithm is correct. And yes, this problem is not hard.