Soluție HackerRank pentru Favorite sequence. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Favorite sequence

Cerinta completa

Johnny, like every mathematician, has his favorite sequence of distinct natural numbers. Let’s call this sequence [Expresie matematică indisponibilă în copia arhivată]. Johnny was very bored, so he wrote down [Expresie matematică indisponibilă în copia arhivată] copies of the sequence [Expresie matematică indisponibilă în copia arhivată] in his big notebook. One day, when Johnny was out, his little sister Mary erased some numbers(possibly zero) from every copy of [Expresie matematică indisponibilă în copia arhivată] and then threw the notebook out onto the street. You just found it. Can you reconstruct the sequence?

In the input there are [Expresie matematică indisponibilă în copia arhivată] sequences of natural numbers representing the [Expresie matematică indisponibilă în copia arhivată] copies of the sequence [Expresie matematică indisponibilă în copia arhivată] after Mary’s prank. In each of them all numbers are distinct. Your task is to construct the shortest sequence [Expresie matematică indisponibilă în copia arhivată] that might have been the original [Expresie matematică indisponibilă în copia arhivată]. If there are many such sequences, return the lexicographically smallest one. It is guaranteed that such a sequence exists.

Note
Sequence [Expresie matematică indisponibilă în copia arhivată] is lexicographically less than sequence [Expresie matematică indisponibilă în copia arhivată] if and only if there exists [Expresie matematică indisponibilă în copia arhivată] such that for all [Expresie matematică indisponibilă în copia arhivată].

Input Format

In the first line, there is one number [Expresie matematică indisponibilă în copia arhivată] denoting the number of copies of [Expresie matematică indisponibilă în copia arhivată].
This is followed by [Expresie matematică indisponibilă în copia arhivată]
and in next line a sequence of length [Expresie matematică indisponibilă în copia arhivată] representing one of sequences after Mary’s prank. All numbers are separated by a single space.

Constraints
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
All values in one sequence are distinct numbers in range [Expresie matematică indisponibilă în copia arhivată].

Output Format

In one line, write the space-separated sequence [Expresie matematică indisponibilă în copia arhivată] – the shortest sequence that might have been the original [Expresie matematică indisponibilă în copia arhivată]. If there are many such sequences, return the lexicographically smallest one.

Sample Input

2
2
1 3
3
2 3 4

Sample Output

 1 2 3 4

Explanation

You have 2 copies of the sequence with some missing numbers: [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată]. There are two candidates for the original sequence [Expresie matematică indisponibilă în copia arhivată], where the first one is lexicographically least.

Limbajul de programare folosit: cpp14

Cod:

//favourite-sequence.cpp
//Favorite sequence
//Weekly Challenges - Week 12
//Author: derekhh

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<functional>
using namespace std;

vector<int> gr[1000001];
int indeg[1000001];
priority_queue<int, vector<int>, greater<int>> pq;

int main()
{
	int n;
	scanf("%d", &n);
	int maxval = -1;
	for (int i = 0; i < n; i++)
	{
		int len;
		scanf("%d", &len);
		int prev;
		for (int j = 0; j < len; j++)
		{
			int tmp;
			scanf("%d", &tmp);
			if (tmp > maxval) maxval = tmp;
			if (j != 0) gr[prev].push_back(tmp), indeg[tmp]++;
			prev = tmp;
		}
	}
	for (int i = 1; i <= maxval; i++)
	{
		if (indeg[i] == 0 && !gr[i].empty())
			pq.push(i);
	}
	while (!pq.empty())
	{
		int next = pq.top();
		printf("%d ", next);
		pq.pop();
		int sz = (int)gr[next].size();
		for (int i = 0; i < sz; i++)
		{
			int node = gr[next][i];
			indeg[node]--;
			if (indeg[node] == 0)
				pq.push(node);
		}
	}
	printf("\n");
	return 0;
}

Scor obtinut: 1.0

Submission ID: 464604453

Link challenge: https://www.hackerrank.com/challenges/favourite-sequence/problem

Favorite sequence