PROBLEM

The Facebook campus has N different attractions, numbered from 1 to N
in decreasing order of popularity. The name of the ith attraction is
Ai, a unique, non-empty string consisting of at most 20 characters.
Each character is either a lowercase letter ("a".."z"), uppercase
letter ("A".."Z"), or digit ("0".."9").

Alex enjoys visiting the campus repeatedly for tours (including the
free food!). Each time he visits, he has time to see exactly K of the
attractions. To decide which K he'll see, he sorts the N attractions
in non-decreasing order of how many times he's already seen them
before, breaking ties in decreasing order of popularity, and then
chooses the first K attractions in the sorted list. In other words, he
prioritizes seeing attractions which he's seen the fewest number of
times previously, but also opts to see the most popular attractions
out of the ones he's seen an equal number of times.

Alex has visited the Facebook campus V-1 separate times already, and
is about to go for his Vth visit. Given that he's always followed the
rules stated above, and that he'll continue to, he'd like to determine
which K attractions he'll see on his Vth visit. He'd like to list them
in decreasing order of popularity (in other words, in the same
relative order as they appear in the given list of all N attractions).

Input

Input begins with an integer T, the number of campuses. For each
campus, there is first a line containing the space-separated integers
N, K, and V. Then, N lines follow. The ith of these lines contains the
string Ai.

Output For the ith campus, print a line containing "Case #i: "
followed by K space-separated strings, the names of the attractions
that Alex sees on his Vth visit, in decreasing order of popularity.

Constraints 1 ≤ T ≤ 80 1 ≤ K ≤ N ≤ 50 1 ≤ V ≤ 1012 Explanation of
Sample In the first case, Alex saw the LikeSign on his first visit and
the Arcade on his second visit. On his third visit he sees the
SweetStop as its the most popular of the attractions he hasn't yet
seen.

In the third and fourth cases, Alex sees LikeSign, Arcade, SweetStop
on his first visit, then LikeSign, Arcade, SwagStore, then
LikeSign, SweetStop, SwagStore.

SAMPLE INPUT

6
4 1 3
LikeSign
Arcade
SweetStop
SwagStore
4 4 100
FoxGazebo
MPK20Roof
WoodenSculpture
Biryani
4 3 1
LikeSign
Arcade
SweetStop
SwagStore
4 3 3
LikeSign
Arcade
SweetStop
SwagStore
4 3 10
LikeSign
Arcade
SweetStop
SwagStore
2 1 1000000000000
RainbowStairs
WallOfPhones

SAMPLE OUTPUT

Case #1: SweetStop
Case #2: FoxGazebo MPK20Roof WoodenSculpture Biryani
Case #3: LikeSign Arcade SweetStop
Case #4: LikeSign SweetStop SwagStore
Case #5: LikeSign Arcade SwagStore
Case #6: WallOfPhones

This is my solution that works well for small data sets but once it gets larger there is always a timeout:

#include <iostream>
#include <vector>
#include <map>
#include <limits>
#include <algorithm>
using namespace std;
struct values 
 int nrSeen;
 int popularity;
;
string getInput()
 string input;
 cin.clear();
 cin.ignore(std::numeric_limits<std::streamsize>::max(), 'n');
 cin >> input;
 return input;

auto sort_map = (pair<string,values*> s1,pair<string,values*> s2)
 if(s1.second->nrSeen == s2.second->nrSeen)
 return s1.second->popularity < s2.second->popularity;
 else
 return s1.second->nrSeen < s2.second->nrSeen;
;
auto sort_pop = (pair<string,values*> s1,pair<string,values*> s2)
 return s1.second->popularity < s2.second->popularity;
;
auto print = (pair<string,values*> s1)
 cout << " " << s1.first;
;
int main()
 vector<pair<string,values*>> attractions;
 vector<pair<string,values*>> result;

 int T,K,N;
 long V;

 cin >> T;
 bool minusOne = false;
 string input;
 for(int i = 0;i < T;i++)
 cin.clear();
 cin >> K >> N >> V;

 if(V%2 == 0 && K == 2)
 minusOne = true;
 
 while(V%K == 0)
 V = V/K;
 
 if(minusOne)
 V--;
 
 for(int j = 0;j<K;j++)
 values* v = new values();
 v->popularity = j;
 string input;
 try

 input = getInput();


 
 catch(char* error) 
 cout << error << endl;
 


 attractions.emplace_back(pair<string,values*>(input,v));
 

 int index = 0;
 for(int k = 0;k < V-1;k++)
 for(int w = 0;w<N;w++)
 if(index == K)
 index = 0;
 
 attractions[index].second->nrSeen += 1;
 index++;
 
 
 int seen = 0;
 sort(begin(attractions),end(attractions),sort_map);
 while(seen < N)

 result.emplace_back(make_pair(attractions[seen].first,attractions[seen].second));
 seen++;

 
 sort(begin(result),end(result),sort_pop);

 cout << "case #" << i +1<< ": ";
 for_each(begin(result),end(result),print);
 cout << endl;
 attractions.clear();
 result.clear();
 

 return 0;

