Matematické Fórum

Lancelot · 27. 02. 2014 18:59

Zdravím,

řeším následující problém. Mám zadaný na vstupu matici čísel N*N a mým úkolem je rozdělit tuto matici na 4 části. Rozdělení si představte tak, že celou matici někde rozpůlíme horizontální čárou a obě zbývající části se rozdělí čárou vertikální. V každé té části se zadaná čísla sečtou a musí se to rozdělit tak, že rozdíl nejmenšího a největšího součtu bude co nejmenší. Např. když budeme mít součty -5, 10, 7, 12, tak rozdíl je roven 17, což je výsledek celé úlohy. Navíc musí být celý algoritmus velice rychlý, tedy tak, aby se asymptotická složitost moc nezvětšovala se zvětšujícím se počtem vstupních dat.

A abych nevypadal, že jsem nad tím nepřemýšlel, tak můžu říct, že jsem vymyslel nejdřív 1. algoritmus, který byl ale hrozně pomalý, když jsem zadával matici více než 600x600. Tak jsem ho celý smazal a vymyslel další. Tady je:

Code:

package alg;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int n = Integer.parseInt(sc.nextLine());
        
        int[][] pole = new int[n][n];
        
        long sum4 = 0;
        
        for(short i = 0; i < n; i++){
                String s = sc.nextLine();
                String mezera = " ";
                int index = 0;
                                                
                for(short j = 0; j < n; j++){
                    String cislo = "";
                    
                    while(mezera.equals(String.valueOf(s.charAt(index))))
                        index++;
                    
                    while(!(mezera.equals(String.valueOf(s.charAt(index))))){
                        cislo += s.charAt(index);
                        index++;
                        if(index >= s.length()) break;
                    }
                    
                    int prvek = Integer.parseInt(cislo);
                    pole[i][j] = prvek;
                    //sum4
                    sum4 += prvek;
                }            
                
        }
            
        
        long sum2 = 0, sum1 = 0, sum3 = 0;
        long sum24Min = Integer.MAX_VALUE, sum12Min = Integer.MAX_VALUE, sum34Min = Integer.MAX_VALUE;
        long pomocnaSum1 = 0, pomocnaSum2 = 0, pomocnaSum3 = 0, pomocnaSum4 = 0;
        int pomocnaI = 0;    
        
        //sum2 a sum4
        for(short i = 0; i < n-1; i++){
            for(short j = 0; j < n; j++){
                if(pole[i][j] == 0) continue;
                sum2 += pole[i][j];
                sum4 -= pole[i][j];
            }
            
            long min, max, rozdil;
            if(sum2 < sum4){
                min = sum2;
                max = sum4;
            } else {
                min = sum4;
                max = sum2;
            }
            
            rozdil = max - min;
            if(rozdil < sum24Min){
                sum24Min = rozdil;
                pomocnaI = i;
                pomocnaSum2 = sum2;
                pomocnaSum4 = sum4;
            }
            
            if(sum4 == 0) break;
        }
        
        sum2 = pomocnaSum2;
        sum4 = pomocnaSum4;
        
        
        //sum 1 a 2
        for(short j = 0; j < n-1; j++){
            for(short i = 0; i <= pomocnaI; i++){
                if(pole[i][j] == 0) continue;
                sum1 += pole[i][j];
                sum2 -= pole[i][j];
            }
            
            long min, max, rozdil;
            min = Math.min(sum1, sum2);
            max = Math.max(sum1, sum2);
            
            rozdil = max - min;
            if(rozdil < sum12Min){
                sum12Min = rozdil;
                pomocnaSum1 = sum1;
                pomocnaSum2 = sum2;
            }    
            
            
            for(short i = (short)(pomocnaI + 1); i < n; i++){
                if(pole[i][j] == 0) continue;
                sum3 += pole[i][j];
                sum4 -= pole[i][j];
            }
            
            long min1, max1, rozdil1;
            min1 = Math.min(sum3, sum4);
            max1 = Math.max(sum3, sum4);
            
            rozdil1 = max1 - min1;
            if(rozdil1 < sum34Min){
                sum34Min = rozdil1;
                pomocnaSum3 = sum3;
                pomocnaSum4 = sum4;
            }    
        }
        
        
        long min, max, result;
        min = Math.min(Math.min(pomocnaSum1, pomocnaSum2), Math.min(pomocnaSum3, pomocnaSum4));
        max = Math.max(Math.max(pomocnaSum1, pomocnaSum2), Math.max(pomocnaSum3, pomocnaSum4));
        
        result = max - min;
        
        System.out.println(result);
        
        sc.close();
        
    }
}

