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

×

Ancient Berland Road problem from december lunchtime.

https://www.codechef.com/LTIME31/problems/ABROADS what data structure will be used to solve this problem, can any one please write editorial to it. Also add links to similar kinds of problems.

and please tell how this code is working: https://www.codechef.com/viewsolution/9023693

This question is marked "community wiki".

asked 30 Dec '15, 16:14

arpit728's gravatar image

1★arpit728
6831562
accept rate: 10%

edited 30 Dec '15, 16:23


Answer is hidden as author is suspended. Click here to view.

answered 30 Dec '15, 16:31

sarvagya3943's gravatar image

4★sarvagya3943
(suspended)
accept rate: 36%

@sarvagya3943 can you write editorial.

(30 Dec '15, 16:35) arpit7281★
2

@arpit728 Editorial is already available for this problem. If you don't understand something there,just ask in the comments.

(30 Dec '15, 16:41) sarvagya39434★

@sarvagya3943: While we process the queries in reverse order, if the query encountered is of "p" type then how we would be knowing, what was the population before that query.(Referring the editorial).

(30 Dec '15, 20:16) arpit7281★

@arpit728 You can use Stack for each index of population array.
While processing the query in online mode whenever you encounter to change the population just push it into stack of particular index of array.
While doing Offline query in reverse order just pop the elements from stack to get back the previous population.

(30 Dec '15, 20:52) ankurverma19944★

Second Approach Maintain a new array of same size as that of number of queries. While doing online query, whenever you encounter to change the popualtion of the town store the current value of that population into new array at same index that of query and update the population array.
Later on you can easily access the previous value. See my implementation for this.

(30 Dec '15, 21:07) ankurverma19944★

@ankurverma1994 Wouldn't it be memory inefficient.

(31 Dec '15, 00:08) arpit7281★

@arpit728 I think we can store the previous value at the cost of memory. If you find any better approach do please tell me.

(31 Dec '15, 10:07) ankurverma19944★
showing 5 of 7 show all

This question has two type of queries: 1) Delete an edge in graph 2) Update/Query some information

Had query 1 would have been insert an edge in graph, we would have Disjoint Set Union Data Structure and easily solved this question, but here it is to delete.

Solution: First of all create disjoint set union on graph after deleting all edges which are going to deleted by some query. In other words, graph should be what it would have been after processing all queries in input. Now start answering queries from last query(i.e. in reverse order). Each "delete edge" query is now changed to "insert edge" query which can be handled by dsu easily.

link

answered 30 Dec '15, 16:21

sumeet_varma's gravatar image

7★sumeet_varma
1258
accept rate: 20%

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:

×1,650
×1,385
×1,197
×524
×342
×13

question asked: 30 Dec '15, 16:14

question was seen: 1,009 times

last updated: 31 Dec '15, 10:07