Overall design

The biggest problem is that you haven't given enough thought to the problem you're solving before jumping into coding complicated structures to solve it. This problem can be solved without a single allocation - no news and no vectors required - and you don't even need to do any sorting.

Let's take a step back and look at what's actually happening in one of the cases. We'll use the most interesting case in the sample input: case 4, which is:

4 3 3
LikeSign
Arcade
SweetStop
SwagStore

with output:

Case #4: LikeSign SweetStop SwagStore

So there are N=4 attractions in this problem:

0: LikeSign
1: Arcade
2: SweetStop
3: SwagStore

The numbers are the indices in a hypothetical vector of attractions. (You'll see we won't actually need a vector, but pretend we'll load all the attractions into a vector<string> for now.)

Alex can only visit K=3 each time. So his first visit will be:

0: LikeSign ┐
1: Arcade │ Visit #1
2: SweetStop ┘
3: SwagStore

So far, no problem. The output of visit 1 would be: "LikeSign Arcade SweetStop". (This is actually the result of Case #3.)

But on his second visit, he wants to visit another K=3 attractions. There's only 1 he didn't visit last time, so he will revisit the first two. The best way to visualize this is to imagine that the vector of attractions repeats itself:

┌ 0: LikeSign ┐
│ 1: Arcade │ Visit #1
│ 2: SweetStop ┘
└ 3: SwagStore ┐
┌ 4: LikeSign │ Visit #2
│ 5: Arcade ┘
│ 6: SweetStop
└ 7: SwagStore

So Alex's second visit will be to the SwagStore, the LikeSign, and the Arcade, which you'l have to sort in the output as "LikeSign Arcade SwagStore". But let's ignore sorting the output for now.

For Alex's third visit, we just extend the vector again:

┌ 0: LikeSign ┐
│ 1: Arcade │ Visit #1
│ 2: SweetStop ┘
└ 3: SwagStore ┐
┌ 4: LikeSign │ Visit #2
│ 5: Arcade ┘
│ 6: SweetStop ┐
└ 7: SwagStore │ Visit #3
┌ 8: LikeSign ┘
│ 9: Arcade
│ 10: SweetStop
└ 11: SwagStore

So on Visit #4, Alex will visit the SweetShop, the SwagStore, and the LikeSign. Sorted, that's "LikeSign SweetShop SwagStore"... exactly the result we're supposed to get.

But looking at the diagram above, the pattern is pretty repetitive and predictable. If we know Alex sees 3 attractions per visit (K=3), then on the 3rd visit (V=3), he will see attractions 6, 7, and 8. Can we calculate those indices? Why yes, we can. The first attraction Alex will see on Visit #3 is $((V - 1) times K) = ((3 - 1) times 3) = 6$. (That equation is trivial to figure out if you think it through a bit.) And the remaining attractions will be the next $K - 1$ numbers (so the next 2 numbers, or 7 and 8).

Due to the magic of the modulus operator, we can convert those imaginary indices into indices in the "real" vector, just by doing the modulo with the size of the vector. The size of the vector is N. So the indices are:

• $((V - 1) times K) mod N = ((3 - 1) times 3) mod 4 = 6 mod 4 = 2$


• $(((V - 1) times K) + 1) mod N = ((3 - 1) times 3) mod 4 = 7 mod 4 = 3$


• $(((V - 1) times K) + 2) mod N = ((3 - 1) times 3) mod 4 = 8 mod 4 = 0$

So the indices are 2, 3, and 0, which map to the SweetShop, the SwagStore, and the LikeSign... exactly what we want.

So here's all you need to do for the problem, basically.

1. Read N, K, and V.


2. Calculate the starting index using $((V - 1) times K) mod N$.


3. Calculate the ending index by adding K to the starting index.


4. Read the N strings into a vector.


5. If the ending index is greater than or equal to N, then print all items in the vector from 0 to the ending index modulo N. (In the example of Case #4, the ending index is 5, because the start index is 2, and K is 3. 5 mod 4 is 1, so you're doing for (auto i = 0; i < 1; i++) cout << attractions[i];.. which will only print attraction[0], which is "LikeSign".)


6. Now just print all items in the vector from the start index to the end of the vector. (In Case #4, the start index is 2, so you're doing for (auto i = 2; i < attractions.size(); ++i) cout << attractions[i];, which will print "SweetShop", then "SwagStore".)

And that's it.

Now, already, the algorithm above doesn't do any sorting. But it does use a vector. You can do better! As you're reading in your attractions list, you can immediately print out attractions that satisfy the criteria in #5 and #6 of the algorithm... no need to store them in a vector at all! I'll leave figuring out how to do that as an exercise for the reader.

Redesigning your algorithm to take advantage of the predictability and repetition - and avoiding unnecessary allocating and sorting - will go 90% of the way to getting the performance you need.

Code review

#include <iostream>
#include <vector>
#include <map>
#include <limits>
#include <algorithm>

You include <map>, but never use a map. Is this include just vestigial from an earlier attempt?

using namespace std;

Never do this.

string getInput()
 string input;
 cin.clear();
 cin.ignore(std::numeric_limits<std::streamsize>::max(), 'n');
 cin >> input;
 return input;

I'm not really sure why you thought you needed this function. When using std::cin one should never mix line-based input (using getline()) with value-based input (using operator>>()). But for this problem, you really don't need need to worry about that. You can just do all your input as value-based.

(Or you could do it all as line-based, and handle parsing the first line and the N,K,V lines specially. Either way.)

In other words, you can ditch the cin.clear() and cin.ignore() lines. And once you've done that, you don't need the function at all. In main(), the line input = getInput(); just becomes std::cin >> input;.

auto sort_map = (pair<string,values*> s1,pair<string,values*> s2)
 if(s1.second->nrSeen == s2.second->nrSeen)
 return s1.second->popularity < s2.second->popularity;
 else
 return s1.second->nrSeen < s2.second->nrSeen;
;

There's a trick to simplify comparisons like this:

auto sort_map = (pair<string,values*> s1,pair<string,values*> s2)
 return std::tie(s1.second->nrSeen, s1.second->popularity) < std::tie(s2.second->nrSeen, s2.second->popularity);
;

On to main():

vector<pair<string,values*>> attractions;
vector<pair<string,values*>> result;

So you create two vectors: one for the attractions list, and one for the result. But... why? Looking down in your code, literally all you do is set everything up in attractions, then copy it all to result, then print result. Why not just print attractions directly, and forget all about result?

int T,K,N;
long V;

It is generally bad practice - both in C++ and modern C - to declare variables until right when they are first being used. There are exceptions to that rule when you're optimizing, but that doesn't apply here.

There's another issue here, and that's with V. If I'm reading the problem right - making some assumptions around the bad formatting - the range for V is $1 le V le 10^12$. The maximum value a long is guaranteed to hold is 2,147,483,647, or just over $2 times 10^9$. That's too small. Now, long on your system might be bigger - in fact, on modern systems, it's usually 64 bits, which is big enough. But you can't assume long will be that big.

You have two choices here.

1. You can use long long, which is guaranteed to be at least 64 bits.


2. You can include <cstdint> and use std::int_fast64_t.

I would recommend the latter. It makes your intentions clearer, and it might actually be faster (because long long could be some really slow 128 bit type, but std::int_fast64_t is, as it says, fast).

cin.clear();
cin >> K >> N >> V;

You don't need to call cin.clear() here. (Or anywhere in this program, really.)

Now... here is what I think is the most baffling decision in this code: you have reordered N, K, and V into K, N, and V. Why would you do that? That's kind of thing people joke about in obfuscated code contests as deliberate attempts to make the code harder to understand. It makes the rest of the code incredibly difficult to reason about.

if(V%2 == 0 && K == 2)
 minusOne = true;

while(V%K == 0)
 V = V/K;

if(minusOne)
 V--;

I must confess I haven't even the foggiest clue what you're doing here.

• First, there's no commenting.


• Second, the variable names are nondescriptive. V and K might have made some measure of sense given that they're parameters of the problem... but then you go and start changing V. Into what? What does it mean after the loop? minusOne apparently means to subtract 1 from V... which is about as helpful as constexpr auto one = 1;. Why are you subtracting one from V (whatever V means after the loop)?


• Third, no comments.


• Fourth, you've swapped the variable names around, so K isn't actually, K, it's N.


• Finally, there are no comments.

Let me see if I can reason this out.... Okay, if the number of visits is even and there are only two attractions, you set this mysterious minusOne variable. Why? Who knows. Then, while the number of visits is a multiple of the number of attractions, you divide the number of visits by the number of attractions. So if there are 64 visits and 4 attractions, that will give you 1. If there are 12 visits and 3 attractions, that will give you 4. I just don't get what these numbers are supposed to mean.

for(int j = 0;j<K;j++)
 values* v = new values();
 v->popularity = j;
 string input;
 try

 input = getInput();


 
 catch(char* error) 
 cout << error << endl;
 


 attractions.emplace_back(pair<string,values*>(input,v));

Okay, this is the loop where you load all your attractions. All this needs to be (assuming attractions is a vector<string>) is:

for (auto j = 0; j < K; ++j)

 std::cin >> input;
 attractions.push_back(input);

preferably with attractions.reserve(K) before the loop to avoid unnecessary allocations. So let's figure out why your loop is so much bigger and more complex.

values* v = new values();

Why are you dynamically allocating this? In the first place, it doesn't seem necessary - you could do use a simple automatic variable, and it would be far more efficient. In the second place, you never delete the memory you allocate anywhere - your program leaks every single value object you allocate.

If you defined your vectors as vector<pair<string,values>> - note, no pointer - you don't need any dynamic allocation at all and your code will probably be faster, because it will be more cache friendly.

v->popularity = j;

It needs to be said here that since an attraction's popularity is a function of its index, the popularity of any attraction attraction[X] is going to be X. You don't really need a value to keep track of its popularity. Ah, but of course, you're going to be sorting them out of source order later. This should have set off an alarm bell in your head: Is sorting the right thing to do? Mightn't there be a better way?

string input;

You already have an input string declared outside of your loop... and that was actually a good idea! Declaring variables before they are used is usually bad, but when optimizing code, it makes sense to move memory allocating objects - like strings - outside of the loop so you can reuse its memory on each loop iteration. So you did the right thing... and then you ruined it by shadowing the variable with this new one.

try
 input = getInput();

catch(char* error) 
 cout << error << endl;

First, why the try-catch? I don't see anything in the whole program that throws a char*. Is this a leftover from some testing you were doing?

Second, I've already pointed out that getInput() is unnecessary, so this entire block of code could just be std::cin >> input;. That would actually be ideal, too, because it could reuse the memory in input on each loop.

attractions.emplace_back(pair<string,values*>(input,v));

If you're going to use emplacement, you don't need to spell out the type. In fact, that's kinda defeating the purpose of emplacement. You can do any of:

attractions.emplace_back(input, v);
attractions.push_back(pair<string, values*>input, v);
attractions.push_back(pairinput, v); // needs C++17
attractions.push_back(input, v);

and that'll do the job.

int index = 0;
for(int k = 0;k < V-1;k++)
 for(int w = 0;w<N;w++)
 if(index == K)
 index = 0;
 
 attractions[index].second->nrSeen += 1;
 index++;
 

So this loop appears to be determining which attractions have been seen. For each visit, then for each attraction, you increment its seen count, literally implementing what's described in the challenge. Since V may be huge - millions and millions - one can initially assume this is the most important loop of the algorithm to optimize. (Though you should profile to determine whether that's actually true.)

One thing you generally want to avoid in hot loops is branching. Sure, modern CPUs will speculatively execute, but even if they do, you could still end up paying jump costs. That whole if is really just to keep index rolling around within the bounds of K (which is really N). That's just a modulo operation. So the whole if can just reduce to index %= K;.

Aside from that, you're just getting into the realm of micro-optimizations that really don't matter on any modern compiler, like:

• replacing any instance of x += 1 with ++x; and


• replacing any instance of x++ with ++x.

So the loop becomes:

int index = 0;
for (int k = 0; k < (V - 1); ++k) 
 for (int w = 0; w < N; ++w) 
 index %= K;
 ++attractions[index].second->nrSeen;
 ++index;
 

But none of that is going to make a huge amount of difference.

Now here's where things really start to get out of control:

int seen = 0;
sort(begin(attractions),end(attractions),sort_map);
while(seen < N)

 result.emplace_back(make_pair(attractions[seen].first,attractions[seen].second));
 seen++;


sort(begin(result),end(result),sort_pop);

First, that seen variable and the while loop is really just a for loop from 0 to N (which is really K).

So what you do is sort the list in order of least seen, then most popular (which, since popularity is on an inverse scale, means the lowest popularity number). Then you copy the first N (which is K) results into another vector. Then you sort that vector by original list order (which is popularity).

Why don't you instead do the first sort... then resize() the vector to N (which is K). Then you can do the second sort on that vector, and that's you're result. You don't need the second vector at all.

Here's what that might look like, replacing the above code:

std::sort(begin(attractions), end(attractions), sort_map);
attractions.resize(N);
std::sort(begin(attractions), end(attractions), sort_pop);
// std::cout << "case #" << (i + 1) << ':';
// std::for_each(begin(attractions), end(attractions), print);

You can even go one better by simply observing that you're working with iterators. You don't need to resize the vector (which may trigger multiple destructors). You just need the end iterator of the result set:

std::sort(begin(attractions), end(attractions), sort_map);
auto const result_end = std::next(begin(attractions), N);
std::sort(begin(attractions), result_end, sort_pop);
// std::cout << "case #" << (i + 1) << ':';
// std::for_each(begin(attractions), result_end, print);

That's about the end of the program, but there are a few more tips for speed. First though:

return 0;

You don't really need this in main().

Now onto I/O optimization.

cout << endl;

Never use endl. It's almost always wrong. What endl does is write a newline... and then flush the stream. Flushing the stream can be painfully slow, which is a waste of time normally, and when you're specifically gunning for speed, it could completely ruin your day.

To speed up C++ IOStreams, there are a couple of tricks you can use. Whether they will work will depend heavily on which implementation your target platform is using.

1. Before any I/O, right at the top of main(), do std::ios_base::sync_with_stdio(false). This will disable synchronization with the C library, which can really slow things down. Once you do this, you cannot use any C I/O functions, only C++.


2. Right after that, do std::cin.tie(nullptr);. When you're mixing input and output, normally std::cin and std::cout are tied together, so that before you do any input with std::cin, std::cout is first flushed. You don't want to pay for that unnecessary flush. (This probably won't help you much, since your input and output isn't really mixed up... but it could (especially if you refactor the algorithm the way I suggested at the beginning of this review).)

And of course, never, never use std::endl.

But if I had to guess, I would say your problem here isn't IOStreams, or I/O at all. I suspect most of your wasted cycles are spent in allocations. No way to be sure without profiling, but there's no point to me doing that, because my platform probably isn't the same as your target platform.

Summary

The real killer of performance here probably isn't low-level code issues or micro-optimizations. The real problem here is that unless my understanding of the problem is way off, you didn't take enough time to understand the problem before writing the first line of code.

The key to writing really good code is ironically not writing code; it's spending more time thinking about the problem you're trying to solve. That planing is the key to real performance. When trying to code something that needs to be extremely efficient, 90% of your time should be spent thinking about what you're trying to solve - without touching a single key on the keyboard. Then 9% of your time should be spent profiling and analyzing the profiler output. Only 1% of your time should actually be spent coding.

There are two serious problems with your code:

• You use a long for V when (I think; I'm assuming the formatting in the question is bad) a long is not guaranteed to be large enough for it. It might work on some systems, but those it doesn't, your program will go berserk. Just use a type guaranteed to be at least 64 bits, like long long or int_fast64_t, and you're fine.


• You never free any of the memory you allocate with new. (But you don't need to allocate any memory with new, so just don't do that and the problem goes away.)

There are a number of causes of inefficiency in your program:

• You duplicate the results you calculate in one vector into an entirely unnecessary second vector. If you're lucky this will only trigger an allocation in the first case. Still, you're paying for the copying in every case.


• You create a string variable outside of the loop - which is good, because it can reuse memory - but then you shadow it with another string variable inside the loop, losing that benefit and paying for a new allocation for every attraction. On top of that, you use an unnecessary getInput() function which further negates the possibility of reusing memory.


• You don't do any reserving of memory. For example, you know before you even start loading the attractions list that there will be N (or K - why did you have to go and mix those variables up?) attractions. So before you start loading, you should reserve N elements in the attractions vector. Failing to do that means that every single emplace_back() could be triggering a reallocation. (This might not be a major problem because you're reusing the vector, though.)

And as for general coding issues:

• There's not a single comment in the program, and many of the variables have useless names (struct values, auto print, bool minusOne), or incorrect or misleading names (like N and K being swapped). And there is some peculiar and complicated logic, with nested loops and so on, and things that appear to be vestigial entities from earlier attempts. If you leave this program for a month and come back to it, you're probably not going to have a clue how it works. Use meaningful variable names and comments to explain what's going on - don't spell out the stupidly obvious (like the infamous "i = i + 1; // adds 1 to i") but explain the meaning of what you're doing, and why it helps you get to whatever goal you're aiming for.


• Don't define things pages away from where they're actually used. sort_map, for example, is defined then not used until almost a hundred lines later... and then only that one time. That lambda can be defined right before the sort (or even used directly in the sort). Generally, if you define a variable, it's first use should be no more than 3-5 lines later, max. (There are exceptions to this rule when optimizing, such as moving variables out of loops, but those are exceptions, not the rule.)