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

×

CodeSprint India : Island Queries Approach

As asked by few people on facebook, I am posting my solution to the problem here

In the question let us assume the permutation of the row as N nodes of a chain connected by N - 1 edges. Let the value of each edge be the maximum of the two elements it is connecting. Now if we are coloring all the nodes whose values are less than or equal to X, let us assume all the nodes are separate Islands initially. So there are X Islands initially.

Now we connect two adjacent Islands together and make a single Island if the maximum value of the two Islands is less than of equal to X (why?) and the count of number of Islands decreases by one. But the maximum value between two Islands is the value of the edge connecting it. So all those edges whose value is less than or equal to X will decrease the count of number of Islands by one.

We can count the number of edges whose value is less than or equal to X by using Binary Indexed Trees or Segment Trees.

In the update operation if we are swapping two different elements the values of the edges connecting those two elements will change. So we need to update 4 edges twice. Complexity ~ O(8 * Q * log(N)).

asked 07 Oct '14, 18:44

adurysk's gravatar image

5★adurysk ♦
92852428
accept rate: 11%


The way I approached this problem was a little different. Lets say we color the nodes in increasing order of their values. So, we will color node 1 first, and the number of island will be 1. Then we color the node numbered 2. If 2 is adjacent to 1, in the given permutation, the number of island remain the same, ie 1, otherwise it increases by 1. Then we color number with value 3. If the permutation was (1,3,2), then before coloring 3, we will have 2 islands, but as we color 3, we actually combine 2 existing islands. Thus each node either increase the number of islands by one, keep it same or decrease the number of island by one if we color the nodes in order. So we can associate one of these 3 values with each node {-1,0,1}. And we can decide this value just by looking at the node number of the node just left and right to it. If node number x, has both its neighbors numbered lower than x, then coloring node x, will merge 2 existing island hence -1(the contribution of node x to the number of islands). If both its neighbors are greater, then contribution will be +1. else 0. So we observe that given a permutation, we can directly say, what values each node gets. Then using a BIT, we can answer the query in O(logN) Finding the sum in BIT, for the first x numbers. Also, while swapping, the values of atmost 6 nodes will be affected. So swap queries can also be answered in O(6*logN).

link

answered 11 Oct '14, 01:00

karanaggarwal's gravatar image

3★karanaggarwal
2716
accept rate: 0%

edited 11 Oct '14, 01:04

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:

×146

question asked: 07 Oct '14, 18:44

question was seen: 880 times

last updated: 11 Oct '14, 01:04