11504 - Dominos

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

Moderator: Board moderators

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

11504 - Dominos

Post by Darko » Sat Sep 27, 2008 11:47 pm

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.

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

Re: 11504 - Dominos

Post by andmej » Sun Sep 28, 2008 3:15 am

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

Post by jan_holmes » Sun Sep 28, 2008 5:38 am

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
Location: Calgary, Canada

Re: 11504 - Dominos

Post by Darko » Sun Sep 28, 2008 5:43 am

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

Post by wahaha » Sun Sep 28, 2008 6:42 am

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

Post by wahaha » Sun Sep 28, 2008 7:25 am

i got it and AC now. :D

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

Post by Anindya » Sun Sep 28, 2008 8:05 am

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

Post by wahaha » Sun Sep 28, 2008 10:58 am

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?


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

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

Re: 11504 - Dominos

Post by andmej » Sun Sep 28, 2008 7:43 pm

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

Post by asmaamagdi » Mon Sep 29, 2008 1:19 am

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

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

Re: 11504 - Dominos

Post by andmej » Mon Sep 29, 2008 2:49 am

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

Post by Dmytro Korzhyk » Thu Oct 02, 2008 12:40 am

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.

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

Re: 11504 - Dominos

Post by marcadian » Thu Oct 02, 2008 9:19 am

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 :D

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

Re: 11504 - Dominos

Post by Darko » Thu Oct 02, 2008 12:34 pm

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

Post by jan_holmes » Sat Oct 04, 2008 2:16 pm

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 : :oops: I got it now. It must be 6.

Post Reply

Return to “Volume 115 (11500-11599)”