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

×

CHEFING - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Aditya Dimri
Tester: Alexey Zayakin and Yash Chandnani
Editorialist: Taranpreet Singh

DIFFICULTY:

Simple.

PREREQUISITES:

Basic Data structures.

PROBLEM:

Given $N$ dishes each represented by a string of lowercase characters, each character representing a different ingredient, find out the number of special ingredients. A special ingredient is an ingredient which is present in all dishes.

QUICK EXPLANATION

  • Initially, all characters are considered special.
  • For every string, we can mark the characters not present in the string as non-special. Hence, the characters marked special after considering all strings are the required set of characters.

EXPLANATION

The problem is really simple. We just need to check for each character from 'a' to 'z' whether this character is present in all strings or not.

This can be done in many ways, such as

  • For each character, iterate over all strings and check if this character is present in all strings. If yes, increment the answer by one. The final value of the answer is the number of special ingredients.
  • Maintain a special integer array of size $A$ being the size of the alphabet, and for every unique occurrence of a character in the string, increase the character position in the array by one. The final answer is the number of characters, which have special array value equal to $N$.

The method which can be a learning experience is, by using bitmasks. Let us represent each character by a bit. Initially, all bits are set. Now, we represent each string as a bitmask, corresponding bit on for each character present in the string. Can you figure out the bitwise operation required here?

View Content

Time Complexity

Time complexity is $O(|S|)$ per test case.

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter's solution
Tester's solution
Editorialist's solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

asked 13 Feb, 23:45

taran_1407's gravatar image

6★taran_1407
4.0k31103
accept rate: 22%

edited 16 Feb, 17:05

admin's gravatar image

0★admin ♦♦
19.8k350498541


btw I get AccessDenied if I click on solutions

link

answered 17 Feb, 02:07

dcrystalj's gravatar image

3★dcrystalj
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:

×15,851
×1,409
×1,191
×643
×185
×8

question asked: 13 Feb, 23:45

question was seen: 509 times

last updated: 17 Feb, 02:07