CCC '21 S5 - Math Homework - DMOJ: Modern Online Judge

CCC '21 S5 - Math Homework

Points: 15 (partial)

Time limit: 3.0s

Memory limit: 1G

Author:

Problem types

Canadian Computing Competition: 2021 Stage 1, Senior #5

Your math teacher has given you an assignment involving coming up with a sequence of $N$ $N$ integers $A_1, \dots, A_N$ $A_{1}, \dots, A_{N}$ , such that $1 \le A_i \le 1\,000\,000\,000$ $1 \leq A_{i} \leq 1 000 000 000$ for each $i$ $i$ .

The sequence $A$ $A$ must also satisfy $M$ $M$ requirements, with the $i^\text{th}$ $i^{th}$ one stating that the GCD (Greatest Common Divisor) of the contiguous subsequence $A_{X_i}, \dots, A_{Y_i}$ $A_{X_{i}}, \dots, A_{Y_{i}}$ $(1 \le X_i \le Y_i \le N)$ $(1 \leq X_{i} \leq Y_{i} \leq N)$ must be equal to $Z_i$ $Z_{i}$ . Note that the GCD of a sequence of integers is the largest integer $d$ $d$ such that all the numbers in the sequence are divisible by $d$ $d$ .

Find any valid sequence $A$ $A$ consistent with all of these requirements, or determine that no such sequence exists.

Input Specification

The first line contains two space-separated integers, $N$ $N$ and $M$ $M$ . The next $M$ $M$ lines each contain three space-separated integers, $X_i$ $X_{i}$ , $Y_i$ $Y_{i}$ , and $Z_i$ $Z_{i}$ $(1 \le i \le M)$ $(1 \leq i \leq M)$ .

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

Subtask	$N$ $N$	$M$ $M$	$Z_i$ $Z_{i}$
$3$ $3$ marks	$1 \le N \le 2\,000$ $1 \leq N \leq 2 000$	$1 \le M \le 2\,000$ $1 \leq M \leq 2 000$	$1 \le Z_i \le 2$ $1 \leq Z_{i} \leq 2$ for each $i$ $i$
$4$ $4$ marks	$1 \le N \le 2\,000$ $1 \leq N \leq 2 000$	$1 \le M \le 2\,000$ $1 \leq M \leq 2 000$	$1 \le Z_i \le 16$ $1 \leq Z_{i} \leq 16$ for each $i$ $i$
$8$ $8$ marks	$1 \le N \le 150\,000$ $1 \leq N \leq 150 000$	$1 \le M \le 150\,000$ $1 \leq M \leq 150 000$	$1 \le Z_i \le 16$ $1 \leq Z_{i} \leq 16$ for each $i$ $i$

Note: an additional test case worth 1 point was added to prevent unintended solutions from passing.

Output Specification

If no such sequence exists, output the string Impossible on one line. Otherwise, on one line, output $N$ $N$ space-separated integers, forming the sequence $A_1, \dots, A_N$ $A_{1}, \dots, A_{N}$ . If there are multiple possible valid sequences, any valid sequence will be accepted.

Sample Input 1

Copy

2 2
1 2 2
2 2 6

Output for Sample Input 1

Copy

4 6

Explanation of Output for Sample Input 1

If $A_1 = 4$ $A_{1} = 4$ and $A_2 = 6$ $A_{2} = 6$ , the GCD of $[A_1, A_2]$ $[A_{1}, A_{2}]$ is $2$ $2$ and the GCD of $[A_2]$ $[A_{2}]$ is $6$ $6$ , as required. Please note that other outputs would also be accepted.

Sample Input 2

Copy

2 2
1 2 2
2 2 5

Output for Sample Input 2

Copy

Impossible

Explanation of Output for Sample Input 2

There exists no sequence $[A_1, A_2]$ $[A_{1}, A_{2}]$ such that the GCD of $[A_1, A_2]$ $[A_{1}, A_{2}]$ is $2$ $2$ and the GCD of $[A_2]$ $[A_{2}]$ is $5$ $5$ .

Comments

3

maxcruickshanks commented on Jan. 1, 2024, 7:16 p.m.

Since the original data were weak, an additional test case worth 1 point was added.

0

31501357 commented on Oct. 29, 2024, 3:42 a.m.

My solution was much faster on the additional test case.