Интерестная задачка, спортивное программирование, разобраться?

Готовлюсь к олимпиаде ACM и попал вот на такую задачку acmicpc-live-archive.uva.es/nuevoportal/data/probl...

В двух словах: в прямоугольной таблице n*m (1<=n<=1000, 1<=m<=20) чисел нам нужно найти столбец с максимальным произведением его елементов. Вроде бы простая задача, но в каждой клетке находится 32 битное целое число, их максимум 1000, получаем что максимальное произведение в столбце — 2^31000 что очень много и вынуждает использовать так называемую «длинную арифметику». Но в рейтинге у людей время выполнения 0,018, что для длинной арифметики мало, а значит есть более еффективный метод чем просто умножить и сравнить, да я и сам в это верю.


Вот и вопрос: есть ли еффективный способ сравнить 2 произведения, в каждом до 1000 множителей, каждый множитель по модулю максимум 2^31? Нам нужно сказать какое из них больше, само значение этих произведений нам не нужно.


Спасибо за внимание.
Update. Сайт лежит, вот условие задачи:


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

Задача A

Last Update


Задача сделана! Спасибо хабрачеловеку ! Он напомнил о этом методе с логарифмами, который я почему то сам раньше вычеркнул потому что не получилось + из-за погрешности и т.д. Но видимо задача расчитана именно на такой метод, по этому Accepted 0.018!!! Наконец то я успокоюсь, меня эта задача мучала)


Исходник:
#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++)) {};
   
}
  • Вопрос задан
  • 3117 просмотров
Решения вопроса 1
@MikeMirzayanov
Если тесты делали не с любовью, то пройдет такой вариант. Можно сравнивать столбцы по суммам логарифмов чисел в них. Надо быть аккуратным с отрицательными числами и нулем, но это детали. Вычисления лучше делать в long double (для C/C++). Вероятно, если подумать, то окажется что это предполагаемое решение.
Ответ написан
Пригласить эксперта
Ответы на вопрос 7
shushu
@shushu
Блин, несколько часов убил на задачку. Потом решил таки проверить с использованием «длинной арифметики», так сказать, в лоб и посмотреть сколько времени выполняется.

тестировал на java с использованием BigInteger

заполнение и вычисление:
        Random r = new Random();
        Vector< Vector<Integer> > nums = new Vector<Vector<Integer>>();
        long t = System.currentTimeMillis();
        System.out.println( "Starting generate example" );
        for( int column = 0; column < 20 ; column++ ){
            Vector<Integer> rows = new Vector<Integer>();
            for( int row = 0; row < 1000; row++ ){
                rows.add( r.nextInt() );
            }
            nums.add(rows);
        }
        long t2 = System.currentTimeMillis();
        System.out.println( "generate example finished at " + ( t2 - t ) );
        System.out.println( "Starting getAnswer" );
        System.out.println( p.getAnswer2(nums) );
        long t3 = System.currentTimeMillis();
        System.out.println( "getAnswer  finished at " + ( t3 - t2) );

getAnswer2 — банальное умножение в цикле и нахождение максимального результата.

вывод:
Starting generate example
generate example finished at 24
Starting getAnswer
13
getAnswer finished at 385


Время в милисикундах, на максимальных условиях, а 0,018 возможно была матрица не 20х1000?
Ответ написан
xappymah
@xappymah
После размышления понял оптимальный способ умножения. Немного похоже на способ с логарифмами выше, но более точный (без плавающих запятых и прочего).

Сначала посчитать примерный суммарный порядок числа, который получится после умножения, складывая количество цифр в каждом числе после самой первой (для 1000 -> 3, для 32132 -> 4. В сумме — 7).

После этого сразу отсечется часть.
Далее следует перемножить эти самые первые цифры и опять сравнить порядок.
Если еще останется кто-то, то опять перемножать, но уже следующий разряд.

И так далее.
В худшем случае, конечно, получится полное перемножение, но это будет fallback :)
Ответ написан
Комментировать
@agul
Задача почему-то не открылась, поэтому решаю задачу по вашему условию.

Раз таблица N*M, то максимум элементов в столбце = 20 (т.к. 1<=M<=20).

Вообще можно динамически раскладывать число на множители (не обязательно простые), затем просто сравнивать их количество и остаточные коэффициенты.

В принципе, можно грамотно написать длинную арифметику по основанию 109, которая будет быстро работать.
Ответ написан
mekegi
@mekegi
вместо длинного умножения используйте обычное, а чтобы не было переполнения делите каждое множимое на миллион.
Ответ написан
G0rDi
@G0rDi
Может я конечно туплю, но мне кажется можно посчитать сумму по столбцу и сумма какого столбца будет больше того и тапки. Предполагаю чем больше сумма тем больше произведение, но на ноль надо проверять если в столбце, он попался значит суммирование надо обнулить ) и продолжать складывать столбец по новой )
Ответ написан
xappymah
@xappymah
Могу предложить альтернативный вариант: быстрая сортировка всех столбцов по убыванию, а потом последовательное сравнение элементов. Соответственно, те столбцы, у которых в i-м ряду число меньше максимального для данного ряда, отпадают.
Ответ написан
@oandrew Автор вопроса
Вот тесты кстати нашлись. Добавил ссылку в шапке.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы