Rəssamın Bölmə Problemi

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Kod milləti google
İkili axtarış Bölün və fəth edin Dinamik proqramlaşdırma AxtarışBaxılıb 68

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Painter's Partition problemində bəzi çitlerimizin və bəzi rəssamlarımızın olduğu bildirilir. Rəssamların bütün çəpərləri boyamaq müddətini minimuma endirmək istəyirik. Çəpərlərin rəssamlar tərəfindən rənglənməsinin qaydasında bir məhdudiyyət var. N rəngkarımız olduğunu düşünək, 'i' indeksli rəngkar çitleri yalnız davamlı qaydada boyaya bilər.

Beləliklə, bu deməkdir ki, ilk rəssam çəpərlərin bir hissəsini çəkəcəkdir. Sonra ikinci rəssam çəpərlərin bir hissəsini rəngləyir. Eyni şey bütün rəssamlara aiddir. Bu, bəzi rəssamların boya üçün bir çit almaması ilə baş verə bilər.

misal

Rəssamın Bölmə ProblemiPin

Size of fence : 10 40 40 10 
Time of painting a unit length of fence : 1
Number of Painters : 2
50

İzahat: Çit 1 və 2-i birinci rəssamın, 3, 4-ünün ikinci rəssamına verəcəyik. Birinci hasara birinci, ikinci rəssam üçün 1, 2 və 3 hasar təyin etsəydik. Sonra birinci rəssam vaxt alır = 4, digəri isə vaxt alır = 10. Bütün rəssamların çəkdiyi maksimum vaxt hasarın çəkilməsinə çəkilən ümumi vaxtdır. Bunun səbəbi, rəssamların hamısının eyni vaxtda t = 90 şəklini çəkməyə başlamalarıdır. Beləliklə, bundan başqa yol daha pis nəticələrlə nəticələnəcəkdir.

Size of fence : 1 100 
Time of painting a unit length of fence : 1 
Number of Painters : 2
100

İzahat: Çit 1-i birinci, ikinci rəssam üçün 2 təyin edəcəyik. Ümumi vaxt rəssamlardan hər hansı birinin çəkdiyi maksimum vaxta bərabər olduğundan. Beləliklə, çıxış 100-dir.

Rəssamın bölmə problemi üçün yanaşma

Biz istifadə edəcəyik Dinamik proqramlaşdırma bu problemin həlli üçün. Burada, çox yaxşı təyin olunmuş bir şəkildə istifadə edəcəyik dinamik proqramlaşdırma zaman cəmini O (1) zaman mürəkkəbliyində götürmək üçün texnika (prefiks cəmi). Əvvəlcə problemi tək bir rəssam üçün həll edəcəyik. Sonra rəssam sayı = 2, 3, 4,… n üçün aşağıdan yuxarıya doğru həll edəcəyik. Bir sənətkar üçün problemi həll etmək üçün, sənətkarın k ilə j arasında hasar çəkmək üçün çəkdiyi vaxtı tapacağıq. Budur, rəssam k ilə j arasında çəpər çəkəcəyini və 1-dən (k-1) -ə qədər çəpərlərin (i-1) rəngləyicilər tərəfindən rəngləndiyini düşündük. Bu alt problemin cavabı (i-1) rəssamların hər biri və ya rəssam tərəfindən çəkilən maksimum vaxt olmalıdır. Bu şəkildə daha kiçik alt problemlərin həllinə davam edirik. Sonra bu kiçik alt problemlərin nəticəsini birləşdirərək ilk problemimizi (rəssamın bölmə problemi) həll edirik.

Kodu

C ++ kodu rəssamın bölmə problemi üçün

#include <bits/stdc++.h>
using namespace std;

long long int solvePaintersPartitionProblem(long long int numberOfPainters, long long int timePerUnit, vector<long long int>& fenceSize){
    int numberOfFences = fenceSize.size();
    if(numberOfFences == 0)return 0;

    vector<long long int> pref(numberOfFences); // stores the prefix sum for faster sum calculation over the range

    pref[0] = (fenceSize[0] * timePerUnit);
    for(int i=1;i<numberOfFences;i++) {
        pref[i] = (fenceSize[i] * timePerUnit);
        pref[i] = (pref[i] + pref[i-1]);
    }

    long long int dp[numberOfPainters][numberOfFences]; // dp[i][j] = minimum time taken for painting j fences by i painters such that they can paint only in contiguous order
    for(int i=0;i<numberOfPainters;i++){
        for(int j=0;j<numberOfFences;j++)
            dp[i][j] = LONG_MAX;
    }

    // Filling the values for first painter
    for(int i=0;i<numberOfFences;i++)dp[0][i] = pref[i];

    // Now solving for painters 2, 3, 4......n
    for(int i=1;i<numberOfPainters;i++){
        for(int j=i;j<numberOfFences;j++){
            for(int k=i;k<=j;k++){
                long long int timeTakenForithPainter = pref[j] - pref[k-1];
                dp[i][j] = min(dp[i][j], max(dp[i-1][k-1], timeTakenForithPainter));
            }
        }
    }

    if(numberOfPainters > numberOfFences)return dp[numberOfFences-1][numberOfFences-1];
    return dp[numberOfPainters-1][numberOfFences-1];
}


