equality and coerciongroupingcopying listsP0205

Identical parcels and parcels with the same contents

n parcels arrive at a warehouse one after another.
The parcels are numbered from 1 in the order they arrive. Each parcel carries one label and k item numbers written in order. Two parcels are "identical" when their labels are the same, they have the same number of items, and the item numbers are the same at every position. Two parcels "have the same contents" when their labels are the same and, ignoring order, they contain the same item numbers the same number of times.
In other words, listing both sides' item numbers from smallest makes them identical. Two identical parcels also have the same contents.
Parcels with no items are identical to each other when their labels are the same. The first line gives n, and the next n lines give parcels 1, 2, … in order as "label k number1 … numberk". For each parcel print two numbers a and b on one line, separated by a single space. a is the number of the earliest-arriving parcel identical to it, and b is the number of the earliest-arriving parcel with the same contents.
The parcel itself counts. On the last line print two numbers separated by a single space. The first is how many kinds of parcels there are when identical parcels count as one kind, and the second is how many kinds there are when parcels with the same contents count as one kind.

Input: 1 ≤ n ≤ 5,000, 0 ≤ k ≤ 10, 0 ≤ item number ≤ 10⁹.
A label is 1 to 10 lowercase English letters.
Output: n+1 lines: "a b" for each parcel, then "identical_kinds contents_kinds" on the last line

Example 1 · stdin

6
box 3 1 23 5
box 3 12 3 5
box 3 23 1 5
box 3 1 23 5
bag 0
box 3 5 1 23

stdout

main.py Programming language Runtime version

Input (stdin)

When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).

$ Ready

Open this on a computer to write and run code. On mobile you can read the problem and the solutions.

In other languagesShow solutions by language · 8 languages

The heart of it is using 'lists with equal values' as dictionary keys, and list == and key comparison differ between languages.
In Python [1, 2] == [1, 2] is true, but a mutable list cannot be a key, so make a tuple as in (label, tuple(codes)).
In C++, == and < on std::vector and std::string compare by value, so std::map<std::pair<std::string, std::vector<int>>, int> works as is.
Java's List.equals compares element by element with equals, so record Key(String label, List<Integer> codes) works as a key (the record generates equals and hashCode).
JavaScript and TypeScript Map and ===, C#'s List<int>, and Craykon's list == only ask whether it is the same list (reference), so build a string key that is equal when the values are, label + " " + codes.join(",") (Craykon codes.Join(",")).
C has no dictionary, so gather equal parcels with qsort, compare neighbours, and compare labels with strcmp.
Build the contents key from a sorted copy.
sorted() in Python, OrderBy in C#, new ArrayList<>(codes) in Java, [...codes] in JS, std::vector<int> sorted = codes; in C++ and codes.GetRange(0, codes.Count) in Craykon are copies.
Seven traps: ① In JS, using an array [label, codes] as a Map key makes every parcel different, because each line makes a new array.
② C#'s (string, List<int>) tuple key gives the same result: the tuple compares by value, but the List<int> inside compares by reference.
③ Java's record Key(String label, int[] codes) compiles, but an array member compares only whether it is the same array (not Arrays.equals).
④ Joining without a separator as in label + "".join(...) turns both [1, 23] and [12, 3] into 123, so different parcels become equal.
⑤ JS codes.sort() sorts codes itself, not a copy, and returns the same array, so the identical key is built from sorted numbers too.
⑥ Craykon's sorted = codes; also just puts a second name on the same list, causing the same problem.
⑦ In C, a->label == b->label and < compare the addresses of the two arrays, so labels are always different even when they are equal.

Pythonmain.py · 18 lines

import sys lines = sys.stdin.read().split("\n")n = int(lines[0])first_same = {}  # (이름표, 번호 튜플) → 가장 먼저 들어온 번호first_bag = {}   # (이름표, 정렬한 번호 튜플) → 가장 먼저 들어온 번호out = []for i in range(1, n + 1):    label, k, *rest = lines[i].split()    codes = [int(x) for x in rest]    # 목록(list)은 바뀔 수 있어서 열쇠가 못 된다. 튜플은 값으로 같고 해시도 값으로 정해진다    same = (label, tuple(codes))    bag = (label, tuple(sorted(codes)))  # sorted는 새 목록을 만든다: codes는 그대로    a = first_same.setdefault(same, i)    b = first_bag.setdefault(bag, i)    out.append(f"{a} {b}")out.append(f"{len(first_same)} {len(first_bag)}")print("\n".join(out))

JavaScriptmain.js · 20 lines

