CCC '22 S2 - Good Groups - Olympiads Online Judge

CCC '22 S2 - Good Groups

Points: 5 (partial)

Time limit: 4.0s

Memory limit: 1G

Problem type

Canadian Computing Competition: 2022 Stage 1, Junior #4, Senior #2

A class has been divided into groups of three. This division into groups might violate two types of constraints: some students must work together in the same group, and some students must work in separate groups.

Your job is to determine how many of the constraints are violated.

Input Specification

The first line will contain an integer $X$ $X$ with $X \ge 0$ $X \geq 0$ . The next $X$ $X$ lines will each consist of two different names, separated by a single space. These two students must be in the same group.

The next line will contain an integer $Y$ $Y$ with $Y \ge 0$ $Y \geq 0$ . The next $Y$ $Y$ lines will each consist of two different names, separated by a single space. These two students must not be in the same group.

Among these $X + Y$ $X + Y$ lines representing constraints, each possible pair of students appears at most once.

The next line will contain an integer $G$ $G$ with $G \ge 1$ $G \geq 1$ . The last $G$ $G$ lines will each consist of three different names, separated by single spaces. These three students have been placed in the same group.

Each name will consist of between $1$ $1$ and $10$ $10$ uppercase letters. No two students will have the same name and each name appearing in a constraint will appear in exactly one of the $G$ $G$ groups.

The following table shows how the available $15$ $15$ marks are distributed at the Senior level.

Marks Awarded	Number of Groups	Number of Constraints
$3$ $3$ marks	$G \le 50$ $G \leq 50$	$X \le 50$ $X \leq 50$ and $Y = 0$ $Y = 0$
$5$ $5$ marks	$G \le 50$ $G \leq 50$	$X \le 50$ $X \leq 50$ and $Y \le 50$ $Y \leq 50$
$7$ $7$ marks	$G \le 100\,000$ $G \leq 100 000$	$X \le 100\,000$ $X \leq 100 000$ and $Y \le 100\,000$ $Y \leq 100 000$

Output Specification

Output an integer between $0$ $0$ and $X + Y$ $X + Y$ which is the number of constraints that are violated.

Sample Input 1

Copy

1
ELODIE CHI
0
2
DWAYNE BEN ANJALI
CHI FRANCOIS ELODIE

Output for Sample Input 1

Copy

Explanation of Output for Sample Input 1

There is only one constraint and it is not violated: ELODIE and CHI are in the same group.

Sample Input 2

Copy

3
A B
G L
J K
2
D F
D G
4
A C G
B D F
E H I
J K L

Output for Sample Input 2

Copy

Explanation of Output for Sample Input 2

The first constraint is that A and B must be in the same group. This is violated.

The second constraint is that G and L must be in the same group. This is violated.

The third constraint is that J and K must be in the same group. This is not violated.

The fourth constraint is that D and F must not be in the same group. This is violated.

The fifth constraint is that D and G must not be in the same group. This is not violated.

Of the five constraints, three are violated.

Comments

-1

EasonZhou123 commented 45 days ago

Bro the TLE

-5

teddycitrus commented on Feb. 16, 2024, 6:50 p.m.

anybody know why my code isnt working? I've went over it countless times, it passes both given cases properly: https://dmoj.ca/submission/6197427

This comment is hidden due to too much negative feedback. Show it anyway.

-5

teddycitrus commented on Feb. 16, 2024, 6:50 p.m.

*it passes both sample test cases given within the problem

This comment is hidden due to too much negative feedback. Show it anyway.

5

grdsznt commented on Feb. 18, 2024, 5:40 p.m.

Just because it passes the sample cases does not mean it will pass the problem :)

Also you have TLE so maybe try different data structure.

-2

teddycitrus commented 72 days ago

are vectors/linked lists recommended? i got TLE(>4.000 seconds) for the first test case in batch 4, and all cases before that were at most 0.004 seconds. my answer is currently built on vectors

2
TZ616 commented 71 days ago
The part of your code where you determine if constraints are violated runs in $O(G*(X+Y))$ $O (G * (X + Y))$ time, which is too slow given that $G, X, Y \le 100000$ $G, X, Y \leq 100000$ . Try thinking of a better way to accomplish this without looping through all the constraints for each group.

Also, try the following case:

Copy
0 1 A D 2 AB AD A B C D

The answer should be 0.

-1

teddycitrus commented 69 days ago

i think i genuinely ended up opting for the worst approach lol thanks for the tip tho, along w the new test case