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

×

DECUNI- Editorial

PROBLEM LINK:

Contest
Practice

Setter- Adhyyan Sekhsaria
Tester- Adhyyan Sekhsaria
Editorialist- Abhishek Pandey

DIFFICULTY:

EASY

PRE-REQUISITES:

BFS on a Graph, Pre-processing, Data Structures such as Vectors, Set &etc.

PROBLEM:

Given a graph of $N$ nodes, we have to answer queries asking if there exists a node $u$ at shortest distance of $D$ from node $1$, such that, the degree of node $u$ is $K$. All the edges are of equal weight.

QUICK-EXPLANATION:

We run a $BFS$ on a graph. Since edges are of equal weight, BFS is guaranteed to give shortest path. At every step, we keep track of two things-

  • How far is this node from node $1$? (i.e. number of levels b/w this node and node $1$)
  • Degree of this node.

Knowledge of STL (such as vectors or dynamic arrays) helps solve this question quickly.

EXPLANATION:

The editorial will consist of a single section only. Implementation will be integrated with explanation, the code being hidden under tabs. It is advised that you try out your own implementation first before peeking into editorial's implementation for self-practice :)

Full Solution-

Lets start the editorial with a very important concept. For graph where weights of ALL edges are equal, there are $2$ things to note-

  • $BFS$ is sufficient to give correct answer.
  • $DFS$ FAILS to give shortest path.

It is very necessary to grasp and reason it. I will informally discuss the first point here, while second one will be in bonus corner for the interested.

Assuming you have an idea of what BFS is (refer to links in pre-requisites section elsewise), lets first observe what BFS does. Please fix node $1$ as reference node for the below discussion.

BFS, in a way, traverses nodes "level-wise". Meaning, first all nodes at level $1$ are visited, then all nodes at level $2$ are visited....and so on. How many edges do you need to go from one level to another? Just $1$. We need just one edge to travel from a node at level $k-1$ to level $k$. (assuming they are directly connected/are neighbors). You can, also hence, get an intuition that no 'unnecessary' edges are picked. This is an informal intuition.

For the formal proof, we can see that because BFS is a level-wise traversal, AND all edges are equi-weighted (i.e. have same weight), we can see that it uses the "currently cheapest edge" to travel to an un-visited node. Thus, we can relate it to proof of Dijkstra's Shortest Path Algorithm , which is guaranteed to give correct answer if all edges are positive.

Now, we know we have to do a BFS, what next?

Well, let me tell you something :)

The only difference between a solution which passes only first subtask (and TLE's on the other) and the full solution is that, the full solution is smart. The inefficient solution will do a BFS for every query, while the efficient one will realize that in just a single BFS, we can get the data to answer any possible query.

How do we do that?

Please take time and get yourself introduced to set data-structure if you are new :)

We make an array of sets, say $degree[d]$. Here, $degree[d]$ is the set which stores ALL degrees at distance of $d$ from node $1$. Now, after taking the input, for any node of degree $b$ at distance $d$, we simply inset it at the appropriate set. This is as simple as doing - degree[d].insert(b);

Now, why set?

  • Insertion and deletion of any element takes $O(LogN)$ time.
  • We can find if an element is present in a set in $O(LogN)$ time.
  • Duplicates are not allowed.

A implementation of modified BFS to pre-process data/store answers is given below. Try to have an attempt yourself first though!

View Content

An example function to answer queries using above ideas is given below. Do give a try yourself first!

View Content

SOLUTION:

The solutions are pasted in tabs below in case links dont work. This is only for your convenience so you dont have to wait for @admin to fix the links :)

Setter

View Content

Editorialist

View Content

$Time$ $Complexity=$ $O( \underbrace{N+M} _ {\text{BFS}}+\underbrace{Nlog_2N} _ {\text{Set insertion}}+\underbrace{QLog_2N} _ {\text{Answering queries}}) \equiv O((Q+N)log_2N)$ (as answering queries and making the set are most expensive part of computation in this question)

CHEF VIJJU'S CORNER :D

1. Why DFS will give a wrong answer.

View Content

2. As an exercise, try to make a small test case where $BFS$ passes and $DFS$ fails. The analysis and insight is always helpful, especially for debugging!

This question is marked "community wiki".

asked 03 Jul '18, 23:07

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

edited 29 Nov '18, 17:03

A implementation of modified DFS to pre-process data/store answers is given below. Try to have an attempt yourself first though! It should be BFS ??

(21 Jul '18, 01:55) aryanc4035★
1

I was just checking your attention. ;). Even the setters missed that :p

