You are not logged in. Please login at www.codechef.com to post your questions!

×

ARGTS2 – Editorial

PROBLEM LINK:

Practice
Contest

Author: Arkapravo Ghosh
Tester: Arkapravo Ghosh
Editorialist: Arkapravo Ghosh

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Dynamic Disjoint Set, Hash Map

PROBLEM:

We are given a number N. Now we are given M queries. The query of type 1 indicates that the numbers x and y are connected. The query of type 2 questions if the numbers a and b are connected together or not.

QUICK EXPLANATION:

We can use disjoint set data structure to efficiently answer the queries. Since the number N can be very large, we can’t use an array implementation of disjoint set, instead we need to use two hash-maps – one to keep track of the parent of each number and on for the size of each set.

EXPLANATION:

We need to use the hash-map implementation of disjoint set in this problem as the number N is very large. We need to keep the maps empty in the beginning. To process the queries efficiently, we will only store elements in the map when we encounter them in the queries. The is no necessity to use path-compression or union-by-rank to pass the test cases in the given time limit, but using it will reduce the execution time obviously.
If we use neither path-compression nor union-by-rank, the time complexity will be O(N). Using union-by-rank alone will reduce the time complexity to O(Mlog(n)), where n is the number of make-set operations, i.e. atmost (n-1) union operations. Using only path-compression alone will give a worst case running time of O(n + f(1 + log2+f/n n)), where n is the number of make-set operation, i.e. atmost (n-1) union operations and f is the number of find-set operations. Using both path-compression and union-by-rank will make the amortized time per operation to O(α(n)), where α(n) is the inverse Ackermann function.

AUTHOR'S AND EDITORIALIST'S SOLUTIONS:

Author's and editorialist’s solution can be found here.

This question is marked "community wiki".

asked 25 Sep, 20:38

horsbug98's gravatar image

4★horsbug98
3236
accept rate: 21%

edited 11 Oct, 17:14

admin's gravatar image

0★admin ♦♦
19.6k349497539

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×75
×75
×59
×2
×2

question asked: 25 Sep, 20:38

question was seen: 58 times

last updated: 11 Oct, 17:14