const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);// Map은 열쇠를 SameValueZero로 비교한다: 배열은 같은 배열(참조)일 때만 같다.// 그래서 값이 같으면 같아지는 문자열 열쇠로 바꾼다. 사이에 쉼표·빈칸을 넣어 경계를 지킨다const firstSame = new Map();const firstBag = new Map();const out = [];for (let i = 1; i <= n; i++) {  const [label, , ...rest] = lines[i].trim().split(" ");  const codes = rest.map(Number);  const sameKey = `${label} ${codes.join(",")}`;  // sort는 제자리에서 바꾸고 같은 배열을 돌려준다: 복사본([...codes])을 정렬한다.  // 비교 함수가 없으면 문자열로 정렬하니 (a, b) => a - b를 준다  const bagKey = `${label} ${[...codes].sort((a, b) => a - b).join(",")}`;  if (!firstSame.has(sameKey)) firstSame.set(sameKey, i);  if (!firstBag.has(bagKey)) firstBag.set(bagKey, i);  out.push(`${firstSame.get(sameKey)} ${firstBag.get(bagKey)}`);}out.push(`${firstSame.size} ${firstBag.size}`);console.log(out.join("\n"));

TypeScriptmain.ts · 25 lines

import { readFileSync } from "node:fs"; const lines = readFileSync(0, "utf8").split("\n");const n = Number(lines[0]); // 배열은 ===로도 Map 열쇠로도 같은 배열(참조)일 때만 같다: 값으로 같아지는 문자열 열쇠를 만든다function keyOf(label: string, codes: readonly number[]): string {  return `${label} ${codes.join(",")}`; // 사이에 빈칸·쉼표를 넣어 [1, 23]과 [12, 3]을 가른다} const firstSame = new Map<string, number>();const firstBag = new Map<string, number>();const out: string[] = [];for (let i = 1; i <= n; i++) {  const [label, , ...rest] = lines[i].trim().split(" ");  const codes: readonly number[] = rest.map(Number);  const sorted = [...codes].sort((a, b) => a - b); // 복사본을 정렬한다(readonly라 codes.sort는 타입 오류)  const sameKey = keyOf(label, codes);  const bagKey = keyOf(label, sorted);  if (!firstSame.has(sameKey)) firstSame.set(sameKey, i);  if (!firstBag.has(bagKey)) firstBag.set(bagKey, i);  out.push(`${firstSame.get(sameKey)} ${firstBag.get(bagKey)}`);}out.push(`${firstSame.size} ${firstBag.size}`);console.log(out.join("\n"));

