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

×

PRMGD - Editorial

PROBLEM LINK:

Practice

Contest

Author: Bhushan Khanale

DIFFICULTY:

Easy-Medium

PREREQUISITES:

DFS

PROBLEM:

The problem was to find the total number of ink blocks at the end of the ink-dropping procedure.

QUICK EXPLANATION:

The solution concept is quite simple, we find the prime numbers and then do a DFS to visit the longest chain of overlapping/connected blocks of ink. Finally while doing so keep a count of the blocks we are looking into. The final answer will be the count generated.

EXPLANATION:

The problem tells us that for every prime number in the grid we will put an ink drop over to it. Also the ink drop will 'spread' and cover all the adjacent elements of the prime number in the grid. It is given that, when two ink blocks overlap each other, they form a single ink block. Hence if the adjacent elements are common in two ink blocks, they constitute to the same ink block. From this we can generate the idea of DFS. Since the ink blocks can be considered as nodes and then the connection will denote the edge between those. We can find out the primes through the sieve and then we can check for the unique block by the source of DFS as the source should be unvisited and should be a prime number. Further such number of sources for the DFS should be counted, which would be our required answer.

Please have a look at @abdullah768 solution given below, which is easy to understand the approach.

SOLUTION:

Solution link

This question is marked "community wiki".

asked 16 Dec '18, 00:52

bhushan_'s gravatar image

5★bhushan_
926
accept rate: 9%

edited 16 Dec '18, 09:14

admin's gravatar image

0★admin ♦♦
19.7k350498541

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:

×15,482
×9
×5
×3

question asked: 16 Dec '18, 00:52

question was seen: 39 times

last updated: 16 Dec '18, 09:14