मैं Hackerrank[1] पर इस समस्या का समाधान कर रहा हूँ: https://www.hackerrank.com/challenges /ग्रिडलैंड-मेट्रो

ग्रिडलैंड शहर को n by m मैट्रिक्स के रूप में दर्शाया जाता है जहां पंक्तियों को 1 से n तक क्रमांकित किया जाता है और कॉलम 1 से m तक गिने जाते हैं।

ग्रिडलैंड में रेल पटरियों का एक नेटवर्क है जो हमेशा एक पंक्ति के साथ सीधी क्षैतिज रेखाओं में चलता है। दूसरे शब्दों में, ट्रेन ट्रैक के प्रारंभ और अंत बिंदु (r,c1) और (r,c2) हैं, जहां r प्रतिनिधित्व करता है पंक्ति संख्या, c1 प्रारंभिक स्तंभ का प्रतिनिधित्व करती है, और c2 ट्रेन ट्रैक के अंतिम स्तंभ का प्रतिनिधित्व करती है।

ग्रिडलैंड के मेयर उन स्थानों की संख्या निर्धारित करने के लिए शहर का सर्वेक्षण कर रहे हैं जहां लैम्पपोस्ट लगाए जा सकते हैं। लैम्पपोस्ट को किसी भी सेल में रखा जा सकता है, जिस पर ट्रेन की पटरी नहीं है।

ग्रिडलैंड और उसके k रेल पटरियों के मानचित्र को देखते हुए, उन कक्षों की संख्या ढूँढें और प्रिंट करें जहाँ मेयर लैम्पपोस्ट लगा सकते हैं।

नोट: एक ट्रेन ट्रैक एक ही पंक्ति में अन्य ट्रेन ट्रैक को ओवरलैप कर सकता है (या नहीं)।

इनपुट प्रारूप

पहली पंक्ति में तीन स्थान से अलग किए गए पूर्णांक हैं जो n (पंक्तियों की संख्या), m (स्तंभों की संख्या), और k (ट्रेन की पटरियों की संख्या)। k की प्रत्येक पंक्ति i बाद की पंक्तियों में तीन स्थान से अलग किए गए पूर्णांक हैं जो के संबंधित मानों का वर्णन करते हैं r,c1, और c2 जो रेल ट्रैक को परिभाषित करते हैं।

उन कक्षों की संख्या को दर्शाने वाला एकल पूर्णांक प्रिंट करें जहां महापौर लैम्पपोस्ट स्थापित कर सकते हैं।

यहाँ मेरा समाधान है:

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

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System. in );
        int n = input.nextInt();
        int m = input.nextInt();
        int k = input.nextInt();
        int[][] arr = new int[n][m];
        int occupied = 0;
        for (int i = 0; i < n; i++) {
            Arrays.fill(arr[i], 0);
        }
        for (int i = 0; i < k; i++) {
            int r = input.nextInt() - 1;
            int c1 = input.nextInt() - 1;
            int c2 = input.nextInt() - 1;
            for (int j = c1; j <= c2; j++) {
                arr[r][j] = -1;
            }
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] != -1) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

क्या कोई मेरे कोड में समस्या बता सकता है? (यह सबमिशन पर सिर्फ 4 टेस्ट केस पास कर रहा है)

0
Aastik 18 फरवरी 2017, 12:49
 – 
Yash Mehta
18 फरवरी 2017, 14:00

3 जवाब

प्रश्न में बाधा 1<=n,m<=10^9 हैं।

आप इतने आकार के द्वि-आयामी सरणी की घोषणा नहीं कर सकते क्योंकि इसके लिए बड़ी मात्रा में ढेर स्थान की आवश्यकता होगी, उदाहरण के लिए यदि n,m दोनों 10^9 हैं, तो गिरफ्तारी का आकार 10^18 * 4 /( 1024 * 1024 * 1024) Gb होगा।

इस बड़े सरणी का उपयोग किए बिना इस प्रश्न को हल किया जा सकता है। अगर आपको सही दृष्टिकोण के साथ किसी मदद की ज़रूरत है तो मैं मदद कर सकता हूं, लेकिन पहले स्वयं प्रयास करें।

