We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Search
  4. Gridland Metro
  5. Discussions

Gridland Metro

Sort by

recency

|

421 Discussions

|

  • 2k23_cscys231046
     + 0 comments

    import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.Map; import java.util.Scanner;

    public class Solution {

    private static Map<Integer, ArrayList<Track>> tracksPerRow = new HashMap<Integer, ArrayList<Track>>();

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int numberOfRows = scanner.nextInt();
    int numberOfColumns = scanner.nextInt();
    int numberOfTracks = scanner.nextInt();

    for (int i = 0; i < numberOfTracks; i++) {
        int row = scanner.nextInt();
        int startColumn = scanner.nextInt();
        int endColumn = scanner.nextInt();
        fillMap(row, startColumn, endColumn);
    }
    scanner.close();

    sortTracksInsideRows_decreasingOrderOfStartColumn();
    long totalCellsWithTracks__exludingOverlaps = getTotalCellsWithTracks_exludingOverlaps();

    long spotsForLampPosts = (long) numberOfRows * numberOfColumns - (long) totalCellsWithTracks__exludingOverlaps;
    System.out.println(spotsForLampPosts);
}

private static void fillMap(int row, int start, int end) {
    Track track = new Track(start, end);

    if (!tracksPerRow.containsKey(row)) {
        ArrayList<Track> tracks = new ArrayList<Track>();
        tracks.add(track);
        tracksPerRow.put(row, tracks);
    } else {
        tracksPerRow.get(row).add(track);
    }
}

private static void sortTracksInsideRows_decreasingOrderOfStartColumn() {
    for (int row : tracksPerRow.keySet()) {
        Collections.sort(tracksPerRow.get(row));
    }
}

private static long getTotalCellsWithTracks_exludingOverlaps() {

    long totalCellsWithTracks__exludingOverlaps = 0;

    for (int row : tracksPerRow.keySet()) {

        int index = 0;

        ArrayList<Track> tracks = tracksPerRow.get(row);

        for (int i = 0; i < tracks.size(); i++) {

            if (index != 0 && tracks.get(index - 1).startColumn <= tracks.get(i).endColumn) {
                while (index != 0 && tracks.get(index - 1).startColumn <= tracks.get(i).endColumn) {

                    int minStart = Math.min(tracks.get(index - 1).startColumn, tracks.get(i).startColumn);
                    int maxEnd = Math.max(tracks.get(index - 1).endColumn, tracks.get(i).endColumn);

                    tracks.get(index - 1).startColumn = minStart;
                    tracks.get(index - 1).endColumn = maxEnd;
                    index--;
                }
            }
            else {
                tracks.set(index, tracks.get(i));
            }
            index++;
        }

        for (int j = 0; j < index; j++) {
            totalCellsWithTracks__exludingOverlaps += (long) tracks.get(j).endColumn
                    - (long) tracks.get(j).startColumn + 1;
        }
    }
    return totalCellsWithTracks__exludingOverlaps;
}

private static class Track implements Comparable<Track> {

    int startColumn;
    int endColumn;

    public Track(int startColumn, int endColumn) {
        this.startColumn = startColumn;
        this.endColumn = endColumn;
    }

    @Override
    public int compareTo(Track arg0) {
        return arg0.startColumn - this.startColumn;
    }
}

    }

  • anatoltbcm
     + 0 comments

    This was the last task on this stupid site. Fortunately, there are many good sites with a similar focus.

  • anatoltbcm
     + 0 comments

    What kind of idiotic condition is this? How can this be?

    k = 3
r   c1  c2
1   1   4
2   2   4
3   1   2
4   2   3

    `Why k=3 if I see 4 tracks??? I have already tried several solutions, but none of them work.

  • CS_2212256_T
     + 0 comments
    import java.util.Scanner;
import java.util.HashMap;

public class GridlandMetro {

     static long gridlandMetro(int n, int m, int k, int[][] track) {
        long total = (long) n * m;
        HashMap<Integer, int[]> d = new HashMap<>();

        for (int i = 0; i < k; i++) {
            int r = track[i][0];
            int c1 = track[i][1];
            int c2 = track[i][2];

            if (!d.containsKey(r)) {
                d.put(r, new int[]{c1, c2});
> >             } else if (c1 > d.get(r)[1]) {
                total -= c2 - c1 + 1;
            } else if (c2 > d.get(r)[1]) {
                d.get(r)[1] = c2;
            }
        }

        long tracks = 0;
        for (int[] range : d.values()) {
            tracks += range[1] - range[0] + 1;
        }

        long lamps = total - tracks;
        return lamps;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read input
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();

        int[][] track = new int[k][3];
        for (int i = 0; i < k; i++) {
            track[i][0] = scanner.nextInt();
            track[i][1] = scanner.nextInt();
            track[i][2] = scanner.nextInt();
        }

        // Calculate and print the result
        long result = gridlandMetro(n, m, k, track);
        System.out.println(result);

        scanner.close();
    }
}

  • mss2518
     + 0 comments
    def gridlandMetro(n, m, k, track):
    bins = defaultdict(list)
    # match each track interval to its row
    for t, s, e in track:
        bins[t].append([s, e])
    # initially we have the whole grid available
    ans = m * n
    for b in bins.values():
        # sort the intervals by start time/position
        b.sort()
        gap = 0
        l_bound, r_bound = b[0]
        for i in range(1, len(b)):
            # the intervals overlap - combine them
            if b[i][0] <= r_bound:
                l_bound = min(l_bound, b[i][0])
                r_bound = max(r_bound, b[i][1])
            # the intervals don't overlap - we need to remove space from the grid
            else:
                gap += r_bound - l_bound + 1
                l_bound, r_bound = b[i]
        # the final interval won't be handled in the loop
        gap += r_bound - l_bound + 1
        ans -= gap
        
    return ans