MIT ACM Practice Contest: Feb 26, 2005
3 - A City of Skyscrapers
Modern cities often contain densely packed skyscrapers arranged neatly on a rectangular grid of streets and avenues. Skytown is no exception. The city has grown tremendously in the past few years. New skyscrapers, ever taller than previous skyscrapers, are constantly being erected with great haste. The skyscrapers have all been constructed identically, of course with the exception that some skyscrapers are taller than others. According to city regulations, each floor of a skyscraper has some minimum and maximum capacity, c and C, respectively. At least c people are required to live on a floor to ensure that the floor is utilized to its full potential. At most C people are permitted to live on a floor to prevent overcrowding.
Because Skytown has grown so fast, the mayor wanted to boast about the city's soaring population. The only problem is that he hasn't the faintest clue how many people live in Skytown. He has put you in charge of estimating the city's population. Of course, being a programmer, you seek a programming solution and do not want to go around the entire city asking how many people live on each floor. You come up with the following simple strategy: you will record the skyline as viewed from from both the south and the west. The skyline from the south is computed as follows: for each line of skyscrapers running north-south, the highest one in that line is recorded.
Given this data, compute the minimum and maximum number of people that could be living Skytown.
Input
The first line contains four integers, M (1 ≤ M ≤ 100,000), N (1 ≤ N ≤ 100,000), c (0 ≤ c ≤ 500), and C (c ≤ C ≤ 500), where M is the dimension of the grid in the north-south direction, N is the dimension of the grid in the east-west direction, c and C are the minimum and maximum number of people allowed per floor.
Each of the next M lines contains exactly one integer in [0, 20000]. Together, they specify the western skyline. After this, the next N lines specify the southern skyline in the same way.
Output
The output contains the minimum and maximum number of people that could be living in Skytown. Both numbers are guaranteed to fit in a 32-bit signed integer. If the two skylines specified in the input are consistent, that is, cannot possibly describe a possible configuration of skyscrapers, print "Impossible" on a single line.
Sample Input
5 10 10 20 2 4 6 8 10 1 2 3 4 5 6 7 8 9 10
Sample Output
Minimum: 550, maximum: 4100
All Submissions
Best Solutions
Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Feb 13, 2009
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
If stronger test data broke your solution, then do as you did here -- fix it! :-)
I know that this flavour of test data is rampant in Codeforces, but there users can hack others' solutions which will inevitably result in exploitation of this deficiency.
Practically speaking, I am in the wrong here, but the Java API documentation is very misleading about this. My main issue with test data of this flavour is that the exception that you get (StackOverflowError) makes no sense. People who just start getting into competitive programming and are told that they have to hack around this sort of test data are going to get discouraged very quickly - being able to sort in one line is something that a lot of competitive programmers take for granted.
Basically, if this sort of test data gets added to other problems, there should be a note added to the wiki about this sort of thing and how to avoid it. Otherwise, a lot of people will get frustrated over something that they honestly shouldn't be held accountable for (especially early in their competitive programming careers).
However, it is my opinion1 that a serious competitive programmer should be intimately familiar with the intricacies of their preferred language. If you choose to use Java, and don't want to write your own methods for efficient sorting, or input, or whatever, then it's on you. You should be prepared to accept that sorting is n^2 and potentially inefficient memory-wise.
And anyway, we're not setting any precedent here that wasn't here before. Indeed, jeffreyxiao's solution uses his own sort, and Sentient's solution uses Collections#sort, which is worst-case O(n log n).
------------------------------
Incidentally, the StackOverflowError is entirely accurate. Here's a bigger chunk of the error:
This doesn't happen in C++, which switches to heapsort when the recursion is sufficiently deep. Your pivot selection just happened to be poor.
------------------------------
1: and therefore, please don't take this as any sort of official word.