hiddentesla's blog

need help in a union-find problem
By hiddentesla, history, 8 years ago, In English

so yesterday i just learned the union-find data structure, and i found this problem: https://open.kattis.com/problems/almostunionfind

my approach is as following: implement basic union-find, but also add array sum[] for the sum of the group and freq[], the number for elements in the group

i also "made" the group using a vector of vector, so if there is a group {1,3,5} and 1 is the leader, the representing vector is

{1,3,5} or {1,5,3} (leader is always in the front, other element is random depending on the union, the function of this is for the "2" function, where how i handle it is i first find the "leader" of the group (lets call it indeks i), then the element must be in v[i], so i erase the element from the vector, make the next first element in the vector the leader and adjust the rest of the vector, if the leader of the new vector (lets call it indeks j) is not i, swap it the vector i with vector j clear vector i;

my code: https://ideone.com/vZVvCn

however, im getting WA :( and i tried to debug it but no luck, can someone point out a counter case?

also, if there is a more optimal approach then my approach, please give me hints

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

bumping...

→ Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Disclaimer: Nobody's helped for three days so I'll try my best, but I'm tipsy so excuse me if the explanation is bad.

So, your code actually doesn't produce WA — it straight up crashes (on my PC at least). What actually confuses me is that you ask for a counter case — when the sample input is your counter case. You can check in the IDEONE you yourself linked that your output is not the sample output ("1 3" on last query instead of the correct "2 8"). This is due to undefined behaviour, and I can only guess that on your PC it actually produced the correct output.

Now your mistake is quite simple — your vector of vectors v is indexed from 0, while the elements are indexed from 1. You fill v in your first loop:

for(temp=1;temp<=m;temp++)
{
	parent[temp]=temp;
	sum[temp]=temp;
	freq[temp]=1;
	vector<int> t;
	t.push_back(temp);
	v.push_back(t);
}

Since it's initially an empty vector obviously the indexing starts from 0. So in our sample test v[5] would actually be undefined and any access to it yields undefined behaviour.

The bad news are — the solution is slow. If you have some large vector and you apply operation 2 on it a lot of times, your complexity seems to be quadratic. I'll give my solution in a spoiler if you want to take a look. There's probably a much better one but this is the best I could come up with at 4 in the morning:

Solution
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ok, so i attempted the problem using set and taking your idea using arr groupid[]: https://ideone.com/c8agkn

    but i am getting RTE, and debugging it myself fails :( a little help?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 5   Vote: I like it +1 Vote: I do not like it

      Extremely simple mistake — on line 15 the size of array s should be m+1 instead of n+1. That causes you to sometimes go out of bounds and RTE. Other than that it should work.

      Using sets is indeed easier to implement and understand, but adds an additional log factor to the complexity. Amortized per query should still work quick enough, though (7s time limit is huge).

      → Reply