ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1549. Another Japanese Puzzle

strange problem
Posted by svr 11 Mar 2008 21:33
I considered some constructions and got AC.
But full analysis of the problem seems equals to scintific reserch. For this problem all timus correspondents
very need in short, proven and full consideration
but this is just mathematic vork.
I know only: L-R==4; F==2*k- it's absolutely clear.
Case F==0 possible only if 1) L=4;R=0
2) R=2*k,L=R+4;k>=2.
I think but failed to prove that cases F==0,L==6;R==2
impossible also as if F==0,R=2*k+1;L=R+4;
Cases when F=2*k>0 ,L=R+4,R>0 all possible, simple
and depend on regular constructions.
Resume:On olimpiads often impossible to have full
foundations for your algorithms.
Re: strange problem
Posted by Janez Brank 2 Oct 2013 15:07
I agree that proving the correctness of your solution is
a bit time-consuming for this task.  Nevertheless, in the
end the proof isn't that complicated, so I'll post it here
in case someone finds it interesting.

Suppose that we managed to position the plates (s straight
segments and t turns) on the plane so that the line segments
on them form a closed path.  Let's introduce a coordinate
system so that each plate can be described by a pair of
integers (X, Y) giving the coordinates of its lower left
corner.  Let's start at any point in our closed path and
traverse the entire path until we get back to the point where
we started.  At each point where we enter a new plate,
let's look at the coordinates (X, Y) of the plate we're
entering, and let's record a triple (x, y, d), where
x = X mod 2, y = Y mod 2, and d is the direction we're facing
at this particular point (one of N, W, S, E).

If we know the triple (x, y, d) at the time we entered
a plate, and if we know whether that plate is a left turn,
a right turn, or a straight one, we can easily determine
the triple that we'll get at the time we leave this plate
and enter the next one.  Thus for example, from 00N,
a left turn takes you into 10W, a right turn takes you into
10E, and a straight segment takes you into 01N.
If we keep computing possible transitions, we end up with
a kind of state transition diagram with 16 possible states.

I can't draw the diagram nicely here, but we can approximate
it by arranging the states into a 4*4 grid:

  00N 00S 01N 01S
  10W 10E 00W 00E
  11S 11N 10S 10N
  01E 01W 11E 11W

The transitions between states are very systematic:

(1) A straight segment changes the state so that you remain
in the same row, but move from the first column to the third
(or vice versa), or from the second column to the fourth
(or vice versa).

(2) If you are in the left half of the grid (first two columns),
a left turn moves you one row down (or from the fourth row back
to the first one) but leaves you in the same column.
A right turn moves you one row down as well, but it also switches
you from the first to the second column and vice versa.

(3) If you are in the right half of the grid (third and fourth column),
a right turn moves you one row up (or from the first row into
the fourth row) and leaves you in the same column.
A left turn moves you one row up as well, but it also switches
you from the third to the fourth column and vice versa.

Of course, if our path is truly closed, we will finish
in the same state where we started.  We can assume without loss
of generality that this state is 00N -- if it wasn't, we could
always move and rotate the entire path (i.e. all the plates)
a little bit.

From (1) it follows that every straight segment moves us from
the left half of the grid to the right one or vice versa.
Since we started on the left half (in 00N) and have to finish
there as well, it follows that the number of straight segments,
i.e. s, must be even.

From (2) and (3) it follows that every turn moves us from
an odd row to an even row or vice versa.  Since we started
in the first row (in 00N) and must finish in the same row,
it follows that the number of turns, i.e. t, must be even.

We can also notice that a turn will always change the direction
(the third character in our state) while a straight segment
will leave it unchanged.  For the path to be closed, we must
be facing each of the four possible directions at some point,
so we require at least four turns; thus t has to be >= 4.

Now let's consider the special case when s = 0, i.e. there
are no straight lines.  Only the first two columns of our
state grid are reachable (from 00N) in that case, and each
turn we take moves us from the current row to the next row
below it.  Since we started in the first row and must finish
in the  first row as well, it follows that in this case t must
be a multiple of 4.

So, to summarize what we've seen so far:
- s and t must be even
- t must be >= 4
- if s = 0, then t must be a multiple of 4.

Nearly all (s, t) that meet these constraints can be solved
if we start by manually constructing solutions for cases where
s = 0 and t = 4 or 16; and also for cases where s = 2 and
t = 6 or 8 or 10.  It is also easy to extend these paths by
inserting 2 straight segments at a time, or by inserting 8 turns
at a time.  The only case which remains unsolved by these
constructions is s = 0, t = 8.  It turns out that no closed path
exists with 8 turns and 0 straight segments, but I don't have
an elegant proof of this (it is however easy to verify it with
a program, using recursion).