My solution for hashcode 2021 practice problem that scored 220 million+ points

Problem description :

Task :

Help the imaginary pizzeria choose the pizzas to deliver to Hash Code teams. And since we want everyone to enjoy their food, let's try to deliver to each team, as many different ingredients as we can.

Pizza :

Expecting many hungry customers, the pizzeria has already prepared some pizzas with different ingredients. Each pizza can be delivered to at most one team. There can be multiple pizzas with the exact same set of ingredients.

For example, there are 5 pizzas available in the pizzeria:

Pizza 0: onion, pepper, olive 

Pizza 1: mushroom, tomato, basil 

Pizza 2: chicken, mushroom, pepper 

Pizza 3: tomato, mushroom, basil 

Pizza 4: chicken, basil 

Note that Pizzas 1 and 3 have the same ingredients, even though they are mentioned in different order.

Teams :

Teams of 2, 3, or 4 people all ordered pizzas. Each team ordered one pizza per team member, but did not specify what ingredients to put on the pizzas. The pizzeria might not deliver to a team (no pizzas are sent to that team). However, if the order is delivered, exactly one pizza should be available per person. For example, it is an error to send 3 pizzas to a 4-person team.

Goal : 

Given the description of the pizzas available, and the number of teams of 2, 3, or 4 people that have ordered, decide which pizzas to send to each of the teams. The goal is to maximize, per team, the number of different ingredients used in all their pizzas.

Input data set :

The input data is provided as a data set file - a plain text file containing exclusively ASCII characters with lines terminated with a single ‘\n’ character (UNIX-style line endings).

File format : 

The first line of the input contains the following integer numbers separated by single spaces:

• M ( 1 ≤ M ≤ 100 000 ) - the number of pizzas available in the pizzeria
• T2 ( 0 ≤ T 0 000 ) - the number of 2-person teams 
• T3 ( 0 ≤ T 0 000 ) - the number of 3-person teams 
• T4 ( 0 ≤ T 0 000 ) - the number of 4-person teams 

The next M lines describe the pizzas available. Each line contains (space separated):

an integer I ( 1 ≤ I ≤ 10 000 ) - the number of ingredients,

followed by the list of I ingredients - Each ingredient consists of lowercase ASCII letters and dash (-) characters, and its length can be between 1 and 20 characters in total. Each ingredient in a pizza is different but the same ingredient can appear on different pizzas.

Example : 

Output file format :

The first line of the submission contains a number D ( 1 ≤ D ≤ T ), representing the 2 + T3 + T4 number of pizza deliveries. The following D lines contain descriptions of each delivery. Each line contains the following integer numbers separated by single spaces:

• L ( 2 ≤ L ≤ 4 ) - the number of people in the team 
• followed by the list of pizzas, P1 … PL - the space separated indexes of the pizzas delivered to that team  

Even though it’s nice to deliver pizzas to all teams, it is allowed to make fewer deliveries than the number of teams. However, making more deliveries than the number of teams is an error. It is also an error to make more deliveries to 2, 3 or 4-person teams than the corresponding number of teams provided in the input file: the number of lines with L=N, should not be greater than T_N.

Example :

 

 Scoring :

For each delivery, the delivery score is the square of the total number of different ingredients of all the pizzas in the delivery. The total score is the sum of the scores for all deliveries.

Download the problem statement here.

Input data :

• A-example : Download here
• b_little_bit_of_everything : Download here
• c_many_ingredients : Download here
• d_many_pizzas : Download here
• e_many_teams : Download here

Approach to solve the problem :

• First take as much time you need to understand the problem. 
• After understanding the problem clearly, think about the logic to solve the problem.
• Then move on to the coding part.
• Choose whatever programming language that you are good at, and proceed with the same to solve the problem.

Solution in python :

import random

def printList(l):

ans=str(len(l))+" "

for i in l:

ans+=str(i)+" "

return ans

def removeNewLine(input_file,output_file):

f=open(input_file,"r")

f1=open(output_file,"w")

f2=open(output_file,"a")

line=f.readlines()

for i in range(len(line)):

line[i]=list(line[i])

