Problem
Recently I came across this problem ,
A despotic king decided that his kingdom needed to be rid of
corruption and disparity. He called his prime minister and ordered
that all corrupt citizens be put to death. Moreover, he wanted this
done quickly.The wily prime minister realised that investigating every citizen to
decide who was corrupt and who was not was rather difficult. So he
decided on the following plan: He ordered all the citizens to appear
in the court one by one and declare their wealth.The king does not sit in the court all the time (he has other
important business to attend to – for instance, meet dignitaries from
neighbouring kingdoms, spend time with his family …) Whenever the
king walks into the court, the prime minister pulls out the richest
man who has appeared before the court so far and is still alive and
beheads him for being corrupt. Since the rich are more likely to be
corrupt, he hopes to get rid of most of the corrupt and the king is
happy as he sees his policy being implemented enthusiastically.Suppose the wealth of the citizens trooping into the court is 1 3 7
6 5 18 9 11 2 4and the king walked in three times: the first time after the first
four persons have seen the minister, the second time after the first
five persons have seen the minister and, finally after the first nine
persons have seen the minister.At the king’s first visit the richest person to have met the minister
has wealth 7 and he would be beheaded. At the second visit, the wealth
of the richest person who has met the minister and is still alive has
wealth 6 and so he would be beheaded. At the third visit the richest
person to have met the minister who is still alive has wealth 18 and
so he would be beheaded.You may assume that the input is such that whenever the king walks in,
it is always possible to behead someone.Your aim is to write a program that will enable the prime minister to
identify the richest man to have met the minister and who is still
alive quickly. You may assume that no two citizens have the same
wealth.Input format
The first line of the input consists of two numbers N and M, where N
is the number of citizens in the kingdom and M is the number of visits
to the court by the king.The next N+M lines describe the order in which the N citizens’
appearances are interleaved with the M visits by the king. A citizen’s
visit is denoted by a positive integer, signifying his wealth. You may
assume that no two citizens have the same wealth. A visit by the king
is denoted by -1.Output format
Your output should consist of M lines, where the ith line contains the
wealth of the citizen who is beheaded at the ith visit of the king.Test Data:
You may assume that M ≤ 10000 and N ≤ 100000. You may further assume
that in 50% of the inputs M ≤ 1000 and N ≤ 8000.
My approach is like that ,until the king approaches store the numbers in an array , when the king approaches get the max number out of array , print it and make it 0 , the lowest value , but this is showing a TLE(Time Limit exceeded) for the last 3 testcases.
Do anyone have any better approach to this problem?
Here is the code:
#include <iostream>
#include <vector>
#include <algorithm>
int findGreatest(std::vector<int>vec){
int n = vec.size();
int arr[n][n];
for(int i=0;i<n;i++){
arr[n][i] = vec[i];
}
for(int i=n-2;i>=0;i--){
for(int j=0;j<n-1;j++){
if(arr[i+1][j] > arr[i+1][j+1]){
arr[i][j] = arr[i+1][j];
}else{
arr[i][j] = arr[i+1][j+1];
}
}
}
return arr[0][0];
}
int getPos(std::vector<int> vec, int num){
for(int i=0;i < vec.size();i++){
if(num == vec[i]){
return i;
break;
}
}
}
int main (int argc, char const* argv[])
{
int n , k ,i=0;
std::cin >> n >> k;
std::vector<int>riches , visits;
while(k){
int a;
std::cin >> a;
if(a == -1){
k--;
int b = getPos(riches,findGreatest(riches));
std::cout << b << findGreatest(riches) << std::endl;
std::cout << riches[b] << std::endl;
riches[b] = 0;
}else{
riches.push_back(a);
}
i++;
}
return 0;
}
Edit : So many views for a solved question , well if possible can anyone take a look at this and this queries?
Solution
i am completely useless
- That
int iinmain. You never read it. Remove it. - The
std::vector<int> visitsinmain. Never used in any way. Remove it.
What are you doing there?
int findGreatest(std::vector<int>vec) {
That sounds good, but why make a copy of the (entire) vector? Better take it by const reference, you don’t plan to modify it in that function:
int findGreatest(std::vector<int> const & vec) {
Now what follows is not so good:
int n = vec.size(); // better use size_t
int arr[n][n]; // This is NOT C++!
for(int i=0;i<n;i++){
arr[n][i] = vec[i]; // Undefined behaviour! Did you mean arr[n-1][i]?
}
/* For the rest, I've no idea what you're doing there ... or better WHY you're doing it */
for(int i=n-2;i>=0;i--){
for(int j=0;j<n-1;j++){
if(arr[i+1][j] > arr[i+1][j+1]){
arr[i][j] = arr[i+1][j];
}else{
arr[i][j] = arr[i+1][j+1];
}
}
}
return arr[0][0];
}
Let’s take a step back and see what you’re trying to achieve: Finding the greatest element in a vector. To do that, iterate over the vector, tracking the currently greatest element:
int currentMax = std::numeric_limits<int>::min(); // or INT_MIN
for (size_t i = 0; i < vec.size(); ++i) { // May also use a range based loop
if (vec[i] > currentMax) {
currentMax = vec[i];
}
}
As this is a rather useful concept, there’s of course a function for it: std::max_element. Though this does not return the value, but rather an iterator (index) to the element with the greatest value. But …
getPos(riches,findGreatest(riches));
… this is exactly what we want.
Save intermediate values
int b = getPos(riches,findGreatest(riches));
std::cout << b << findGreatest(riches) << std::endl;
std::cout << riches[b] << std::endl;
riches[b] = 0;
You call your (expensive) findGreatest function twice. Don’t. Also you don’t stick to the output format specified in the problem statement.
Thus we can reduce to
std::vector<int>::iterator wealthiest = std::max_element(std::begin(riches), std::end(riches));
std::cout << *wealthiest << std::endl;
*wealthiest = 0;
But isn’t there a faster solution?
With the above, you always search to the entire vector of currently known persons to find the wealthiest of them. In the worst case, e.g. when all N persons enter, and then the king comes to see M people beheaded, you’re basically searching M times through the whole vector, thus you have O(M * N).
To improve on that: Nothing states that the persons must stay in the order in which they entered the room. Whenever a new person enters the room, let it stand so that all persons in front of it are wealthier, and all persons behind it are less wealthy. When the king comes, behead the first (as it has no one in front, there’s no wealthier person). Basically, keep the collection of citizens sorted according to their wealth.
There are multiple ways of doing so:
- Use not a vector but a sorted container, e.g. a
std::priority_queueor (since there are no two citizens with the same wealth) astd::set. - Keep a heap inside your vector:
std::make_heap. - Sort your vector whenever the king comes. (Though this only works good if sorting an already almost sorted sequence is fast)
Random improvements
- You know how many citizens there’ll be. Reserve space for them beforehand.
I think you should not search for the greatest value, but rather keep your array sorted. But first things first:
-
Use descriptive names. Even if the problems normally use single letters this is bad practise
int numPeople, numVisits; std::cin >> numPeople >> numVisits; std::vector<int> people; std::vector<int> beheadedWealth; -
You can already reserve the memory for the vectors as you know their maximal size:
people.reserve(numPeople); // lets be pessimistic about that beheadedWealth.reserve(numVisits); -
Whats the purpose of i?
-
You loop does strange things, as it calls findGreatest twice, which is unnecessary. Instead just insert the new values into the vector in a sorted fashion:
void insert_sorted(std::vector<int> &vec, int wealth) { vec.insert(std::upper_bound(vec.begin(), vec.end(), wealth), wealth); }Therewith you always know that the richest person is the one at the end of the people vector and your loop becomes:
while (numVisits != 0) { int input; std::cin >> input; if (input == -1) { beheadedWealth.push_back(people.back()); people.pop_back(); numVisits--; } else { insert_sorted(people, input); } } -
Now that you have a vector with all the wealth of the beheaded people you can easily print them out:
for (auto &elem : beheadedWealth) { std::cout << elem << "n"; }Please note that i use
"n"instead ofstd::endlas this doesnt flush the stream.
All put together we get:
#include <iostream>
#include <vector>
#include <algorithm>
void insert_sorted(std::vector<int> &vec, int wealth) {
vec.insert(std::upper_bound(vec.begin(), vec.end(), wealth), wealth);
}
int main () {
int numPeople, numVisits;
std::cin >> numPeople >> numVisits;
std::vector<int> people;
people.reserve(numPeople);
std::vector<int> beheadedWealth;
beheadedWealth.reserve(numVisits);
while (numVisits != 0) {
int input;
std::cin >> input;
if (input == -1) {
beheadedWealth.push_back(people.back());
people.pop_back();
numVisits--;
} else {
insert_sorted(people, input);
}
}
for (auto &elem : beheadedWealth) {
std::cout << elem << "n";
}
}
I would think that a heap would be a better choice of data structure for this problem.
#include <iostream>
#include <vector>
#include <algorithm>
int main (int argc, char const* argv[])
{
int n, k;
std::cin >> n >> k;
std::vector<int> v;
std::make_heap (v.begin(), v.end());
while (k && n) {
int a;
std::cin >> a;
if (a == -1) {
k--;
int x = v.front();
std::cout << x << 'n';
std::pop_heap(v.begin(),v.end()); v.pop_back();
} else {
n--;
v.push_back(a); std::push_heap(v.begin(),v.end());
}
}
return 0;
}
Here is what the data structure looks like if you insert 20 and then 1 through 19. This ends up being 20 writes and 35 moves.
20
20 1 # add 1
20 1 2 # add 2
20 3 2 1 # add 3, move 1
20 4 2 1 3 # add 4, move 1
20 4 5 1 3 2 # add 5, move 1
20 4 6 1 3 2 5 # add 6, move 1
20 7 6 4 3 2 5 1 # add 7, move 2
20 8 6 7 3 2 5 1 4 # add 8, move 2
20 9 6 7 8 2 5 1 4 3 # add 9, move 2
20 10 6 7 9 2 5 1 4 3 8 # add 10, move 2
20 10 11 7 9 6 5 1 4 3 8 2 # add 11, move 2
20 10 12 7 9 11 5 1 4 3 8 2 6 # add 12, move 2
20 10 13 7 9 11 12 1 4 3 8 2 6 5 # add 13, move 2
20 10 14 7 9 11 13 1 4 3 8 2 6 5 12 # add 14, move 2
20 15 14 10 9 11 13 7 4 3 8 2 6 5 12 1 # add 15, move 3
20 16 14 15 9 11 13 10 4 3 8 2 6 5 12 1 7 # add 16, move 3
20 17 14 16 9 11 13 10 15 3 8 2 6 5 12 1 7 4 # add 17, move 3
20 18 14 17 9 11 13 10 16 3 8 2 6 5 12 1 7 4 15 # add 18, move 3
20 19 14 17 18 11 13 10 16 9 8 2 6 5 12 1 7 4 15 3 # add 19, move 3
If we just keep the vector ordered then for the worst case we have to move 171 memory locations.
20
20 1
20 2 1 # move 1
20 3 2 1 # move 2
20 4 3 2 1 # move 3
20 5 4 3 2 1 # move 4
20 6 5 4 3 2 1 # move 5
20 7 6 5 4 3 2 1 # move 6
20 8 7 6 5 4 3 2 1 # move 7
20 9 8 7 6 5 4 3 2 1 # move 8
20 10 9 8 7 6 5 4 3 2 1 # move 9
20 11 10 9 8 7 6 5 4 3 2 1 # move 10
20 12 11 10 9 8 7 6 5 4 3 2 1 # move 11
20 13 12 11 10 9 8 7 6 5 4 3 2 1 # move 12
20 14 13 12 11 10 9 8 7 6 5 4 3 2 1 # move 13
20 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 # move 14
20 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 # move 15
20 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 # move 16
20 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 # move 17
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 # move 18
@Daniel Jour suggested in his great answer to use a std::priority_queue. I thought I give that a try and turn it into a full working example code. It’s pretty much a straightforward implementation of the problem description.
#include <iostream>
#include <queue>
int main ()
{
int N = 0, M = 0, input = 0;
std::priority_queue<int> sortedWealthList;
std::cin >> N >> M;
for(int inputLine = 0; inputLine < N + M; ++inputLine)
{
std::cin >> input;
if (input == -1)
{
std::cout << sortedWealthList.top() << "n";
sortedWealthList.pop();
}
else
{
sortedWealthList.push(input);
}
}
}
That scores 100 on the IARCS Problems Archive, whatever that means.