Interesting problem, sports programming, understand?

Question

Programming

I'm getting ready for the ACM Olympiad and I got this problem acmicpc-live-archive.uva.es/nuevoportal/data/probl...
In a nutshell: in a rectangular table n*m ​​(1<=n<=1000, 1<= m<=20) numbers, we need to find a column with the maximum product of its elements. It seems to be a simple task, but in each cell there is a 32-bit integer, their maximum is 1000, we get that the maximum product in the column is 2 ^ 31000, which is a lot and forces us to use the so-called "long arithmetic". But in the ranking of people, the execution time is 0.018, which is not enough for long arithmetic, which means there is a more efficient method than just multiplying and comparing, and I myself believe in it.
So the question is: is there an efficient way to compare 2 products, each with up to 1000 factors, each factor modulo a maximum of 2^31? We need to say which of them is greater, we do not need the very meaning of these works.
Thank you for your attention.
Update . The site lies, here is the condition of the problem:
Consider the table of 32-bit signed integers with n rows and m columns. The columns are numbered from 1 to m beginning from the left side of the table. Let Ai (1im) is the product of all numbers in the i-th column. Find the maximum of these products and print the column number where this maximum product is achieved. If there are many such columns, print the largest number of the column.
Input
Consists of multiple tests. Each test begins with a line with two integers m and n (1<=m<=20, 1<=n<=1000). Each of the next n lines contains m 32-bit signed integers.
Output
For each test case print on a separate line the column number with the maximum product. If there are several of them - print the largest number of such column.
Sample Input
3 3
20 10 30
15 20 20
30 30 20
3 2
2 -2 2
2 -2 2
Sample Output
3
3
Update 2
acm.ro/prob/ACMproblems2010.zip
Task A
Last Update
Task done! Thanks habraman! He reminded me about this method with logarithms, which for some reason I crossed out earlier because it didn’t work out + because of the error, etc. But apparently the task is designed specifically for this method, so Accepted 0.018 !!! Finally, I will calm down, this task tormented me)
Source:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

struct col {
    long double lg;
    int sign;
    col() {
        lg = 1;
        sign = 1;
    }
    
};


bool solve(int test) {
    col cols[20];
    int m,n;
    if( scanf("%d %d",&m,&n) != 2) return false;
    
    long long x;
    for(int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            
            scanf("%lld",&x);
            if(cols[j].sign == 0) {continue;}
            
            if(x==0) {
                cols[j].sign = 0;
                continue;
            } else if(x<0) {
                x=-x;
                cols[j].sign *= -1;
            } 
            
            cols[j].lg += log((long double)x);
                
        }
    }
    
    int max = 0;
    for(int i=1;i<m;i++) {
        if(cols[i].lg*cols[i].sign >= cols[max].lg*cols[max].sign) {
            max = i;
        }
    }
    max++;
    printf("%d\n",max);
    

    return true;
        
}


int main() {
    int c=1;
   while(solve(c++)) {};
   
}

Answer 1

If the tests were not done with love, then this option will pass. You can compare columns by the sums of the logarithms of the numbers in them. You have to be careful with negative numbers and zero, but these are details. Calculations are best done in long double (for C/C++). Probably, if you think about it, it turns out that this is the intended solution.

Answer 2

After thinking, I figured out the best way to multiply. A bit like the logarithm method above, but more accurate (no floating points, etc.).
First, calculate the approximate total order of the number that will be obtained after multiplication, adding the number of digits in each number after the very first one (for 1000 -> 3, for 32132 -> 4. In total - 7).
After that, the part will immediately be cut off.
Next, you should multiply these very first numbers and again compare the order.
If there is still someone left, then multiply again, but already the next digit.
Etc.
In the worst case, of course, you will get a full multiplication, but it will be a fallback :)

Answer 3

For some reason, the task did not open, so I solve the problem according to your condition.
Since the table is N*M, then the maximum of elements in the column = 20 (because 1<=M<=20).
In general, you can dynamically decompose a number into factors (not necessarily prime ones), then simply compare their number and residual coefficients.
In principle, it is possible to correctly write long arithmetic in base 10 ⁹ that will work quickly.

Answer 4

instead of a long multiplication, use the usual one, and to avoid overflow, divide each multiplier by a million.

Answer 5

Maybe I'm stupid, of course, but it seems to me that you can calculate the sum of the column and the sum of which column will be more than that and slippers. I suppose the larger the sum, the greater the product, but you need to check for zero if it is in the column, it means that the summation must be reset to zero) and continue to add the column over again)

Answer 6

I can offer an alternative: quick sorting of all columns in descending order, and then sequential comparison of elements. Accordingly, those columns whose number in the i-th row is less than the maximum for the given row are discarded.

Answer 7

Here are the tests by the way. Added a link in the header.