<p>Let key space <span class="math-container">$K_n =$</span> { <span class="math-container">$1, 2,...,n$</span> }<br><br>
Let Data Structure <span class="math-container">$D$</span> implementing a set <span class="math-container">$S$</span> of sets such that<br></p>
<ol>
<li>All sets in <span class="math-container">$S$</span> are of same size <span class="math-container">$l$</span>, <span class="math-container">$1 \le l \le n$</span></li>
<li>All sets in <span class="math-container">$S$</span> contain keys belonging to <span class="math-container">$K_n$</span> only<br></li>
</ol>
<p><span class="math-container">$D$</span> should support following queries:</p>
<ol>
<li><span class="math-container">$Delete(k):$</span> Deletes all sets in <span class="math-container">$S$</span> which contain key <span class="math-container">$k$</span>.</li>
<li><span class="math-container">$Insert(k):$</span> Inserts key <span class="math-container">$k$</span> in all sets of <span class="math-container">$S$</span>.<br></li>
</ol>
<p>An information about the nature of sequence of queries to <span class="math-container">$D$</span> is given:<br>
Let <span class="math-container">$f(k)$</span> be a query sequence <span class="math-container">$Delete(k) \rightarrow Insert(k)$</span><br>
The environment in which <span class="math-container">$D$</span> is to be used will always produce a query sequence like:<br> <span class="math-container">$f(x) \rightarrow f(y) \rightarrow f(z) \rightarrow ...$</span></p>
<p><span class="math-container">$Illustration:$</span><br>
<span class="math-container">$K_n =$</span> { <span class="math-container">$1, 2, 3, 4, 5, 6$</span> }<br>
A sequence of queries is given below:<br>
<span class="math-container">$S =$</span> { { <span class="math-container">$1, 2, 3$</span> }, { <span class="math-container">$1, 2, 4$</span> }, { <span class="math-container">$1, 4, 5$</span> }, { <span class="math-container">$1, 3, 6$</span> }, { <span class="math-container">$1, 5, 6$</span> } }<br>
<span class="math-container">$Delete(3)$</span><br>
<span class="math-container">$S =$</span> { { <span class="math-container">$1, 2, 4$</span> }, { <span class="math-container">$1, 4, 5$</span> }, { <span class="math-container">$1, 5, 6$</span> } }<br>
<span class="math-container">$Insert(3)$</span><br>
<span class="math-container">$S =$</span> { { <span class="math-container">$1, 2, 3, 4$</span> }, { <span class="math-container">$1, 3, 4, 5$</span> }, { <span class="math-container">$1, 3, 5, 6$</span> } }<br>
<span class="math-container">$Delete(6)$</span><br>
<span class="math-container">$S =$</span> { { <span class="math-container">$1, 2, 3, 4$</span> }, { <span class="math-container">$1, 3, 4, 5$</span> } }<br>
<span class="math-container">$Insert(6)$</span><br>
<span class="math-container">$S =$</span> { { <span class="math-container">$1, 2, 3, 4, 6$</span> }, { <span class="math-container">$1, 3, 4, 5, 6$</span> } }<br></p>
<p><span class="math-container">$Question:$</span> Can such a data structure <span class="math-container">$D$</span> be designed with supports both of the above queries in less than <span class="math-container">$O(2^n)$</span> time and occupies space less than <span class="math-container">$O(|S|)$</span></p>

CC BY-SA 4.0
2024-01-09T19:09:06.757Z
How are the sets in $S$ given, initially?  (Seems hard to give them using space "less than $O(|S|)$".)
Neal Young
CC BY-SA 4.0
2024-01-09T19:20:09.903Z
(i) Can please explain where this question arises (per the posting guidelines)?  (ii) As specified, *each query returns no information*, so a trivial implementation that simply does (and stores) nothing will, technically, support the given queries.
Neal Young
<ds.data-structures><set-theory>
Data structure for storing set of sets
yash vinayvanshi
# Data structure for storing set of sets

(Asked by: username_0 on 2024-01-09)

Let key space $K\_n =$ { $1, 2,...,n$ }  
  
Let Data Structure $D$ implementing a set $S$ of sets such that

1. All sets in $S$ are of same size $l$, $1 \le l \le n$
2. All sets in $S$ contain keys belonging to $K\_n$ only

$D$ should support following queries:

1. $Delete(k):$ Deletes all sets in $S$ which contain key $k$.
2. $Insert(k):$ Inserts key $k$ in all sets of $S$.

An information about the nature of sequence of queries to $D$ is given:  
Let $f(k)$ be a query sequence $Delete(k) \rightarrow Insert(k)$  
The environment in which $D$ is to be used will always produce a query sequence like:  
 $f(x) \rightarrow f(y) \rightarrow f(z) \rightarrow ...$

$Illustration:$  
$K\_n =$ { $1, 2, 3, 4, 5, 6$ }  
A sequence of queries is given below:  
$S =$ { { $1, 2, 3$ }, { $1, 2, 4$ }, { $1, 4, 5$ }, { $1, 3, 6$ }, { $1, 5, 6$ } }  
$Delete(3)$  
$S =$ { { $1, 2, 4$ }, { $1, 4, 5$ }, { $1, 5, 6$ } }  
$Insert(3)$  
$S =$ { { $1, 2, 3, 4$ }, { $1, 3, 4, 5$ }, { $1, 3, 5, 6$ } }  
$Delete(6)$  
$S =$ { { $1, 2, 3, 4$ }, { $1, 3, 4, 5$ } }  
$Insert(6)$  
$S =$ { { $1, 2, 3, 4, 6$ }, { $1, 3, 4, 5, 6$ } }

$Question:$ Can such a data structure $D$ be designed with supports both of the above queries in less than $O(2^n)$ time and occupies space less than $O(|S|)$

**Tags:** ds.data-structures, set-theory

> **Comments:**
> **username_1**: How are the sets in $S$ given, initially?  (Seems hard to give them using space "less than $O(|S|)$".)  
> **username_1**: (i) Can please explain where this question arises (per the posting guidelines)?  (ii) As specified, *each query returns no information*, so a trivial implementation that simply does (and stores) nothing will, technically, support the given queries.  

---

## 0 answers

