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 1063. Domino Puzzle

An easy task,and an easy WA task...
Posted by Yu Yuanming 21 Jun 2005 18:03
In fact, this problem is easy, don't be frighten by the low AC ratio...

When I read the description of this problem, I immediately thought it as a Euler Path problem.

I try to add some edges so that will form a Euler Path.

First, I add edges according to greedy strategy,but soon I learnt it was wrong, a simple calc proved it won't work.

As far as I know, there isn't exist a greedy algo...
(It you used it got AC, email me: yyming@hotmail.com )

In spite of this, my pro runs quickly, it got AC in 0.015 sec :)
http://acm.timus.ru/status.aspx?space=1&pos=865497
Re: An easy task,and an easy WA task...
Posted by Denis Koshman 1 Aug 2008 15:28
The algo is greedy once you connect all components