# Aliens at the train

I solved this problem on SPOJ:

The aliens have arrived to Earth and everything is in harmony, the two races can live together. However, one specific Female Alien does not want to see humans on her way to the university, the alien must use the train as every human does. But she can choose any train station such she doesn't see more than $B$ humans, however, the Alien wants to go as far as possible with the train. Please, help her in this task.

INPUT:

You will receive one integer $T$ denoting the number of test cases, then, the next line will contain two integers $A_t$ $B_t$ where $A_t$ and $B_t$ is the number of stations in the train ($1\leq A_t \leq100,000$) and the number of people that the alien wants to see as maximum ($1\leq B_t \leq10,000,000$), after that, one line containing $A_t$ integers separated by a single space will denote the number of people the Alien can find in the $A_t(i)$ station. (For each station there will be as much 100 people.)

OUTPUT:

Your output should consist on $T$ pair of numbers denoting the number of people the alien will see and the number of stations she will pass respectively.

EXAMPLE Input / Output:

INPUT:

1
5 100
20 15 30 80 100


OUTPUT

65 3


My solution was just on the border of the time limit. I want to know of any improvements for my code in the context of competitive programming and the C/C++ languages.

How can I speed up the I/O and how can I shorten my code?

#include <cstdio>
#include <deque>
using namespace std;

int main()
{
int t,siz;
scanf("%d",&t);
long long int at,bt,sum=0,max=0,maxsum=0,peep=0;
deque<int> people;
while(t--){
sum=max=maxsum=peep=0;
people.clear();
scanf("%lld%lld",&at,&bt);
while(at--){
scanf("%lld",&peep);
people.push_back(peep);
if(sum+peep<=bt)
{
sum+=peep;
}
else{
siz=people.size()-1;
if(max==siz){
maxsum=maxsum<sum?maxsum:sum;
}
else if(max<siz){
maxsum=sum;
max=siz;
}
sum+=peep;
while(sum>bt){
sum-=people.front();
people.pop_front();
}
}
}
siz=people.size();
if(max==siz){
maxsum=maxsum<sum?maxsum:sum;
}
else if(max<siz){
maxsum=sum;
max=siz;
}
printf("%lld %lld\n",maxsum,max);
}
return 0;
}

• Use spaces, e.g. maxsum < sum ? maxsum : sum instead of maxsum<sum?maxsum:sum. – kenorb Aug 8 '14 at 16:18
• LOL, I thought this Q is about XCOM: Enemy Unknown :-) – Free Consulting Aug 8 '14 at 21:53

You're likely to be correct that the main performance bottleneck is I/O in this program. For that reason, you might consider doing one or more of the following:

## Read a line at a time

Try using fgets to fetch a line at a time and then use sscanf to parse the numbers from the buffer. This may be particularly useful for reading the train station line.

## Roll your own scanf replacement

The scanf function is useful but general purpose. A faster special purpose sscanf replacement function which also does very little error checking, would be this:

const char *fetchnum(const char *buffer, long long int *n)
{
for (*n = 0; *buffer >= '0' && *buffer <= '9'; buffer++)
*n = 10 * (*n) + (long long int)(*buffer - '0');
return ++buffer;
}


## Consider doing lower level I/O

Right now, your code uses the relatively high level scanf function, but you might find a performance gain using lower level calls such as read and then parsing the lines in memory.

• +1 for lower-level IO; for large input, this gives a much bigger performance boost than some may think. – Schism Aug 8 '14 at 16:10

Do not use using namespace std

It is not really such a big deal here but using namespace std; is usually considered bad practice.

You are using C++, deal with stdio the C++ way

Instead of playing with scanf, you can use the stream operators.

Indentation seems a bit awkward in your code. Use your favorite text editor to fix this.

Define your variables in the smallest possible scope

It will make things easier to understand but it will also remove need for re-initialising variables.

At this stage, your code looks like :

#include <iostream>
#include <deque>

int main()
{
int t;
std::cin >> t;
while(t--){
std::deque<int> people;
long long int at,bt,sum=0,max=0,maxsum=0;
std::cin >> at >> bt;
while(at--){
long long int peep;
std::cin >> peep;
people.push_back(peep);
if(sum+peep<=bt)
{
sum+=peep;
}
else{
int siz=people.size()-1;
if(max==siz){
maxsum=maxsum<sum?maxsum:sum;
}
else if(max<siz){
maxsum=sum;
max=siz;
}
sum+=peep;
while(sum>bt){
sum-=people.front();
people.pop_front();
}
}
}
int siz=people.size();
if(max==siz){
maxsum=maxsum<sum?maxsum:sum;
}
else if(max<siz){
maxsum=sum;
max=siz;
}
std::cout << maxsum << " " << max << std::endl;
}
return 0;
}