int main(){
    int t;cin>>t;
    while(t--){
        long long int numberOfPainters, numberOfFences, timePerUnit;
        cin>>numberOfPainters>>timePerUnit>>numberOfFences;
        vector<long long int> fenceSize(numberOfFences);
        for(int i=0;i<numberOfFences;i++) cin>>fenceSize[i];
        long long int ans = solvePaintersPartitionProblem(numberOfPainters, timePerUnit, fenceSize);
        cout<<ans<<endl;
    }
}
2

2 5 2 // number of painters, time taken paint a unit length of fence and number of fences

1 10  // fences size

10 1 4

1 8 11 3
50 
11

Java kodu rəssamın bölmə problemi üçün

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    
    static long solvePaintersPartitionProblem(int numberOfPainters, long timePerUnit, int numberOfFences, long fenceSize[]){
        if(numberOfFences == 0)return 0;
        long pref[] = new long[numberOfFences]; // stores the prefix sum for faster sum calculation over the range
        pref[0] = (fenceSize[0] * timePerUnit);
        for(int i=1;i<numberOfFences;i++) {
            pref[i] = (fenceSize[i] * timePerUnit);
            pref[i] = (pref[i] + pref[i-1]);
        }
    
        long dp[][] = new long[numberOfPainters][numberOfFences]; // dp[i][j] = minimum time taken for painting j fences by i painters such that they can paint only in contiguous order
        for(int i=0;i<numberOfPainters;i++){
            for(int j=0;j<numberOfFences;j++)
                dp[i][j] = Long.MAX_VALUE;
        }
    
        // Filling the values for first painter
        for(int i=0;i<numberOfFences;i++)dp[0][i] = pref[i];
    
        // Now solving for painters 2, 3, 4......n
        for(int i=1;i<numberOfPainters;i++){
            for(int j=i;j<numberOfFences;j++){
                for(int k=i;k<=j;k++){
                    long timeTakenForithPainter = pref[j] - pref[k-1];
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[i-1][k-1], timeTakenForithPainter));
                }
            }
        }
        if(numberOfPainters > numberOfFences)return dp[numberOfFences-1][numberOfFences-1];
        return dp[numberOfPainters-1][numberOfFences-1];
    }


    public static void main (String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
  int t = sc.nextInt();
        while(t-- > 0){
            int numberOfPainters = sc.nextInt();
            long timePerUnit = sc.nextLong();
            int numberOfFences = sc.nextInt();
            long fenceSize[] = new long[numberOfFences];
            for(int i=0;i<numberOfFences;i++) fenceSize[i] = sc.nextLong();
            long ans = solvePaintersPartitionProblem(numberOfPainters, timePerUnit, numberOfFences, fenceSize);
            System.out.println(ans);
        }
    }
}
2

2 5 2// number of painters, time taken paint a unit length of fence and number of fences 

1 10 // fences size

10 1 4

1 8 11 3
50 
11

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (N * M ^ 2)

burada N = rəssamların sayı 

M = çəpərlərin sayı, çünki burada rəssamın sərf etdiyi vaxtı tapmaq üçün cəm prefiksindən istifadə etdiyimiz üçün zamanın mürəkkəbliyini azaltdıq.

Birinci döngə rəngkarların sayından, iç içə döngələr isə çəpərlərin sayından keçir. N = M olarsa, zaman mürəkkəbliyi: Rəssamın bölmə problemi üçün O (N ^ 3).

Kosmik Mürəkkəblik: O (N * M)

N = rəssamların sayı 

M = çit sayı, çünki N * M ölçülərindəki 2D DP bir sıra var. Beləliklə, rəssamın bölmə problemi üçün polinom boşluğu mürəkkəbliyi həllinə sahibik.

Crack Sistemi Dizayn Müsahibələri
Translate »