Thread: input files using command line arguments possible?

Maybe two of your inputs are overflowing and your prefix_sum_array should be long long? It looks like you could use just one array, too.

Hey bruteforce, thanks for your help. I tried long long too but it says the answer is wrong. About using one array, I also did that but it's still wrong.
Here's the code using one array instead of two(if I'm not mistaken in understanding what you meant):

Code:

#include <stdio.h>
#include <stdlib.h>


void to_prefix_sum_array(long long int *values, int count);


int main() {
    int n;
    scanf("%d", &n);
    long long int *values = malloc(n * sizeof(long long int));
    for (int i = 0; i < n; i++) {
        scanf("%lld", &values[i]);
    }


    to_prefix_sum_array(values, n);
    long long int best;
    long long int special_sum = values[0];
    int step_length = 2;
    for (int j = 2; j < n; j += step_length) {
        special_sum += values[j] - values[j - step_length];
        step_length++;
    }
    best = special_sum;
    for (int i = 1; i < n; i++) {
        special_sum = 0;
        step_length = 1;
        for (int j = i; j < n; j += step_length) {
            special_sum += (values[j] - values[j - step_length]);
            step_length++;
        }
        if (special_sum > best) { best = special_sum; }
    }


    free(values);


    printf("%lld", best);
    return 0;
}


void to_prefix_sum_array(long long int *values, int count) {
    for (int i = 1; i < count; i++) {
        values[i] = values[i - 1] + values[i];
    }
    return;
}

This seems to work. I started with your code but tried to simplify it, to my eyes at least, and debug it. I can't remember all that I changed but maybe you can compare it to yours to see the difference. I haven't actually run it on that site, though, so let me know if it even works! I also removed the free as a bit of an "optimization" (maybe) since the system will clean up the memory for you.

Code:

#include <stdio.h>
#include <stdlib.h>
 
int main() {
    int n;
    scanf("%d", &n);
 
    long long v, *values = malloc(n * sizeof *values);
 
    scanf("%lld", &values[0]);
    for (int i = 1; i < n; i++) {
        scanf("%lld", &v);
        values[i] = values[i - 1] + v;
    }
 
    long long best = values[0];
    for (int j = 2, step = 2; j < n; j += step) {
        best += values[j] - values[j - step];
        step++;
    }
 
    for (int i = 1; i < n; i++) {
        long long sum = values[i] - values[i - 1];
        for (int j = i + 2, step = 2; j < n; j += step) {
            sum += values[j] - values[j - step];
            step++;
        }
        if (sum > best)
            best = sum;
    }
 
    printf("%lld\n", best);
 
    return 0;
}

Here's a bit more of a simplification. I still haven't tested it except for the 2 little examples since the site wants me to join to do more.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
int main() {
    int n;  // 1 <= n <= 100000
    scanf("%d", &n);
 
    long long v, *values = malloc((n + 1) * sizeof *values);
 
    values[0] = 0;
    scanf("%lld", &values[1]);
    for (int i = 2; i <= n; i++) {
        scanf("%lld", &v); // -10000000 <= v <= 10000000
        values[i] = values[i - 1] + v;
    }
 
    long long best = LLONG_MIN;
    for (int i = 1; i <= n; i++) {
        long long sum = values[i] - values[i - 1];
        for (int j = i + 2, step = 2; j <= n; j += step)
            sum += values[j] - values[j - step++];
        if (sum > best)
            best = sum;
    }
 
    printf("%lld\n", best);
 
    return 0;
}

The interesting thing that I can not still understand is your code and my code both give 419872311 as the result of the 11th input on my own computer (tried that using cat input11.txt | ./program) however your answer gets accepted on the site outputting 2683246 and mine gets rejected outputting 2386270 and neither is the number 419872311 that I said both of them give on my own computer. o-O

Originally Posted by narniat

I will not submit it because it's not my own work but I compiled it using custom input and gave the exact input (the 11th one) that failed my code to it and it works perfectly! It's even faster than the best answer I guess!!!

I doubt it's faster than all the other answers. And it is 90 percent your code, really, since I didn't think about how to solve the problem at all but just followed your very good idea. I only added at most 10 percent, so you certainly have my permission to submit it and I think it is fair enough that you do.


Starting the array with a 0 value and starting the "best" at LLONG_MIN is just a trick to get rid of the duplicated code. I can't say that this version is actually an improvement on the previous one and the previous one is even closer to your original code and should be just as fast.

Originally Posted by narniat

The interesting thing that I can not still understand is your code and my code both give 419872311 as the result of the 11th input on my own computer (tried that using cat input11.txt | ./program) however your answer gets accepted on the site outputting 2683246 and mine gets rejected outputting 2386270

That's strange. I was going to say maybe your computer is 32-bits, but long long should be 64 bits even on a 32-bit machine. Is your computer 64 bits? What OS? What compiler?

You could try ./program < input11.txt instead, but I don't think it should make a difference.

Maybe you have a corrupted version of the input. Try downloading the file again. If the problem persists, you could upload that file somewhere and I could try it.

Yes this is strange. No my computer is 64 bits, my OS is Windows10 but indeed I should say it's Ubuntu since I'm using WSL (which is a Linux distribution developed by Microsoft for Windows users, it's not a virtual machine, it's exactly an Ubuntu and for example, although it's installed in C, but hard drives like C,D,E... are mounted on it in /mnt directory. It's weird for me but it's true , here's my `uname -a`:"Linux DESKTOP-QOJFPAF 4.4.0-17134-Microsoft #345-Microsoft x86_64 GNU/Linux") and the compiler I use is GCC (gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0). I also tried `./program < input11.txt` as you said and the same number: 419872311. (It's very difficult to say there's a problem in the site's compiler since they are experts but I also had an obvious issue on another problem, so... MAYBE THEY really have an issue...). About uploading the file that you said, I don't think it's needed, because there's a direct link to it even if you're not logged in to the website, here's the link: (https://he-s3.s3.amazonaws.com/media...ICDAQTL3Q6ZBKA) (Please tell me in case it doesn't work.)(Thanks)

(Something funny in parentheses: I submitted it and then checked answers of others to see how everyone else has solved it and then saw someone has just submitted the same answer as mine (copy pasting from here) even sooner than myself LOL, I think I'll be jailed in future for plagiarism from him)

Best Index | Basics of Input/Output & Basic Programming Practice Problems | HackerEarth

"You are given an array of elements. Now you need to choose the best index of this array . An index of the array is called best if the special sum of this index is maximum across the special sum of all the other indices."

Interesting, but I don't understand the exercise really. This example is clear, that have I understand . . .

Input6
-3 2 3 -4 3 1
Output
3

... but why is the solution 8 and 9

5
A1 - 1 + 3 + 1 + 2 + 5 = 12
A2 - 3 + 1 + 2 + 5 = 11
A3 - 1 + 2 + 5 = 8
A4 - 2 + 5 = 7
A5 - 5

Why is the solution here 8?

Thanks!