Indeed your final solution in A is mathematically correct:
(1) There is a first row that contains one or more letter. For these letters,
the "up" will always stop at the first row, and "left" / "right" operations
performs in the same way as if the empty top rows are not present.
(2) "Left" and "right" operations guarantees to fill in the row (or block in
the cases below).
(3) For "down" operations, each block may or may not end up in the same row by
hitting the bottom or another letter. e.g.
XXXXXXXXXXXX
XXX XXXXXXX
X XXX
where "X" = filled by "left", "right", or "down" operation in row 1.
and " " = unprocessed (may be empty or not).
(4) Now start from the topmost row with " ". There must be at least one
unprocessed letter in the leftmost group of unprocessed places, as that is the
letter that blocked the "down" operation. If not, all " "s in that group should
have become "X"s by previous "down" actions.
(5) Repeat (2) and (3) for this small space. Another configuration similar to 3
is created, but this time more spaces is filled, e.g.
XXXXXXXXXXXX
XXXYYXXXXXXX
X YY XXX
where "X" = filled by "left", "right", or "down" operation in row 1.
"Y" = filled by "left", "right", or "down" operation in (4) and (5).
and " " = unprocessed (may be empty or not).
(6) Repeat (4) and (5). Since each application of (4) and (5) process at least
one unprocessed space, the whole board will be processed in a finite number of
steps.
(Note: sometimes no empty spaces are filled. But the processed letter still
counts as one unprocessed space, even without expanding into an empty space.)
P.S. I still don't know my submission for qualification-D is correct or not.
And don't think the simulation of C-small is much simpler than C-large. Without
math skills (sadly also for me) some part of the simulation would be wrong
anyway.
On Saturday, April 15, 2017 at 2:52:55 PM UTC, Bartholomew Furrow wrote:
> I tried this round at the end of a pretty tiring day, and discovered I had no
> working memory or ability to do math. Here's how to solve A without either of
> those things:
>
>
> 1. Iterate from top to bottom, from left to right. For each letter you find,
> see how big a rectangle you can make, first by growing it up, then left, then
> down, then right. Make many, many mistakes, including multiple off-by-ones.
> 2. Download the input and run your code. grep for ?. Find it in the case
> mentioned in the editorial.
> 3. Solve that case by hand and submit. Correct!
> 4. Go solve B (again making many, many mistakes).
> 5. Change the order in step 1 to growing the rectangle up, then left, then
> right, then down.
> 6. Generate 10,000 random cases. grep for ?. No results.
> 7. Download Large, run your code and submit. At the end of the contest:
> Correct!
> 8. Try to solve C-large. Don't switch to the simpler simulation of C-small
> until way too late.
>
>
> So there you go. If you can't think, blunder around until you get the
> problems right!
> Bartholomew
>
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/61c1ec96-2ce0-40e0-b292-7aa58e77d060%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
