10503 - The dominoes solitaire

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

Moderator: Board moderators

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

10503 - The dominoes solitaire

Post by dwyak » Tue Jul 22, 2003 4:00 pm

the rules of dominoes: the number of adjacent dots on two different dominoes must coincide. Pieces with repeated values are placed in the same way as the other pieces, and not at right angels.

what does "dots" & "values" mean? i didn't find anywhere contains description of "dots" & "value".

thanks!

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sun Aug 31, 2003 1:11 pm

Can this problem be solved by some quick approach? :-?
Is backtracking the only way?
Last edited by Observer on Sun Aug 31, 2003 3:05 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Sun Aug 31, 2003 1:21 pm

What do you mean by a quick approach?
It seems backtracking works pretty fast.. I used a simple DP and got 1.8secs, and I'm the SLOWEST ;)
JongMan @ Yonsei

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Sun Aug 31, 2003 2:19 pm

i use backtracking, it quite fast, < 0.1 sec :). so backtracking is more than enough.
Kalo mau kaya, buat apa sekolah?

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sun Aug 31, 2003 3:04 pm

Thx I've got ACC. I use backtracking too, and my program runs for 0.01s only. Not bad for a Pascal program, eh? :D

Btw, backtracking problems are fun! Please, if there are any other problems that can be solved by backtracking, tell me.

Some problems that can be solved by backtracking/exhaustion by recursion are listed below
(Of course, some of them could be solved with the help of DP) :
00140 Bandwidth
00165 Stamps
00167 Sultan's Successors, the
00193 Graph Colouring
00195 Anagrams
00216 Getting in Line
00259 Software Allocation
00291 House of Santa Claus, the
00296 Safebreaker
00301 Transportation
00399 Another Puzzling Problem (* the 500th problem that i've solved! *)
00441 Lotto
00524 Prime Ring Problem
00539 Settlers of Catan
00565 Pizza Anyone?
00574 Sum It Up
00598 Bundling Newspapers
00628 Passwords
00639 Don't Get Rooked
00656 Optimal Programs
00729 Hamming Distance Problem
00732 Anagrams by Stack
00750 8 Queens Chess Problem
10063 Knuth's Permutation
10068 Treasure Hunt, the
10098 Generating Fast, Sorted Permutations
10186 Euro Cup 2000
10344 23 out of 5
10364 Square
10400 Game Show Math
10419 Sum-up the Primes
10422 Knights in FEN
10447 Sum-up the Primes II
10496 Collecting Beepers
10501 Simplified Shisen-Sho
10503 Domino Solitaire, the
10513 Bangladesh Sequences
10582 ASCII Labyrinth
10605 Mines for Diamonds
10637 Coprimes

[Keywords] exhaustion backtracking Pascal easy recursion problems

(p.s. how i like this abandoned topic. my free area :p)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Re: What does 10503 mean?

Post by wyvmak » Fri May 07, 2004 8:44 am

dwyak wrote:what does "dots" & "values" mean? i didn't find anywhere contains description of "dots" & "value".
one piece of domino has two "values", say (0,1). there are "dots" to represent the "value", so on the domino there is one dot for "1". just like a dice.

It took me some time to figure out the problem. And, finally, I treat the problem as: determining there exists a (directed) chain from (i1,i2) to (d1,d2).

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

10503-The dominoes solitaire

Post by TISARKER » Sat Nov 19, 2005 3:38 am

the rules of dominoes: the number of adjacent dots on two different dominoes must coincide. Pieces with repeated values are placed in the same way as the other pieces, and not at right angels.
Plase Clarify Above Lines.
Mr. Arithmetic logic Unit

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Thu Aug 09, 2007 6:59 pm

Hello..~
What is the correct output for this input..?

Code: Select all

1
1
1 2
3 4
3 2
1
1
1 2
3 4
1 3
0
Thanks.. :-)

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Aug 09, 2007 7:29 pm

My accepted code returns 'NO' for both cases. [However, I forgot the problem completely]
Ami ekhono shopno dekhi...
HomePage

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Fri Aug 10, 2007 5:00 am