(21 Jul '18, 02:11) vijju123 ♦♦5★

I used map of pairs,int to store distance and degree of each node and for each query i will just check whether that particular pair is set or not.

So, the time complexity for my solution should be O(N+Q).

correct me if i m wrong.

link

answered 21 Jul '18, 01:28

sagar_sam's gravatar image

4★sagar_sam
522
accept rate: 0%

Please give link to your solution. Also note that, if you used HashMap/unordered map, then its possible (although very difficult) to generate a worst case of $O(Q*N)$ for your solution if you use in built hashing function.

(21 Jul '18, 01:35) vijju123 ♦♦5★

I used simple map in c++

Here is my solution: https://www.codechef.com/viewsolution/19285092

(21 Jul '18, 01:45) sagar_sam4★

map has a complexity of $O(logN)$ for these operations. Your complexity is same as in editorial :)

(21 Jul '18, 01:47) vijju123 ♦♦5★

Thank you for the correction.

(21 Jul '18, 01:54) sagar_sam4★

Can somebody look into my code and tell me what's wrong. I am getting WA in 4th and 5th sub task.

I am first finding the distance of each city from capital and then finding degree of each city.

http://dpaste.com/1EM3SEP

link

answered 27 Aug '18, 19:53

akash1729's gravatar image

4★akash1729
11
accept rate: 0%

edited 27 Aug '18, 19:54

@vijju123 the time complexity seems wrong. Breadth-first search runs in $\mathcal {O}(N+M)$, and for each node that was in the queue, we're inserting something into the set, which is $\mathcal{O}(\log_2N)$. Also, since the graph is connected, each node will be there in the queue exactly once. For $N$ nodes, the time complexity of the set operations will be $\mathcal{O}(N\log_2N)$. So, the overall time complexity comes out to be $\mathcal{O}(M+(N+Q)\log_2N)$. Please correct it in the editorial.

link

answered 28 Nov '18, 15:28

the_extractor's gravatar image

4★the_extractor
1627
accept rate: 10%

Why is there a $(N+Q)Log_2N$ term in your complexity? We have $N$ things in set and searching them takes $log_2N$ per item, hence $QLog_2N$. Regarding $M$ term, it doesnt really matters in my opinion. We know that in worst case $M \equiv N$ hence $N+M \equiv 2*N \equiv O(N)$. But yes, using $M$ there is semantically correct.

(28 Nov '18, 16:36) vijju123 ♦♦5★

$Q\log_2N$ is for searching in the set $Q$ times, but $N\log_2N$ is for inserting degrees into the set $N$ times (for each of the $N$ nodes), which you're doing in this line:

degreeAtDistance[temp.distance].insert(arr[u].size());
Regarding $M$, in the worst case, $M$ will be equal to $\frac{N(N-1)}{2} \approx N^2$, if there's an edge between every two nodes.

(28 Nov '18, 19:07) the_extractor4★

Ah! You're being theoritical. Its good :).

Regarding M, in the worst case

$M \le 10^5$ in the question, hence my assumption/approximation.

The reason why I did not go too much into deriving the time complexity was because its an easy problem, editorial is for beginners. They might get overwhelmed if I derive complexity of each and every stuff here. Hence I just give an easy, approximate complexity seeing which they get an idea that Ok, complexities of these types are accepted for such problems.. for harder problems though, its fun deriving them :)

(28 Nov '18, 22:07) vijju123 ♦♦5★

I will change it if you still feel the need though :)

(28 Nov '18, 22:09) vijju123 ♦♦5★

Thanks, though you have changed the complexity to what you had originally written. -_-
This is the correct time complexity: $\mathcal{O}(M+(N+Q)\log_2N)$

(29 Nov '18, 00:11) the_extractor4★

Regarding $M$, even if $N \approx M$, I think it should still be mentioned in the time complexity, because not doing so would mean that, no matter what the size of the input is, the running time does not depend on the number of edges at all, which is wrong.

editorial is for beginners.

I wish editorialists on codeforces understood this (no sarcasm here). Sometimes, reading through the editorials on codeforces, it seems that they are only meant to explain the solution to higher rated coders/experienced people/people who could solve that particular problem.

(29 Nov '18, 00:18) the_extractor4★

There, fixed for you.

For CF, I will say it depends a lot on community. There are many red/high-rated-coders coders there who want crisp editorials over everything and CF tends to it.

(29 Nov '18, 17:59) vijju123 ♦♦5★
showing 5 of 7 show all
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:

×3,820
×513
×26
×15

question asked: 03 Jul '18, 23:07

question was seen: 550 times

last updated: 29 Nov '18, 17:59