CCC '21 S5 - Math Homework - Olympiads 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 \le A_i \le 1\,000\,000\,000~ for each $i$ ~i~.

The sequence $A$ ~A~ must also satisfy $M$ ~M~ requirements, with the $i^\text{th}$ ~i^\text{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 \le X_i \le Y_i \le 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 \le i \le 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 \le N \le 2\,000~	$1 \le M \le 2\,000$ ~1 \le M \le 2\,000~	$1 \le Z_i \le 2$ ~1 \le Z_i \le 2~ for each $i$ ~i~
$4$ ~4~ marks	$1 \le N \le 2\,000$ ~1 \le N \le 2\,000~	$1 \le M \le 2\,000$ ~1 \le M \le 2\,000~	$1 \le Z_i \le 16$ ~1 \le Z_i \le 16~ for each $i$ ~i~
$8$ ~8~ marks	$1 \le N \le 150\,000$ ~1 \le N \le 150\,000~	$1 \le M \le 150\,000$ ~1 \le M \le 150\,000~	$1 \le Z_i \le 16$ ~1 \le Z_i \le 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

2 2
1 2 2
2 2 6

Output for Sample Input 1

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

2 2
1 2 2
2 2 5

Output for Sample Input 2

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.