for i in line[-1]:

if(i=="\n"):

line[-1].remove(i)

word=""

for i in line:

for j in i:

word+=str(j)

f2.write(word)

def pizzaria(input_file,output_file):

first=input_file.readline().split()

pizza_count=int(first[0])

two_team=int(first[1])

three_team=int(first[2])

four_team=int(first[3])

data=input_file.readlines()

data.remove(data[0])

new=[]

count=0

for line in data:

words=line.split()

words.append(count)

new.append(words)

count+=1

new_1=random.sample(new,len(new))

f=open(output_file,"w")

f=open(output_file,"a")

pizza=pizza_count

if(pizza<2*two_team):

int(pizza/2)

else:

pizza-=2*two_team

rem=two_team

if(pizza<3*three_team):

rem+=int(pizza/3)

else:

pizza-=3*three_team

rem+=three_team

if(pizza<4*four_team):

rem+=int(pizza/4)

else:

pizza-=4*four_team

rem+=four_team

f.write(str(rem))

f.write("\n")

member=1

two=0

three=0

four=0

idx=[]

ing=[]

while(pizza_count>2):

if(two<=2*two_team):

two=member

idx.append(new[new.index(new_1[member])][-1])

new.remove(new_1[member])

if(member%2==0):

f.write(printList(idx))

if(pizza_count>=3):

f.write("\n")

idx=[]

elif(three<=3*three_team):

three=member-(2*two_team)

idx.append(new[new.index(new_1[member])][-1])

new.remove(new_1[member])

if(three%3==0):

f.write(printList(idx))

if(pizza_count>=3):

f.write("\n")

idx=[]

elif(four<=4*four_team):

four=member-(2*two_team)-(3*three_team)

idx.append(new[new.index(new_1[member])][-1])

new.remove(new_1[member])

if(four%4==0):

f.write(printList(idx))

if(pizza_count>=3):

f.write("\n")

idx=[]

pizza_count-=1

member+=1

input_file.close()

f.close()

def sample_a():

file=open("a_example.txt","r")

first=file.readline().split()

pizza_count=int(first[0])

two_team=int(first[1])

three_team=int(first[2])

four_team=int(first[3])

data=file.readlines()

data.remove(data[0])

f=open("a_example_output.txt","w")

f=open("a_example_output.txt","a")

new_1=random.sample([0,1,2,3,4],5)

pizza=pizza_count

if(pizza<2*two_team):

int(pizza/2)

else:

pizza-=2*two_team

rem=two_team

if(pizza<3*three_team):

rem+=int(pizza/3)

else:

pizza-=3*three_team

rem+=three_team

if(pizza<4*four_team):

rem+=int(pizza/4)

else:

pizza-=4*four_team

rem+=four_team

f.write(str(rem))

f.write("\n")

member=0

idx=[]

for i in range(len(new_1)):

if(member<2*two_team):

idx.append(new_1[i])

if(member%2==1):

f.write(printList(idx))

f.write("\n")

idx=[]

elif(member<=3*three_team):

idx.append(new_1[i])

if((member-2*two_team+1)%3==0):

f.write(printList(idx))

if(i!=len(new_1)-1):

f.write("\n")

idx=[]

pizza_count-=1

member+=1

sample_a()

in_file_1=open("b_little_bit_of_everything.txt","r")

out_file_1="b_little_bit_of_everything_output.txt"

pizzaria(in_file_1,out_file_1)

removeNewLine(out_file_1,"b_data.txt")

in_file_2=open("c_many_ingredients.txt","r")

out_file_2="c_many_ingredients_output.txt"

pizzaria(in_file_2,out_file_2)

removeNewLine(out_file_2,"c_data.txt")

in_file_3=open("d_many_pizzas.txt","r")

out_file_3="d_many_pizzas_output.txt"

pizzaria(in_file_3,out_file_3)

removeNewLine(out_file_3,"d_data.txt")

in_file_4=open("e_many_teams.txt","r")

out_file_4="e_many_teams_output.txt"

pizzaria(in_file_4,out_file_4)

removeNewLine(out_file_4,"e_data.txt")

Score :