0
Amit Kumar 18 फरवरी 2017, 13:23

मैंने हैश मैप का उपयोग करके यह समाधान लिखा है, मैं एक नक्शा बनाए रख रहा हूं इंटीजर पंक्ति संख्या है और हैशसेट विशेष पंक्ति के लिए देखे गए कॉलम का सेट है। यह नक्शा यह जांचने के लिए रखा जाता है कि कहीं कोई ओवरलैपिंग ट्रैक तो नहीं है। कोड छोटे परीक्षण मामलों पर सही उत्तर देता है। लेकिन, अधिकांश परीक्षण मामलों में, यह समय समाप्त होने के कारण विफल हो जाता है। इस कोड को अनुकूलित करने में किसी भी मदद की अत्यधिक सराहना की जाती है।

    import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();
        long m = sc.nextInt();
        int k = sc.nextInt();        
        HashMap<Integer,HashSet> map = new HashMap<Integer,HashSet>(); 
        long count = n*m;
        for (int i =0;i<k;i++)
            {
            HashSet<Integer> set = new HashSet<Integer>();    
            int row = sc.nextInt();
            int c1 = sc.nextInt();
            int c2 = sc.nextInt();
            //System.out.println(row+" "+ c1+" "+c2);
            if (map.containsKey(row))
                {
                set = map.get(row);
                for (int j = c1;j<=c2;j++)
                {
                    if(set.add(j)) count--;
                }
                //if (set.add(c2)) count--;
                map.put(row,set);
            }
                else
                {
                    for (int p = c1;p<=c2;p++)
                    {
                        if (set.add(p)) count --;
                    }
                    //if (set.add(c2)) count--;

                    map.put(row,set);
                }
        }
        System.out.println(count);

    }
    }
0
Machine_leaning_9 27 अप्रैल 2017, 03:27
मैं अपने सुझावों के आधार पर आपके एल्गोरिदम को बदलने की सलाह देता हूं। आपको कामयाबी मिले!
 – 
johnnieb
3 मई 2017, 20:40

मैं यहाँ समाधान प्रदान नहीं करने जा रहा हूँ क्योंकि मुझे नहीं लगता कि यह HackerRank की भावना में है। हालाँकि, मैंने कुछ संकेत दिए हैं और आपके कोड की समस्याओं की पहचान की है।

Scanner input = new Scanner(System.in);
int n = input.nextInt();//ERROR: n ranges from 1 to 10E9, read in as a String
int m = input.nextInt();//ERROR: m ranges from 1 to 10E9, read in as String
int k = input.nextInt();
int[][] arr = new int[n][m];/*ERROR: The range of an int is 2E31-1 and large 
                                    integers will cause stack overflow anyway. 
                                    You'll need to consider a data structure 
                                    that's compatible w/ strings. Hint, consider 
                                    a hash table. */
int occupied = 0;
for (int i = 0; i < n; i++) {
    Arrays.fill(arr[i], 0);
}
for (int i = 0; i < k; i++) {
    int r = input.nextInt() - 1;//ERROR: r ranges from 1 to 10E9, read in as a String
    int c1 = input.nextInt() - 1;//ERROR: c1 ranges from 1 to 10E9, read in as a String
    int c2 = input.nextInt() - 1;//ERROR: c2 ranges from 1 to 10E9, read in as a String
    for (int j = c1; j <= c2; j++) {
        arr[r][j] = -1;
    }
}
/* NOTE: A train track may (or may not) overlap other train tracks within the 
     same row. Hence, your algorithm will need to account for track overlaps 
     and tracks that are in between of each other. For example, if a track 
     overlaps with another track in the same the row, the tracks should be 
     merged into a single track. If a smaller track is contained in a bigger 
     track, the smaller track should be ignored.*/
int count = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (arr[i][j] != -1) {
            count++;
        }
    }
}

System.out.println(count);
0
johnnieb 3 मई 2017, 21:16