JavaMain.java · 36 lines

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map; public class Main {    // record는 equals·hashCode를 멤버마다 equals로 만들어 준다.    // List.equals는 길이와 자리마다의 값을 비교한다(배열 int[]라면 같은 배열인지만 본다)    record Key(String label, List<Integer> codes) {}     public static void main(String[] args) throws IOException {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        int n = Integer.parseInt(br.readLine().trim());        Map<Key, Integer> firstSame = new HashMap<>();        Map<Key, Integer> firstBag = new HashMap<>();        StringBuilder out = new StringBuilder();        for (int i = 1; i <= n; i++) {            String[] p = br.readLine().trim().split(" ");            List<Integer> codes = new ArrayList<>();            for (int j = 2; j < p.length; j++) codes.add(Integer.parseInt(p[j]));            List<Integer> sorted = new ArrayList<>(codes); // 복사본을 정렬한다            sorted.sort(null);            // putIfAbsent: 열쇠가 없으면 i를 넣고 null을, 있으면 먼저 넣은 값을 돌려준다            Integer a = firstSame.putIfAbsent(new Key(p[0], codes), i);            Integer b = firstBag.putIfAbsent(new Key(p[0], sorted), i);            if (a == null) a = i;            if (b == null) b = i;            out.append(a).append(' ').append(b).append('\n');        }        out.append(firstSame.size()).append(' ').append(firstBag.size()).append('\n');        System.out.print(out);    }}

C#Main.cs · 32 lines

using System;using System.Collections.Generic;using System.Linq;using System.Text; class Program{    static void Main()    {        var input = Console.In;        int n = int.Parse(input.ReadLine()!.Trim());        // List<int>는 Equals가 참조 비교라 열쇠로 쓰면 값이 같아도 다른 열쇠가 된다.        // 값으로 같아지는 문자열 열쇠를 만든다(사이에 빈칸·쉼표를 넣어 경계를 지킨다)        var firstSame = new Dictionary<string, int>();        var firstBag = new Dictionary<string, int>();        var sb = new StringBuilder();        for (int i = 1; i <= n; i++)        {            string[] p = input.ReadLine()!.Trim().Split(' ');            string label = p[0];            int[] codes = p.Skip(2).Select(int.Parse).ToArray();            int[] sorted = codes.OrderBy(x => x).ToArray();  // 새 배열: codes는 그대로            string sameKey = label + " " + string.Join(",", codes);            string bagKey = label + " " + string.Join(",", sorted);            if (!firstSame.TryGetValue(sameKey, out int a)) firstSame[sameKey] = a = i;            if (!firstBag.TryGetValue(bagKey, out int b)) firstBag[bagKey] = b = i;            sb.Append(a).Append(' ').Append(b).Append('\n');        }        sb.Append(firstSame.Count).Append(' ').Append(firstBag.Count).Append('\n');        Console.Write(sb);    }}

C++main.cpp · 33 lines

#include <algorithm>#include <iostream>#include <map>#include <string>#include <utility>#include <vector> int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    int n;    std::cin >> n;    // std::string과 std::vector는 ==와 <가 값(길이와 자리마다의 원소)으로 비교한다.    // 그래서 pair<string, vector<int>>를 그대로 map의 열쇠로 쓸 수 있다    using Key = std::pair<std::string, std::vector<int>>;    std::map<Key, int> firstSame, firstBag;    std::string out;    for (int i = 1; i <= n; i++) {        std::string label;        int k;        std::cin >> label >> k;        std::vector<int> codes(k);        for (int &x : codes) std::cin >> x;        std::vector<int> sorted = codes;  // vector 대입은 복사: codes는 그대로        std::sort(sorted.begin(), sorted.end());        // emplace는 열쇠가 이미 있으면 넣지 않고, 있던 칸을 가리키는 반복자를 돌려준다        int a = firstSame.emplace(Key{label, codes}, i).first->second;        int b = firstBag.emplace(Key{label, sorted}, i).first->second;        out += std::to_string(a) + ' ' + std::to_string(b) + '\n';    }    out += std::to_string(firstSame.size()) + ' ' + std::to_string(firstBag.size()) + '\n';    std::cout << out;}

Cmain.c · 73 lines

#include <stdio.h>#include <stdlib.h>#include <string.h> #define MAXN 5000 typedef struct {    char label[11];    int k;    int codes[10];  /* 들어온 차례 그대로 */    int sorted[10]; /* 작은 것부터 늘어놓은 것 */} Parcel; static Parcel p[MAXN];static int order[MAXN]; static int cmp_int(const void *a, const void *b) {    int x = *(const int *)a, y = *(const int *)b;    return (x > y) - (x < y);} /* 두 꾸러미를 비교한다. 문자열은 ==로 비교하면 주소를 비교하니 strcmp로,   배열은 길이를 먼저 보고 칸마다 비교한다 */static int compare(const Parcel *a, const Parcel *b, int use_sorted) {    int c = strcmp(a->label, b->label);    if (c != 0) return c;    if (a->k != b->k) return a->k - b->k;    const int *x = use_sorted ? a->sorted : a->codes;    const int *y = use_sorted ? b->sorted : b->codes;    for (int j = 0; j < a->k; j++)        if (x[j] != y[j]) return x[j] < y[j] ? -1 : 1;    return 0;} static int use_sorted_now;static int cmp_order(const void *a, const void *b) {    int i = *(const int *)a, j = *(const int *)b;    int c = compare(&p[i], &p[j], use_sorted_now);    return c != 0 ? c : i - j; /* 같은 것끼리는 먼저 들어온 것이 앞에 */} /* 같은 것끼리 모이도록 번호를 정렬하고, 무리마다 맨 앞(가장 먼저 들어온 것)의 번호를 적는다 */static int group(int n, int use_sorted, int *first) {    for (int i = 0; i < n; i++) order[i] = i;    use_sorted_now = use_sorted;    qsort(order, (size_t)n, sizeof order[0], cmp_order);    int kinds = 0, head = 0;    for (int t = 0; t < n; t++) {        if (t == 0 || compare(&p[order[t]], &p[order[t - 1]], use_sorted) != 0) {            head = order[t];            kinds++;        }        first[order[t]] = head;    }    return kinds;} int main(void) {    static int first_same[MAXN], first_bag[MAXN];    int n;    scanf("%d", &n);    for (int i = 0; i < n; i++) {        scanf("%10s %d", p[i].label, &p[i].k);        for (int j = 0; j < p[i].k; j++) scanf("%d", &p[i].codes[j]);        memcpy(p[i].sorted, p[i].codes, sizeof p[i].codes);        qsort(p[i].sorted, (size_t)p[i].k, sizeof(int), cmp_int);    }    int same_kinds = group(n, 0, first_same);    int bag_kinds = group(n, 1, first_bag);    for (int i = 0; i < n; i++) printf("%d %d\n", first_same[i] + 1, first_bag[i] + 1);    printf("%d %d\n", same_kinds, bag_kinds);    return 0;}

Craykonmain.cray · 33 lines

n = Console.ReadLine().ToNumber();// 목록끼리 ==는 같은 목록인지만 묻고, 사전의 열쇠는 문자열이나 수만 된다.// 그래서 값이 같으면 같아지는 문자열 열쇠를 만든다(사이에 빈칸·쉼표를 넣는다)firstSame = Dict();firstBag = Dict();kinds = 0;bagKinds = 0;for (i = 1; i <= n; i++){    p = Console.ReadLine().Trim().Split(" ");    label = p[0];    codes = [];    for (j = 2; j < p.Count; j++)    {        codes.Add(p[j].ToNumber());    }    sorted = codes.GetRange(0, codes.Count); // 새 목록: 정렬해도 codes는 그대로    sorted.Sort();    sameKey = label + " " + codes.Join(",");    bagKey = label + " " + sorted.Join(",");    if (!firstSame.Contains(sameKey))    {        firstSame[sameKey] = i;        kinds = kinds + 1;    }    if (!firstBag.Contains(bagKey))    {        firstBag[bagKey] = i;        bagKinds = bagKinds + 1;    }    Console.WriteLine(firstSame[sameKey] + " " + firstBag[bagKey]);}Console.WriteLine(kinds + " " + bagKinds);