Back To School '17: New English

Points: 12 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

Problem type

Summer is an employee of a certain company which tries to create viral trends. The company's latest scheme is to create a single word which will then be adopted by the "youth" and become a meme. Summer is put in charge of this project, and she decides the word should have exactly $N$ ~N~ lowercase letters.

Excited by the possibility of a new internet sensation, $M$ ~M~ of Summer's friends each make one suggestion as to what the word should contain. Specifically, each friend wants a lowercase letter $c$ ~c~ to appear exactly $x$ ~x~ times within the first $i$ ~i~ letters of the word (inclusive).

Since Summer doesn't want to disappoint any of her friends, she asks you to help her create the next big thing!

Input Specification

The first line will contain two space separated integers $N$ ~N~ and $M$ ~M~, which represent the length of the word Summer is to make, and the number of friends she has respectively.

The next $M$ ~M~ lines will each contain a suggestion by one of her friends in the form c x i.

Constraints

For all subtasks:

$1 \le i \le N$ ~1 \le i \le N~

$0 \le x \le N$ ~0 \le x \le N~

$c$ ~c~ will always be a lowercase letter of the alphabet.

Subtask 1 [30%]

$1 \le N, M \le 10^3$ ~1 \le N, M \le 10^3~

Subtask 2 [70%]

$1 \le N, M \le 10^5$ ~1 \le N, M \le 10^5~

Output Specification

The output should be one line, consisting of a string which satisfies all $M$ ~M~ suggestions of her friends. If there are multiple solutions, output any of them. If there are no solutions, output -1.

Sample Input 1

Sample Output 1

aacbbbc

Explanation of Sample Output 1

The word must have its first two letters be a to fulfill the first suggestion. The second suggestion is fulfilled by having c appear at indices $3$ ~3~ and $7$ ~7~. The third suggestion is fulfilled, with b appearing at the $4^{th}$ ~4^{th}~, $5^{th}$ ~5^{th}~ and $6^{th}$ ~6^{th}~ indices. Finally, the last suggestion is fulfilled, as the letter c only appears once in the first $5$ ~5~ indices.

Other possible solutions include aacbbcb, aabcbbc, etc.

Sample Input 2

4 2
x 2 3
y 2 3

Sample Output 2

-1

Explanation of Sample Output 2

It is impossible for characters x and y to each appear twice in the first three characters.

Comments

1

maxhflow commented on Sept. 10, 2017, 4:35 a.m.

I think the checker might be broken for this question. It marks 'aabcd' as a wrong answer for input 4. However, I think that it is impossible for my algorithm to output something other than "-1" which is incorrect, because I have written my own validator to check my answers. Also, I managed to write a hack that outputs the input for test 4 to check, and it looks to me like my output is correct.

If the checker is not broken, I will be interested to see what wrong idea I had. Because I read the problem statement many times now, haha!

3

atarw commented on Sept. 10, 2017, 4:44 a.m. ← edit 3 →

the case you're failing on is an edge case, unfortunately i can't give more details since the contest is ongoing and it's unfair to others. however, the case and its answer are both valid and correct (i checked manually).

0

maxhflow commented on Sept. 10, 2017, 5:38 a.m.

I found my misunderstanding :(