All Tracks Math Problem

Chef & Chutneys

Advanced Data Structures, Data Structures, Gaussian Elimination, Linear Algebra, Math, Segment Trees


A chef has recently opened a new restaurant to serve his special dishes. He has a list of ingredients from which he makes them. Each ingredient is denoted by a unique lowercase letter. Thus, a dish is represented as a string of ingredients possibly with repititions. There are \(N\) people in his restaurant currently each of whom have ordered some dished.

You are given a collection of dishes with duplicates possibly. The chef can serve one of his favorite dishes from them if he is able to reorder all their ingredients (i.e. a permutation of the concatenation of all the strings) such that they form a palindrome. You have to facilitate the day-to-day working of the restaurant. There are two types of events happening in the restaurant:

  1. A person updates his order to get a new kind of dish.
  2. People in the range \([L, R]\) wants to know the number of non-empty subsets of \(A[L \ldots R]\) from which the Chef can make one of his favorite dish.

You are given the initial orders of the people. Therefore, you have to process \(Q\) events of the mentioned types. 

Input format

  • First Line: Two integers \(N, Q\) denoting the number of people currently in the restaurant and the numbers events happening over time

  • Second Line: \(N\) space seperated strings consisting only of lowercase letters, \(A_1, A_2, A_3,\ldots, A_N\) where \(A_i\) denotes the chutney initially ordered by the \(i^{th}\) person
  • Next \(Q\) Lines: Event of any of the above two type in the following format:
    1. \(1 \text{ } i \text{ } X \): The \(i^{th}\) person has updated his order to a new chutney \(X\): \(A[i] = X\)
    2. \(2 \text{ } L \text{ } R\): Count the number of subsets satisfying the constraint described above.

Output format

Print the required answer for each event of the \(2^{nd}\) type.


\(1 \le N \le 2\cdot10^5 \)

\(1 \le i \le N, 1 \le L \le R \le N\)

\(1 \le Q \le 5 \cdot 10^4\)

\(1 \le \sum |A_i|, \sum |X| \le 10^6\)

There is at least one event of \(2^{nd}\) type.


11 8
tamarind red mint coconut ginger peanut pudina tomato periperisauce hummus redchilli
2 1 4
2 3 10
2 1 7
2 4 11
1 8 papaya
2 4 11
1 4 onion
2 1 7

For the first 3 events, answers are as follows:

  1. We have only 1 subset from the first 4 chutneys from which Chef can prepare one of his favorite chutney: \(\{ \text{tamarind}, \text{red}, \text{mint} \} \Rightarrow \text{tamrindednirmat}\).
    Note: There might by many possible favorite chutneys Chef can prepare from a specific collection of chutneys but people are only interested to know if he can prepare one of them.
  2. There is no subset from \(A[3 \ldots10]\) from which Chef can prepare any of his favorite chutney.
  3. Indices from which favorite chutney can be prepared: \(\{1, 2, 3\}, \{1, 3, 4, 5, 6, 7\}\).
Time Limit: 4.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

March Circuits '20

View All Notifications