Sort the Fabrics solution kickstart

Problem

A fabric is represented by three properties:

  • Color (CC), a string consisting of lowercase letters of the English alphabet, representing the color of the fabric.
  • Durability (DD), an integer representing the durability of the fabric.
  • Unique identifier (UU), an integer representing the ID of the fabric.

Solution – CLICK HERE

Ada and Charles work at the Kick Start fabric factory. Each day they receive NN fabrics, and one of them has to sort it. They sort it using the following criteria:

  • Ada sorts in lexicographically increasing order by color (CC).
  • Charles sorts in ascending order by durability (DD).
  • They break ties by sorting in ascending order by the unique identifier (UU).

Sort the Fabrics solution kickstart

Given NN fabrics, count the number of fabrics which end up in the same position regardless of whether Ada or Charles sort them.

Sort the Fabrics solution kickstart

The first line of the input gives the number of test cases, TTTT test cases follow.
Each test case begins with one line consisting of an integer NN denoting the number of fabrics. Then NN lines follow, each line with a string CiCi, an integer DiDi, and an integer UiUi: the color, the durability and the unique identifier of the ii-th fabric respectively.

Output

For each test case, output one line containing Case #xxyy, where xx is the test case number (starting from 1) and yy is the number of fabrics which end up in the same position regardless of whether a worker sorts them by color or by durability.

Sort the Fabrics solution kickstart

Time limit: 20 seconds.
Memory limit: 1 GB.
1T1001≤T≤100.
11≤ length of string CiCi 10≤10.
String CiCi consists of only lowercase letters of the English alphabet.
No two fabrics have same UiUi.

Test Set 1

1N21≤N≤2.
1Di21≤Di≤2.
1Ui21≤Ui≤2.

Test Set 2

1N1031≤N≤103.
1Di1021≤Di≤102.
1Ui1031≤Ui≤103.

Sort the Fabrics solution kickstart

Note: there are additional samples that are not run on submissions down below.

Sample Input
content_copy
3
2
blue 2 1
yellow 1 2
2
blue 2 1
brown 2 2
1
red 1 1
Sample Output
content_copy
Case #1: 0
Case #2: 2
Case #3: 1

In Sample Case #1, when sorted by color, the order of fabrics represented by the unique identifier is 11 and 22. When sorted by durability, the order of fabrics is 22 and 11. Therefore, 00 fabrics have the same position when sorted by color or durability.

In Sample Case #2, when sorted by color, the order of fabrics represented by the unique identifier is 11 and 22. When sorted by durability, the order of fabrics is also 11 and 22. Therefore, 22 fabrics have the same position. Notice that both fabrics have the same durability, so when Charles sorts them he decides that fabric 11 comes first because it has a smaller identifier.

In Sample Case #3, since there is only 11 fabric, the position remains the same whether the fabrics are sorted by color or durability.

 

Additional Sample – Test Set 2

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.

Sample Input
content_copy
1
5
blue 1 2
green 1 4
orange 2 5
red 3 6
yellow 3 7
Sample Output
content_copy
Case #1: 5

In Sample Case #1, the order is the same for both when sorted by color or durability. So the answer is 55.

Leave a Comment

Your email address will not be published.