11504 - Dominos

[Darko]

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]

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.

[jan_holmes]

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]

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]

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]

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]

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]

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]

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.

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!

[asmaamagdi]

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.

[andmej]

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?

[Dmytro Korzhyk]

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]

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]

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]

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.