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

×

RAINBOW - Editorial

PROBLEM LINK:

Practice
Contest

Author: Lewin Gan
Testers: Kamil Dębowski
Editorialist: Lewin Gan

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Graphs

PROBLEM:

Find a maximum subset of nodes such that each node has at least two neighbors of different colors.

QUICK EXPLANATION:

Remove nodes that cannot be part of any interesting subset, and repeat.

EXPLANATION:

Let's call a vertex "bad" if all its neighbors are the same color. Obviously, we can't have any bad vertices in our interesting subset, so let's remove them from the graph. This might introduce some more bad vertices, but we can keep repeating this process (this is illustrated in the last sample case).

Now, if we have no bad vertices, we claim that the subset is interesting. Of course, this follows from the definition of an interesting subset. What about maximum size? Well, we only removed vertices that had no way of being part of an interesting subset. Thus, we must have a subset of maximum size at the end since we never removed something that could be part of an interesting subset.

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter
Tester

This question is marked "community wiki".

asked 19 Mar, 20:12

lg5293's gravatar image

7★lg5293
511213
accept rate: 10%

edited 20 Mar, 00:23

admin's gravatar image

0★admin ♦♦
15.2k347484504


Tester should have used assert statements, to check whether the given constraints are satisfied.

link

answered 20 Mar, 02:03

prakhar_26's gravatar image

5★prakhar_26
2775
accept rate: 9%

edited 20 Mar, 02:03

4

I did it. The thing is that we made some change in constraints one day before the contest and I didn't modify my validator (program with asserts) — I will try not to let it happen again. I'm sorry for that.

(20 Mar, 03:34) errichto ♦♦5★

Its okay dear, you did your best. :)

(20 Mar, 10:54) vijju1234★

I spend > 1hrs to debug and cannot get it accepted. Then suddenly, when I woke up in the next morning, my solution is ACed. Why?

link

answered 20 Mar, 08:18

yakumo_yukari's gravatar image

4★yakumo_yukari
111
accept rate: 0%

1

There was a small error in the test files. It was fixed at the ending of the contest which was extended by 15 mins.

(20 Mar, 08:40) swetankmodi5★

the tester's solution time complexity seems to be O(N^2) for the worst case .I wonder if there is some optimal approach for this,, doesn't seem to be existent .

link

answered 20 Mar, 12:19

daljit1's gravatar image

2★daljit1
435
accept rate: 0%

edited 20 Mar, 16:04

2

The setter's solution is also O(N^2). We can't do any better since we need O(N^2) time just to read the input.

(20 Mar, 20:28) lg52937★

Thankyou ,I was just wondering ;).

(21 Mar, 19:53) daljit12★

i couldn't understand the editorial properly problem says that color/a number is assigned to an edge.but editorial says that fiind neighbour node of different color!!! anyone please explain editorial

link

answered 20 Mar, 12:48

forhadsidhu's gravatar image

2★forhadsidhu
1
accept rate: 0%

@forhadsidhu neigbour, since the graph is a complete graph .

link

answered 20 Mar, 12:52

daljit1's gravatar image

2★daljit1
435
accept rate: 0%

edited 20 Mar, 12:55

@daljit1 actually i couldn't understand the editorial.is it possiblem to explain what u underrstood??

link

answered 20 Mar, 12:56

forhadsidhu's gravatar image

2★forhadsidhu
1
accept rate: 0%

The editorial is self explanatory :)

link

answered 20 Mar, 13:08

daljit1's gravatar image

2★daljit1
435
accept rate: 0%

We needed to find subset of veriticies so that all of them had edges from them not of same colour. If any vertex had all the edges from it of same colour to all vetricies in the subset, then such a vetrex is termed bad.So, keep removing bad vertices from the graph. Try solving the last test case given the examples.

link

answered 20 Mar, 14:40

san1997's gravatar image

5★san1997
1
accept rate: 0%

The tester Solution is O(N^2)....can't we do better than this...?

link

answered 20 Mar, 19:43

iamabjain's gravatar image

4★iamabjain
1213
accept rate: 8%

1

The setter's solution is also O(N^2). Anyways, we can't do better than this since we need at least O(N^2) time just to read the input.

(20 Mar, 20:27) lg52937★

@forhadsidhu you start with the complete graph given to you. Each node has edges emanating off it. Let us denote the total number of distinctly colored edges that come out of node i as diff[i]. Now once you've performed this task remove all the nodes which have diff[i] < 2. However, as you are removing nodes it means other nodes might get affected and their values of diff[i] might decrease below 2. Suppose node i only has green colored edges coming out of it and node j has one green colored edge to node i and the rest are orange colored edges. Now when you calculate diff[i] you will find that node i needs to be removed but node j can stay. However, once you've removed node i node j will become faulty as now it has only orange colored edges coming off it. So you need to perform this process until you get a set of nodes where each node has diff[i] >= 2. As for the proof of why this will work: Suppose a node has diff[i] < 2, it's faulty. Then it can't be a part of any set of nodes we give as the answer. Therefore removing it does no harm to our solution and we can safely remove it. As we started with the biggest set (the complete graph) the first time we encounter such a set of nodes where diff[i] >= 2, will be the biggest set with the required properties.

link

answered 01 Jun, 11:38

arri12345's gravatar image

2★arri12345
1
accept rate: 0%

@forhadsidhu you start with the complete graph given to you. Each node has edges emanating off it. Let us denote the total number of distinctly colored edges that come out of node i as diff[i]. Now once you've performed this task remove all the nodes which have diff[i] < 2. However, as you are removing nodes it means other nodes might get affected and their values of diff[i] might decrease below 2. Suppose node i only has green colored edges coming out of it and node j has one green colored edge to node i and the rest are orange colored edges. Now when you calculate diff[i] you will find that node i needs to be removed but node j can stay. However, once you've removed node i node j will become faulty as now it has only orange colored edges coming off it. So you need to perform this process until you get a set of nodes where each node has diff[i] >= 2. As for the proof of why this will work: Suppose a node has diff[i] < 2, it's faulty. Then it can't be a part of any set of nodes we give as the answer. Therefore removing it does no harm to our solution and we can safely remove it. As we started with the biggest set (the complete graph) the first time we encounter such a set of nodes where diff[i] >= 2, will be the biggest set with the required properties.

link

answered 01 Jun, 11:39

arri12345's gravatar image

2★arri12345
1
accept rate: 0%

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:

×10,708
×1,010
×888
×667
×54
×6

question asked: 19 Mar, 20:12

question was seen: 1,326 times

last updated: 01 Jun, 16:34