If you are following this blog you are probably asking yourself Who the beep is Karen? and why do I write a 2. article about her in a row? 🙂 Well, that’s Karen and she obviously likes coffee:
Karen was the main character of the 816 Competition of CodeForces and thus she had her 5 hours of fame among 10000 competitive programmers. Anyhow, forget about Karen and concentrate on the 2. problem of the B division. It sounds like this:
Karen, a coffee aficionado, wants to know the optimal temperature for brewing the perfect cup of coffee. Indeed, she has spent some time reading several recipe books, including the universally acclaimed “The Art of the Covfefe”.
She knows n coffee recipes. The i-th recipe suggests that coffee should be brewed between li and ri degrees, inclusive, to achieve the optimal taste.
Karen thinks that a temperature is admissible if at least k recipes recommend it.
Karen has a rather fickle mind, and so she asks q questions. In each question, given that she only wants to prepare coffee with a temperature between a and b, inclusive, can you tell her how many admissible integer temperatures fall within the range?
The first line of input contains three integers, n, k (1 ≤ k ≤ n ≤ 200000), and q (1 ≤ q ≤ 200000), the number of recipes, the minimum number of recipes a certain temperature must be recommended by to be admissible, and the number of questions Karen has, respectively.
The next n lines describe the recipes. Specifically, the i-th line among these contains two integers li and ri (1 ≤ li ≤ ri ≤ 200000), describing that the i-th recipe suggests that the coffee be brewed between li and ri degrees, inclusive.
The next q lines describe the questions. Each of these lines contains a and b, (1 ≤ a ≤ b ≤ 200000), describing that she wants to know the number of admissible integer temperatures between a and b degrees, inclusive.
For each question, output a single integer on a line by itself, the number of admissible integer temperatures between a and b degrees, inclusive.
What is the problem with this case? It seems extremely trivial – we record the data from the input in some list, increment the lists with the times it is mentioned in the recipes and then simply count the numbers within the range.
Somehow trivial and even a developer who comes from a university where students are taught to program with paper and pen can probably solve it. Perhaps.
However, the problem is that we have a 2.5 seconds time limit (which is in general quite ok) and we may have an input of 200.000. Which is where the real problem is, if we start looping and counting. Thus, we should think a bit and use some sort of data structure, which is incrementing the results. Thus, if I have to see how many recipes are between 1 and 50000 degrees, I should not iterate 50K times, but simply take the data structure and make a simple calculation of datastructure[50000]-datastructure[1].
Like this:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; class Startup { static void Main() { int intTotal = 200002; int[] intInput = ReadLineAndParseToArray(); int intRecipies = intInput[0]; int intConfirm = intInput[1]; int intQuestions = intInput[2]; List<int> liFirstLine = new List<int>(new int[intTotal]); List<int> liSecondLine = new List<int>(new int[intTotal]); List<int> liThirdLine = new List<int>(new int[intTotal]); int x; int y; for (int i = 0; i < intRecipies; i++) { intInput = ReadLineAndParseToArray(); x = intInput[0]; y = intInput[1]; liFirstLine[x]++; liFirstLine[y + 1]--; } for (int i = 1; i < intTotal; i++) { liSecondLine[i] = liSecondLine[i - 1] + liFirstLine[i]; } int intCounter=0; for (int i = 0; i < intTotal; i++) { if (liSecondLine[i] >= intConfirm) { intCounter++; } liThirdLine[i]=intCounter; } for (int i = 0; i < intQuestions; i++) { intInput = ReadLineAndParseToArray(); x = intInput[0]-1; y = intInput[1]; Console.WriteLine(liThirdLine[y]- liThirdLine[x]); } } static int[] ReadLineAndParseToArray() { return Console.ReadLine().Split().Select(int.Parse).ToArray(); } } |
The trick is hidden in the 3 lists – liFirstLine, liSecondLine and liThirdLine. Take a look at the picture below:
The first line is the first list. Thus, we put a 1 on the starting range and -1 on the ending range. The second line is a cumulation with sum of the result of the first line. The third line is a pure cumulation of the second line. Thus, I I ask How many recipes do we have between 92 and 95 degrees? the result would be [the position on the third list for 95] – [the position on the third list for 91]. Thus 3-0, thus 3.
The only way to understand the magic above is to debug for about 20 minutes the given code and to see what is happening in the lists. Or to read a chapter of a book for algorithms dedicated to binary search. The choice is yours! 🙂