Thanks a lot..
Now, I understand the problem.. :-)

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Tue Aug 28, 2007 6:21 pm

I finally got AC on this problem..
But, my AC code returns..

Code: Select all

YES
NO
for my test case above..

Maybe, we're allow to rotate dominos except for the initial ones..

frznlich
New poster
Posts: 1
Joined: Sun Mar 11, 2012 11:54 am

Re: 10503 - The Dominoes Solitaire

Post by frznlich » Mon Jun 11, 2012 1:00 am

Hi, can someone provide me with critical testcases?

I've tried all the above testcases, and still got WA. Thank you :)

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10503 - The Dominoes Solitaire

Post by brianfry713 » Tue Jun 12, 2012 12:15 am

Generate some input that you'd like the AC output for.
Check input and AC output for thousands of problems on uDebug!

tiendaotd
New poster
Posts: 12
Joined: Mon Jan 14, 2013 12:21 pm

Re: 10503 - The Dominoes Solitaire

Post by tiendaotd » Tue Feb 19, 2013 8:37 am

For those who got WA : a domino (a,b) can provide (a,b) or (b,a) but only one of them is available. Therefore, when you already used (a,b) ( or (b,a) ) , it's impossible to use (b,a) ( or (a,b) ) in further spaces.

This simple logic may looks like that :

Code: Select all

// S : second
// idx : space index
if(a[i].F == line[idx-1].S)
			{
				use pair (a[i].F, a[i].S) ;
			}
			else if(a[i].S == line[idx-1].S)
			{
				use pair (a[i].S, a[i].F) ;
			}
...
                                       avail[i] = 0 ;
					line[idx] = pair used above;
					backtrack(idx+1) ;	
					avail[i] = 1 ;

Munchor
New poster
Posts: 19
Joined: Sun Mar 03, 2013 4:03 pm

Re: 10503 - The Dominoes Solitaire

Post by Munchor » Tue Mar 19, 2013 1:51 am

I'd just love some critical input for this one. I get correct output for the example, but WA on UVa:

Code: Select all

#include <stdio.h>
#include <string.h>

using namespace std;

unsigned int n, m, i, u, filled;
unsigned int first[2];
unsigned int last[2];
unsigned int dominoes[15][2];
unsigned int used[20];
bool problem_solved;

void place_from(int j, int to_match)
{
  //printf("%d %d %d\n", to_match, dominoes[j][0], dominoes[j][1]);

  if (filled == n - 1)
  {
    if (to_match == last[0])
    {
      problem_solved = true;
    }

    return;
  }

  filled++;
  
  for (u = 0; u < m; u++)
  {
    if (u == j || used[u]) continue;

    if (dominoes[u][0] == to_match)
    {
      used[u] = 1;
      place_from(u, dominoes[u][1]);
      used[u] = 0;
    }
    else if (dominoes[u][1] == to_match)
    {
      used[u] = 1;
      place_from(u, dominoes[u][0]);
      used[u] = 0;
    }
  }

  filled--;
}

int main()
{
  while (true)
  {
    scanf("%d", &n);
    if (n == 0) break;

    scanf("%d", &m);
    memset(dominoes, 0, sizeof dominoes);
    problem_solved = false;

    scanf("%d %d", &first[0], &first[1]);
    scanf("%d %d", &last[0], &last[1]);

    for (i = 0; i < m; i++)
    {
      scanf("%d %d", &dominoes[i][0], &dominoes[i][1]);
    }

    for (i = 0; i < m; i++)
    {
      memset(used, 0, sizeof used);
      filled = 0;

      if (dominoes[i][0] == first[1])
      {
        used[i] = 1;
        filled++;
        place_from(i, dominoes[i][1]);
      }
      else if (dominoes[i][1] == first[1])
      {
        used[i] = 1;
        filled++;
        place_from(i, dominoes[i][0]);
      }

      if (problem_solved) break;
    }

    if (problem_solved)
      printf("YES\n");
    else
      printf("NO\n");
  }

  return 0;
}
Any ideas? Thanks in advance.

Post Reply

Return to “Volume 105 (10500-10599)”