Mock CCO '18 Contest 2 Problem 5 - Victor's Triangles

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Roger was unable to tilt Victor with rectangles, so now he's going to try with triangles instead!

Roger has given Victor a triangulation of a convex polygon with N sides. The polygon has already been triangulated by Roger, and every triangle has been filled in with some color. The vertices are randomly labeled with distinct positive integers from 1 to N.

Roger challenges Victor to draw as many line segments connecting points on the border of the polygon such that, for every color present on the polygon, that color only appears in exactly one region defined by the polygon and the line segments that Victor has drawn.

Compute the maximum number of segments that Victor can draw respecting the above constraint.


3 \le N \le 10^5

1 \le a_i, b_i, c_i, d_i \le N

The triangulation provided in the input will correspond to a valid triangulation of some polygon with N sides.

For at most 50% of full credit, N \le 5 \cdot 10^3.

Input Specification

The first line will contain a single integer, N.

Each of the next N-2 lines will contain four space-separated integers, a_i, b_i, c_i, and d_i, indicating that the triangle with vertices a_i, b_i, c_i, is colored with color d_i.

Output Specification

Print, on a single line, the maximum number of line segments Victor can draw.

Sample Input

1 2 3 2
4 5 1 1
3 1 4 2

Sample Output


Sample Input

1 4 2 1
2 4 5 2
6 2 5 3
3 6 5 1

Sample Output



There are no comments at the moment.