• Since the OP goal is speed not (the more normal maintainability) I don't agree with all the Define your variables in the smallest possible scope. Doing this has the cost of constructor/destructor calls. The original design of declaring people in the outer scope and calling people.clear() seems more appropriate. – Martin York Aug 8 '14 at 11:15
• As the ultimate goal is speed remember to un-sync the C and C++ streams (this makes C/C++ stream have equivalent speed) by calling std::ios_base::sync_with_stdio(false);. See Difference in execution time in C and C++. – Martin York Aug 8 '14 at 11:18
• Well, to be fair, I was performing little changes in order to get a better understanding of the algorithm used to be able to improve it. On that kind of challenges, real improvements come from a change in the algorithm more than from micro-optimisations. This being said, I didn't know about sync_with_stdio so I am glad I learnt something today. – SylvainD Aug 8 '14 at 12:57
• @LokiAstari Moving variables at smaller scope doesn't necessarily make the program less efficient. It affects the semantics of the program in general, rather than the actual code generated after optimization. As for constructors/desctructors, you only get a new/delete per test case, whereas the current code has a resize operation per inner iteration anywhay (which I have removed in my answer). – iavr Aug 9 '14 at 0:10
• @ivar: I am only looking at this from a speed perspective. One should not dismiss micro optimizations without first timing. By moving the people structure in one scope level you are swapping a clear() for two calls deque<int>() and ~deque<int>() both of which do significant memory management operations (not simple and unlikely to be optimized out). Also the clear() call is not required to release the memory associated with the container and thus on subsequent loops may reuse the memory rather than re-aquire more dynamic memory. – Martin York Aug 9 '14 at 3:23

I don't have anything to add regarding performance, but I have some advice so that your program is easier to read. And programs easier to read are often easier to understand, and therefore easier to improve:

• Since you are adding elements at the end of your std::deque and removing them from the front, I guess that what you really need is a std::queue. It won't make any performance improvement since std::queue uses a std::deque, but it could make your code cleaner. Just replace std::deque by std::queue and the push_back and pop_front operations by push and pop. That actually makes one more indirection, but all the operations should be inlined, so this small wrapper shouldn't make your code any slower.

• This piece of code:

maxsum=maxsum<sum?maxsum:sum;


can be replaced by this one:

maxsum = std::min(maxsum, sum);


There shouldn't be any performance benefits, but there shouldn't be any performance loss either. The chances are that std::min uses a ternary and the call to std::min is inlined by the compiler. Honestly, it makes the code more readable; since you are using a variable called maxsum here, I was convinced at first that what you were doing was a max operation. Explicitly using std::min avoids this possible misunderstanding.

• You don't need return 0; at the end of main. It will be automatically added by the compiler if it reaches the end of main without having found any return statement.

As I said, none of these changes should have any impact on performance. You will only improve the readability. And since I like to repeat myself: the more readable your code, the more understandable, the more likely to be improved.

• "You don't need return 0; at the end of main. It will be automatically added by the compiler if it reaches the end of main without having found any return statement." This depends entirely on which compiler you use. For example, Visual Studio will just yell at you for being lazy. – Pharap Aug 9 '14 at 11:31
• @Pharap That seems strange considering that the online example of Visual Studio (2013CTP) is a simple Hello World program that does not explicitly return anything from main. And it doesn't yell at me. – Morwenn Aug 9 '14 at 11:41

Your code is one big function all in main().

• Create C++ classes that hold data and have methods to perform the computations on the data and give them meaningful descriptions.

I don't actually understand the problem or what the algorithm is you are using to solve it.

I would say use streams rather than scanf / printf. I doubt it is the I/O that is making it slow. More likely to be the algorithm.

As an algorithm, it looks correct and efficient enough to me. Well done.

As a program, here's how I would reformulate it:

#include <iostream>
#include <vector>

namespace test {

using namespace std;

struct alien
{
int max_sum, max_length;

void update(int sum, int length)
{
if (max_length == length)
max_sum = min(max_sum, sum);
else if (max_length < length)
{
max_sum = sum;
max_length = length;
}
}

alien()
{
int cases;
cin >> cases;

while (cases--)
{
int stations, max_people;
cin >> stations >> max_people;
vector<int> people(stations);
for (auto& p: people)
cin >> p;

int sum = 0;
max_sum = max_length = 0;
auto enter = people.begin(), leave = enter;

while (leave != people.end())
{
int prev_sum = sum;
if ((sum += *leave++) <= max_people)
continue;

update(prev_sum, leave - enter);
while (sum > max_people)
sum -= *enter++;
}

update(sum, leave - enter);
cout << max_sum << " " << max_length - 1 << endl;
}
}
};

}  // namespace test

