## 11504 - Dominos

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am

### 11504 - Dominos

I thought the time limit was a bit harsh during the contest. My Java solution was linear in the size of the input and kept timing out.

But, when I heard what kind of solution passed, I realized that the test data was bad, too.

Here is the test case:

Code: Select all

``````1
6 6
1 2
2 3
3 1
4 5
5 6
6 4``````
You obviously need 2, but the accepted solution says one.

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### Re: 11504 - Dominos

What's the algorithm for solving this problem? During the contest I tried with DFS, marking nodes as either standing, knocked down by hand, or knocked down by another tile.

This gave me lots of wrong answers, perhaps related with what Darko said because my program outputs 2 in the case above.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

### Re: 11504 - Dominos

I was using union-find algorithm at the contest. But I got several WA's. I think my program failed in handling reversible connection (i.e. 1->2 and 2->1).

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am

### Re: 11504 - Dominos

Maybe something to do with the note in your signature? I don't know how big Pascal stack is, but I got RTE when I tried DFS in Java.

I went through all connected components and counted nodes with indegree 0. If there were none, I would add one. That timed out and it's linear in number of edges, so I gave up after trying to optimize it for a while.

My accepted solution in C is incorrect, it subtracts from n for any new domino that is second in the pair, not taking care of any disjoint cycles.

wahaha
New poster
Posts: 16
Joined: Mon Jul 14, 2008 6:18 pm

### Re: 11504 - Dominos

jan_holmes wrote:I was using union-find algorithm at the contest. But I got several WA's. I think my program failed in handling reversible connection (i.e. 1->2 and 2->1).

i use union-find algorithm , and i got WA too . i think this algorithm is correct , but why i got wrong ?

wahaha
New poster
Posts: 16
Joined: Mon Jul 14, 2008 6:18 pm

### Re: 11504 - Dominos

i got it and AC now.

someone who got WA can use this test:

input:
1
5 4
1 2
3 2
2 4
2 5
output:
2

Anindya
New poster
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA

### Re: 11504 - Dominos

For the following input:

Code: Select all

``````1
10 13
1 2
2 1
3 4
4 3
5 6
6 5
4 6
7 8
8 7
9 10
10 9
5 10
10 1
``````
the output should be 2.
AC code outputs 3.
The input is taken from waterloo site.
Then how the case is not included in UVa?

wahaha
New poster
Posts: 16
Joined: Mon Jul 14, 2008 6:18 pm

### Re: 11504 - Dominos

Anindya wrote:For the following input:

Code: Select all

``````1
10 13
1 2
2 1
3 4
4 3
5 6
6 5
4 6
7 8
8 7
9 10
10 9
5 10
10 1
``````
the output should be 2.
AC code outputs 3.
The input is taken from waterloo site.
Then how the case is not included in UVa?

OMG, i think we should calculate SCC(strongly connected components) first ?

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### Re: 11504 - Dominos

Darko wrote:Maybe something to do with the note in your signature? I don't know how big Pascal stack is, but I got RTE when I tried DFS in Java.
The thing is I used C++ during the contest.
Darko wrote: I went through all connected components and counted nodes with indegree 0. If there were none, I would add one. That timed out and it's linear in number of edges, so I gave up after trying to optimize it for a while.
When you traversed the connected components, did you consider the graph directed or not directed?

Here's an explanation of my algorithm:
Try to knock down by hand each tile, and the knock down all connected tiles. If at any moment a tile can knock down another tile that was already knocked down by hand, then this second tile didn't need to be knocked down by hand (Except if it is the root, in which case we have seen a cycle that points back to the root, and the root must be knocked down by hand to start the domino effect).

Here's my DFS code:

Code: Select all

``````using namespace std;
#include <iostream>
#include <vector>

const int N = 100005;

vector<int> g[N];
int color[N];

enum { standing, tiled, handed };

void dfs(int u, int root){
if (color[u] != standing) return;

if (u == root) color[u] = handed;
else color[u] = tiled;

vector<int> &out = g[u];
for (int k=0, m=out.size(); k<m; ++k){
int v = out[k];
if (color[v] == handed && v != root) color[v] = tiled;
else if (color[v] == standing) dfs(v, root);
}
}

int main(){
int t;
for(cin >> t; t--;){
int n, m; cin >> n >> m;
for (int i=0; i<=n; ++i) g[i].clear(), color[i] = standing;
for (int u, v, i=0; i<m && cin >> u >> v; ++i) g[u].push_back(v);
for (int i=1; i<=n; ++i) if (color[i] == standing) dfs(i, i);

int ans = 0;
for (int i=1; i<=n; ++i) ans += (color[i] == handed);

cout << ans << endl;
}
return 0;
}

``````
I've tried it on all Waterloo official input files and it only fails in this (huge ~ 4.4MB) input.
It produces 238 instead of the correct 237 in a single case.

Can somebody spot the bug? I don't know why it fails, but I suspect it is something related with cycles.

Edit:
Voilà! My code fails on this input:

Code: Select all

``````1
4 4
1 2
2 3
3 1
4 2
``````
Correct answer is 1, knock down tile 4. But my programs outputs 2!
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

asmaamagdi
New poster
Posts: 27
Joined: Tue Dec 20, 2005 9:14 am
Location: Egypt

### Re: 11504 - Dominos

wahaha wrote:
jan_holmes wrote:I was using union-find algorithm at the contest. But I got several WA's. I think my program failed in handling reversible connection (i.e. 1->2 and 2->1).

i use union-find algorithm , and i got WA too . i think this algorithm is correct , but why i got wrong ?
That's because union-find is for undirected graphs and this is a directed graph here. For example a case like this:
3 2
1 2
3 2
union-find algorithm will give you 1 while it should be 2.
---
Asmaa Magdi

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### Re: 11504 - Dominos

I finally got accepted, here's the algorithm I used:

Find the strongly connected components of the graph. I used the two-pass DFS algorithm explained in Cormen's book.
The answer is the number of these components that do not have an incoming connection from a different component.
In other words, the number of strongly connected components with in-degree == 0.

But my program is slow, 1.670 seconds. I would like to know how other people solved this problem in less than a second. Can you PM your code?
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

Dmytro Korzhyk
New poster
Posts: 8
Joined: Sat Dec 20, 2003 12:57 pm
Location: Duke University, NC

### Re: 11504 - Dominos

My simple C++ implementation of Kosaraju's algorithm runs in 0.7 sec, so yours is probably slower because of language. What language do you use?

EDIT: oh, I see you code in C++. So it might be because of cin/cout instead of scanf/printf.

New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:

### Re: 11504 - Dominos

My AC solution is failed with darko's case

Code: Select all

``````1
6 6
1 2
2 3
3 1
4 5
5 6
6 4
``````
My AC code gives 2 instead of one. But this one give AC during contest

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am

### Re: 11504 - Dominos

Correct answer is 2. I was just pointing out that my AC solution would fail that case (as it later did, when they rejudged this problem).

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

### Re: 11504 - Dominos

I wonder what is the answer for the following test case :

Code: Select all

``````1
10 5
1 2
2 5
3 4
1 3
2 3
``````
Is it 5 ?

EDIT : I got it now. It must be 6.