Sum1 - rozdělení nahoře vlevo
Sum2 - rozdělení nahoře vpravo
Sum3 - rozdělení dole vlevo
Sum4 - rozdělení dole vpravo
V principu jde o to, že na začátku spočítám sum4, což bude součet všech čísel dohromady. Poté začnu počítat sum2 a sum4 tak, že od sum4 postupně odčítám řádky od shora a zároveň ty řádky přičítám do sum2. Po uplynutí cyklu zjistím, kdy se ty 2 sumy od sebe liší minimálně, přičemž to pro mě bude rozdělení v horizontálním směru.

Ostatní sumy se řeší stejně, akorát se jedná o vertikální rozdělení, takže se matice prochází obráceně.

Početně je všechno v pořádku, počítá mi to správně, i když je objem dat např. 2000x2000. Jenže algoritmus není dostatečně rychlý (potřebuju ho zrychlit minimálně o 0,1s). Už jsem zkoušel spoustu věcí, ale ani jedna mi nepomohla a už mě nic nenapadá. No a moc se mi nechce celý algoritmus zase smazat a začít od znova...

Předem děkuji za odpověď.

Lancelot · 27. 02. 2014 21:05

Tak jsem to nakonec vyřešil sám. Já totiž úplně zapomněl na fakt, že Scanner je hrozně pomalej. Tak jsem místo scanneru použil BufferedReader, který mi načtení všech dat o dost zrychlil. Určitě by šlo ale celý alogirtmus ještě o něco zrychlit, takže pokud někoho něco napadne, tak to sem klidně může hodit. Hodně mě to zajímá.

check_drummer · 28. 02. 2014 14:11

↑ Lancelot:
Ahoj, jsou čísla jen kladná (nezáporná) a nebo mohou být i záporná?

Lancelot · 28. 02. 2014 15:11

↑ check_drummer:
Čísla mohou být i záporná, konkrétně jsou z intervalu <-10^6, 10^6>, přičemž výsledné číslo (tedy ten výsledný rozdíl) bude už číslo nezáporné.

Bati · 28. 02. 2014 18:14

↑ Lancelot:
Ahoj,
nemám čas zkoumat detaily tvého řešení, takže možná napíšu něco, co už víš, ale nastíním, jak bych asi postupoval já.

Nejprve bych vyřešil úlohu v jednorozměrném případě (tedy pro posloupnost délky N). Tvrdím, že se složitostí 2N jsem schopen najít optimální dělící místa. Nejprve spočítám součet všech čísel a dám před to mínus, což bude vlastně bilance levá strana mínus pravá, kde dělící místo je úplně nazačátku. Teď jen projíždím čísla zleva a přičítám dvojnásbek jejich hodnoty k aktuální bilanci. Zároveň si pamatuju na jaké pozici byla v absolutní hodnotě nejmenší bilance. Nyní bych se to pokusil zobecnit na matici, i když se přiznám, že mě zatím nic jednoduchého nenapadá.

lpis · 28. 02. 2014 19:36

bati, to tvoje reseni by se dalo elegentne vyresit pres frobeniovu normu=energii matice a skrze euklidovskou normu radku a sloupcu matice....

1, to jsou realna , nebo cela cisla?
2, kde se toto uplatnuje? vstup jsou ciste random ccisla? muze nastat situace ze jen jedno cislo muze mit vetsi velikost nez soucet vsech ostattnich?
3, proc to vubec delate v JAve? java je vyssi prog. jazyk, ktery se preklada z 'poloviny' v c++ by ten kod bezel na stejnem stroji i 11 krat rychleji, doporucuji knihovnu Eigen> jsou zde velice optiamliozvane template instrukce.... pokud vam tedy jen o optimalizaci,

Lancelot · 01. 03. 2014 03:11

↑ lpis:
Cisla jsou celá, tedy integer v intervalu <-10^6, 10^6>. No a v javě to programuju, protože javu znám lépe než jazyk C a C++. Jde o to, že jsem v prvním ročníku na VŠ a dříve jsem nic neprogramoval. Ale určitě se mrknu na to řešení i v C++, jak jsi navrhnul, jen si budu muset něco dostudovat.

Matematické Fórum

#1 27. 02. 2014 18:59

Optimální rozdělení matice čísel N*N

Code:

#2 27. 02. 2014 21:05

Re: Optimální rozdělení matice čísel N*N

#3 28. 02. 2014 14:11

Re: Optimální rozdělení matice čísel N*N

#4 28. 02. 2014 15:11

Re: Optimální rozdělení matice čísel N*N

#5 28. 02. 2014 18:14

Re: Optimální rozdělení matice čísel N*N

#6 28. 02. 2014 19:36

Re: Optimální rozdělení matice čísel N*N

#7 01. 03. 2014 03:11

Re: Optimální rozdělení matice čísel N*N

Zápatí