Answers.Body: <p>Another one is the following job scheduling problem:</p>
  
  <pre><code>N jobs are arriving with priorities:
  
  priority_1  arrival_time_1  execution_time_1
  priority_2  arrival_time_2  execution_time_2
  ...
  priority_N  arrival_time_N  execution_time_N
  
  The arriving jobs are queued. When the CPU can process the next job, he will pick
  the one that has already arrived and has the highest priority in the queue. The
  job will then be processed for a time equal to its execution time.
  
  Determine the maximum time some job will have to wait in the queue until being
  processed.
  </code></pre>
  
  <p>An efficient implementation of the queue will give <span class="math-container">$O(N \cdot log(N))$</span> solution.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-09-04T11:49:36.383Z
Answers.LastActivityDate: 2019-09-04T11:49:36.383Z
Answers.UserDisplayName: mercury0114
Answers.Body: <p>You have a list <span class="math-container">$[l_1, l_2, ..., l_N]$</span> of <span class="math-container">$N$</span> distinct integers.</p>
  <p>Then you receive <span class="math-container">$K$</span> queries where the query <span class="math-container">$q_i = (a_i, b_i)$</span> asks you to find
  the minimal element in the sublist <span class="math-container">$[l_{a_i}, l_{a_i+1}, ..., l_{b_i}]$</span></p>
  <p>Preprocess the list to serve <span class="math-container">$K$</span> queries in less than <span class="math-container">$O(K \cdot N)$</span> time.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-12T12:00:52.807Z
Answers.LastActivityDate: 2020-07-12T12:00:52.807Z
Answers.UserDisplayName: mercury0114
Answers.Body: <p>One nice problem that I found is:</p>
  
  <pre><code>Given n segments in 2D Euclidean space, find two segments that intersect.
  </code></pre>
  
  <p>Seek for <span class="math-container">$O(n \cdot log(n))$</span> solution.</p>
  
  <p><a href="https://cp-algorithms.com/geometry/intersecting_segments.html" rel="nofollow noreferrer">https://cp-algorithms.com/geometry/intersecting_segments.html</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-27T19:26:30.797Z
Answers.LastActivityDate: 2019-08-27T19:26:30.797Z
Answers.UserDisplayName: mercury0114
Answers.Body: <p>How about Huffman encodings?</p>
  
  <blockquote>
    <p>Given a text that uses an alphabet of <span class="math-container">$n$</span> unique characters, how can we uniquely encode the alphabet so that the text uses the smallest amount of bits?</p>
  </blockquote>
  
  <p>More formally for Huffman encodings (as formulated by Tardos &amp; Kleinberg in their book <em>Algorithm Design</em>):</p>
  
  <blockquote>
    <p>Given an alphabet and a set of frequencies for letters, we would like to produce a prefix code that is as efficient as possible - namely, a prefix code that minimises the average number of bits per letters <span class="math-container">$ABL(\gamma) = \sum\limits_{x\in S} f_x|\gamma(x)|$</span>. We will call such a prefix code optimal.</p>
  </blockquote>
  
  <p>This has an <span class="math-container">$O(n \log n)$</span> solution.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-28T10:30:44.487Z
Answers.LastActivityDate: 2019-08-28T13:40:41.900Z
Answers.LastEditDate: 2019-08-28T13:40:41.900Z
Answers.UserDisplayName: MrHug
Body: <p>I want to practice my problem-solving skills that involve the usage of a tree data structure (e.g. <code>Binary Search Tree</code>, <code>Heap</code>, <code>Fenwick Tree</code>, etc.)</p>
  
  <p>The problem should make me search for the right tree data structure and apply it in solving the problem, but not manipulate the tree itself. Hence, problems like the lowest common ancestor, inorder traversal, etc. do not count.</p>
  
  <p>One nice problem that I know is as follows:</p>
  
  <pre><code>N pixels in a row are originally coloured as white:
  WWWWWWWWWWWWWWW // N=15 in this case
  
  We now keep recolouring all pixels between position i and position j 
  with a different colour c for T times:
  
  T = 1: WWWBBBBBWWWWWWW // i = 4, j = 8, c = B
  T = 2: WWWBBGGGGWWWWWW // i = 6, j = 9, c = G
  T = 3: YYYBBGGGGWWWWWW // i = 1, j = 3, c = Y
  T = 4: YBBBBBGGGWWWWWW // i = 2, j = 5, c = B
  ...
  
  At the end, you are asked to print the colour of each pixel.
  </code></pre>
  
  <p>Since N and T can be large, one requires a tree data structure to efficiently update the colour pattern of the pixels. </p>
  
  <p>Can anyone suggest good programming problems of this nature?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-08-26T18:07:43.690Z
Comments.Text: Is there a reason for the restriction on updating the tree? How much practice does it take to learn tree traversal?
Comments.UserDisplayName: Ben I.
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-14T14:03:51.287Z
Comments.Text: Hey @mercury0114 I am new in these type of competitive programming world..Can you please point me to the link where I can find soln to this problem, or what is the genre of this problem which I can google?
Comments.UserDisplayName: Abhinaba Chakraborty
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-14T14:08:00.387Z
Comments.Text: I was given this specific problem in the interview, so I don't have a link to it. In general problems like these appear at https://codingcompetitions.withgoogle.com/codejam 
  , http://usaco.org/ etc.
