CodeChef : April Challenge 2017 – Dish Of Life

By | April 9, 2017
Dish Of Life

Source: CodeChef

Chef wants to serve mankind by making people immortal by preparing a dish, a dish of life – a dish with the best taste in the universe, one with the smell and splash of fresh water flowing down the springs of the mountain, one with the smell of the best lily flowers of the garden, one that has contained the very essence of life in a real sense.

This dish will contain K ingredients that are found only in remote islands amid mountains. For sake of convenience, we enumerate the ingredients by the integers from 1 to K, both inclusive. There are N islands and each of them offers some ingredients. Chef being a little child did not know how to collect the ingredients for the recipe. He went to all the islands and bought all the ingredients offered in each island. Could he possibly have saved some time by skipping some island? If it was not possible for Chef to collect the required ingredients (i.e. all the K ingredients), output “sad”. If it was possible for him to skip some islands, output “some”, otherwise output “all”.

Input

First line of the input contains an integer T denoting number of test cases. The description of T test cases follow.

The first line of each test case contains two space separated integers N, K.

The i-th of the next lines will contain first an integer Pi, denoting the number of ingredients grown in the i-th island, followed by Pi distinct integers in the range [1, K]. All the integers are space separated.

Output

For each test case, output a single line containing one of the strings “sad”, “all” or “some” (without quotes) according to the situation.

Constraints

  • 1 ≤ T ≤ 10
  • 1 ≤ N, K ≤ 105
  • 1 ≤ PiK
  • Sum of Pi over all test cases ≤ 106

Subtasks

Subtask #1 (30 points)

  • 1 ≤ N, K ≤ 50

Subtask #2 (30 points)

  • 1 ≤ K ≤ 50

Subtask #3 (40 points)

  • original constraints

Example

Input
3
3 4
3 1 2 3
2 1 3
2 1 2
2 3
3 1 2 3
2 1 3
2 3
2 1 2
2 1 3

Output
sad
some
all

Explanation

Example 1. The ingredient 4 is not available in any island, so Chef can’t make the dish of life. Hence, the answer is “sad”.

Example 2. Chef can just go to the first island and collect all the three ingredients required. He does not need to visit the second island. So, the answer is “some”.

Example 3. Chef has to visit both the islands in order to obtain all the three ingredients. So, the answer is “all”.

Solution

Able to solve it. Got 60 points. TLE in sub task #3.
I have used ArrayList to save items. This is the reason of TLE i guess.
Will try to optimize code.

package aprilChallenge2017;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class DishOfLife {

	public static boolean findAll(int k, TreeSet set) {
		boolean flag = true;
		for (int i = 1; i <= k; i++) {
			if (!set.contains(i)) {
				flag = false;
				break;
			}
		}
		return flag;
	}
	public static ArrayList findAllAL(ArrayList myList, ArrayList list) {
		for (int i = 0; i < list.size(); i++) {
			if (myList.contains(list.get(i))) {
				myList.remove(list.get(i));
			}
		}
		return myList;
	}
	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int t = scan.nextInt();

		for (int i = 0; i < t; i++) {
			int n = scan.nextInt();
			int k = scan.nextInt();
			int flagk = 0;

			TreeSet set = new TreeSet<>();

			List listOfN = new ArrayList<>();

			for (int j = 0; j < n; j++) {
				int p = scan.nextInt();
				List listIsland = new ArrayList<>();
				for (int z = 0; z < p; z++) {
					int items = scan.nextInt();
					listIsland.add(items);
					set.add(items);
				}
				listOfN.add((ArrayList) listIsland);
			}
			if (findAll(k, set) == false)
				System.out.println("sad");
			else {
				ArrayList myList = new ArrayList<>();
				for (int y = 1; y <= k; y++) {
					myList.add(y);
				}
				for (int l = 0; l < listOfN.size(); l++) {
					ArrayList myListReturn = findAllAL(myList, listOfN.get(l));

					if (myListReturn.size() == 0 && l < listOfN.size() - 1) {
						System.out.println("some");
						break;
					} else if (myListReturn.size() == 0 && l == listOfN.size() - 1) {
						System.out.println("all");
						break;
					}
				}
			}
		}
	}
}