int main() { test::alien(); }


It may be longer than yours in terms of lines of code, but it's more structured, less redundant, and probably easier to follow.

I have used modern, high-level C++ conventions where possible, and tried to choose self-documenting variable names, moving their declarations as close as possible to their use. I have kept using namespace std for all its convenience, but only inside my own namespace test, so no harm done. Note that you don't need long long for the given bounds.

I have separated input reading from actual computations. I have stored all input in advance in vector people, which doesn't have to resize after that, because I am referring to its two ends by iterators enter, leave, both moving forward. This should have an impact on performance. The difference leave - enter is the number of stations our alien has travelled. Because leave is in fact one-past-the-end position, we subtract 1 when printing.

I have moved the redundant code in function update, which is now called twice. In order not to pass too many arguments around, I have kept state in two variables max_sum, max_length. For this reason, everything is now in class alien, whose constructor does the actual computation.

I prefer to break in the middle of the loop with continue in order to avoid too many nested scopes. I don't check before updating the sum; I just keep its previous value in prev_sum, thus making only one addition. Of course, this is a job of the optimizer anyway.

It may be possible to re-write everything without loops, utilizing standard algorithms like std::accumulate, std::find_if etc. along with lambdas. I have not tried to be too smart in that respect, remaining closer to your code.

• Doing basically everything in a constructor, though? I/O and all? :P – cHao Aug 10 '14 at 11:04
• "I have used modern, high-level C++ conventions where possible" Putting everything in a constructor is definitely not the "modern, high-level C++ convention." And using namespace std; ... – L. F. Aug 1 at 5:42

Some time ago I have started to write lightweight fast io header only library. Very useful for competitions like spoj. It's just really start of my work (I don't have to much time) but you can try it (just copy the source at the begining and use): https://github.com/adamf88/Algorithms/blob/master/fastio.h

My optimization of your code (all optimizations, are low level):

1. Instead of using deque, I have used simple array with maximum size to avoid memory allocations. The code is not as simple as previous, and I had to add two new variables to manage my queue manually (variables begin and end).
2. I have changed long long type to unsigned int (it's enough after checking the task limitations)
3. Instead of using cin/cout, I have created few functions to read unsigned int value based on fread function and with most simple parsing it. fread is even faster than scanf. The buffer size I have chosen manually.

My solution takes 0.01ms:

#include <stdio.h>

//---- fast io  begin
#define BUF_SIZE 4000
char bufor[BUF_SIZE + 1 + 30];
char *buf_pointer;
char *end_pointer;

bool end_of_buffer()
{
return buf_pointer == end_pointer;
}

void init()
{
buf_pointer = bufor;

{
--end_pointer;

while ((*end_pointer & 16) && readed)
{
++end_pointer;
}

if (*end_pointer & 16)
{
++end_pointer;
*end_pointer = ' ';
}

for (; (*buf_pointer & 16) == false;)
{
++buf_pointer;
if (buf_pointer >= end_pointer)
{
init();
}
}
}
}

{
char *data = buf_pointer;

l = 0;
while (*data & 16)
{
l *= 10;
l += *data & 15; //-40
++data;
}

for (; (*data & 16) == false;)
{
++data;
if (data >= end_pointer)
{
init();
data = buf_pointer;
}
}

buf_pointer = data;
}

//---- fast io end

unsigned int q;
int main()
{
init();
unsigned int n;
while (n--)
{
unsigned int a, b, begin = 0, end = 0;
unsigned int best_sum = 0, cur_sum = 0, best_len = 0;

while (a--)
{
cur_sum += q[end];
++end;

while (cur_sum > b)
cur_sum -= q[begin++];

int q_size = end - begin;
if (best_len < q_size)
{
best_len = q_size;
best_sum = cur_sum;
}
else if (q_size == best_len && best_sum > cur_sum)
{
best_sum = cur_sum;
}
}
printf("%u %u\n", best_sum, best_len);
}
}

• If you wish to provide your own implementation, then you must also explain how it improves upon the OP's code. Otherwise, it would be considered a non-answer. – Jamal May 18 '15 at 20:45