Comments.UserDisplayName: mercury0114
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-08-26T19:10:22.503Z
Comments.Text: Well updating the tree is already implemented, I'm looking more for ways to practice the usage of a tree. Same goes for tree traversal, in modern languages you traverse a tree with the same piece of code as traversing a list.
Comments.UserDisplayName: mercury0114
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-08-26T19:12:07.567Z
Comments.Text: It's like the difference between learning to sort vs using a sorting algorithm to solve a problem.
Comments.UserDisplayName: mercury0114
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-09-18T14:15:15.743Z
Comments.Text: I don't understand why you're talking about tree data structures but mention std::set and std::map. These might work with tree data structures *in the background*, but they don't actually model trees, they model sets and (key,value) pairs. So: Are you interested in using tree structures or learning how sets and (key,value) associative containers work?
Comments.UserDisplayName: Pascal
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-09-19T15:32:06.230Z
Comments.Text: @Pascal I modified the question. I am interested in using tree data structures. I want to practice my skill at spotting what data structure fits to solve the problem effectively.
Comments.UserDisplayName: mercury0114
Tags: <algorithms><data-structure>
Title: What are competitive programming problems that require a tree data structure to solve them?
ThreadText: # What are competitive programming problems that require a tree data structure to solve them?
  
  (Asked by: username_0 on 2019-08-26)
  
  I want to practice my problem-solving skills that involve the usage of a tree data structure (e.g. `Binary Search Tree`, `Heap`, `Fenwick Tree`, etc.)
  
  The problem should make me search for the right tree data structure and apply it in solving the problem, but not manipulate the tree itself. Hence, problems like the lowest common ancestor, inorder traversal, etc. do not count.
  
  One nice problem that I know is as follows:
  
  ```
  N pixels in a row are originally coloured as white:
  WWWWWWWWWWWWWWW // N=15 in this case
  
  We now keep recolouring all pixels between position i and position j 
  with a different colour c for T times:
  
  T = 1: WWWBBBBBWWWWWWW // i = 4, j = 8, c = B
  T = 2: WWWBBGGGGWWWWWW // i = 6, j = 9, c = G
  T = 3: YYYBBGGGGWWWWWW // i = 1, j = 3, c = Y
  T = 4: YBBBBBGGGWWWWWW // i = 2, j = 5, c = B
  ...
  
  At the end, you are asked to print the colour of each pixel.
  
  ```
  
  Since N and T can be large, one requires a tree data structure to efficiently update the colour pattern of the pixels.
  
  Can anyone suggest good programming problems of this nature?
  
  **Tags:** algorithms, data-structure
  
  > **Comments:**
  > **username_1**: Is there a reason for the restriction on updating the tree? How much practice does it take to learn tree traversal?  
  > **username_0**: Well updating the tree is already implemented, I'm looking more for ways to practice the usage of a tree. Same goes for tree traversal, in modern languages you traverse a tree with the same piece of code as traversing a list.  
  > **username_0**: It's like the difference between learning to sort vs using a sorting algorithm to solve a problem.  
  > **username_3**: I don't understand why you're talking about tree data structures but mention std::set and std::map. These might work with tree data structures *in the background*, but they don't actually model trees, they model sets and (key,value) pairs. So: Are you interested in using tree structures or learning how sets and (key,value) associative containers work?  
  > **username_0**: @username_3 I modified the question. I am interested in using tree data structures. I want to practice my skill at spotting what data structure fits to solve the problem effectively.  
  > **username_2**: Hey @username_0 I am new in these type of competitive programming world..Can you please point me to the link where I can find soln to this problem, or what is the genre of this problem which I can google?  
  > **username_0**: I was given this specific problem in the interview, so I don't have a link to it. In general problems like these appear at https://codingcompetitions.withgoogle.com/codejam  , http://usaco.org/ etc.  
  
  ---
  
  ## 4 answers
  
  ### Answer by username_0 on 2019-08-27. Score: 2 | Accepted answer
  
  One nice problem that I found is:
  
  ```
  Given n segments in 2D Euclidean space, find two segments that intersect.
  
  ```
  
  Seek for $O(n \cdot log(n))$ solution.
  
  <https://cp-algorithms.com/geometry/intersecting_segments.html>
  
  
  ---
  
  ### Answer by username_4 on 2019-08-28. Score: 3
  
  How about Huffman encodings?
  
  > Given a text that uses an alphabet of $n$ unique characters, how can we uniquely encode the alphabet so that the text uses the smallest amount of bits?
  
  More formally for Huffman encodings (as formulated by Tardos & Kleinberg in their book *Algorithm Design*):
  
  > Given an alphabet and a set of frequencies for letters, we would like to produce a prefix code that is as efficient as possible - namely, a prefix code that minimises the average number of bits per letters $ABL(\gamma) = \sum\limits\_{x\in S} f\_x|\gamma(x)|$. We will call such a prefix code optimal.
  
  This has an $O(n \log n)$ solution.
  
  
  ---
  
  ### Answer by username_0 on 2019-09-04. Score: 1
  
  Another one is the following job scheduling problem:
  
  ```
  N jobs are arriving with priorities:
  
  priority_1  arrival_time_1  execution_time_1
  priority_2  arrival_time_2  execution_time_2
  ...
  priority_N  arrival_time_N  execution_time_N
  
  The arriving jobs are queued. When the CPU can process the next job, he will pick
  the one that has already arrived and has the highest priority in the queue. The
  job will then be processed for a time equal to its execution time.
  
  Determine the maximum time some job will have to wait in the queue until being
  processed.
  
  ```
  
  An efficient implementation of the queue will give $O(N \cdot log(N))$ solution.
  
  
  ---
  
  ### Answer by username_0 on 2020-07-12. Score: 0
  
  You have a list $[l\_1, l\_2, ..., l\_N]$ of $N$ distinct integers.
  
  Then you receive $K$ queries where the query $q\_i = (a\_i, b\_i)$ asks you to find
  the minimal element in the sublist $[l\_{a\_i}, l\_{a\_i+1}, ..., l\_{b\_i}]$
  
  Preprocess the list to serve $K$ queries in less than $O(K \cdot N)$ time.
  
  
  ---
  
  