10103 - Karpovich blocks

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10103 - Karpovich blocks

Post by xenon » Fri Jul 12, 2002 3:13 pm

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

Alexander Denisjuk
New poster
Posts: 35
Joined: Sat Jan 05, 2002 2:00 am
Contact:

Post by Alexander Denisjuk » Wed Sep 04, 2002 11:23 am

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

Post by xenon » Thu Sep 05, 2002 7:43 am

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

Post by Alexander Denisjuk » Sat Sep 07, 2002 10:22 am

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:

Post by Yarin » Tue Sep 10, 2002 5:46 pm

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:

Post by Alexander Denisjuk » Thu Sep 12, 2002 11:32 am

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

Post by Sanghack » Thu Aug 07, 2003 5:36 am

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

Post by oriol78 » Fri Sep 26, 2003 1:18 pm

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

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

Post by .. » Sun Feb 15, 2004 9:29 am

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:
  • Please make discussion about the algorithm BRFORE posting source code.
    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

Post by minskcity » Fri Mar 26, 2004 4:04 am

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

Post by .. » Wed Mar 02, 2005 9:08 pm

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:
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    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

Post by minskcity » Wed Mar 02, 2005 9:41 pm

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

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

Off topic :)

Post by .. » Wed Mar 02, 2005 9:53 pm

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.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu Apr 28, 2005 12:39 am

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

Post by minskcity » Thu Apr 28, 2005 7:47 pm

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

Post Reply

Return to “Volume 101 (10100-10199)”