Codegoda 2023 Problem Editorials

Official editorials for the problems in Codegoda 2023, a programming competition hosted by Agoda.

What is Codegoda?

Codegoda is a coding competition hosted by Agoda to foster a community of programmers across the globe. We first started an open programming competition in 2019 and, with a rebranding, continued in 2021 and 2022.

Read all about Codegoda 2023 here.

Codegoda 2023 had a total of 6 problems distributed among 5 sections. The first three problems were selected randomly from a group of problems of similar difficulty, while the last three problems were the same for all participants.

The editorials for the fixed problems are shown below. You can find the solution to the remaining problems here.

Table of Content

1. Agojis Equal Day Trip
2. Search Result Ranking
3. Trip Planner

1. Agojis Equal Day Trip

Jump to the solution

Agoji is a traveler who loves to explore new cities. He has planned a trip to visit different cities around the world. Agoji has received N offers for different cities for his trip. Each offer contains the city name, the maximum number of days in the city, and the price per day. With each offer, he can choose to stay for any number of days between 0 and max number of days.

His goal is to maximize the total stay while minimizing the total cost. The number of days he stays per city must be equal as he does not want to visit some cities more than others. It’s not required for him to visit all cities available.

Can you help him find the best deals for his trip?

Input Format

The first line of the input is an integer, N, which represents the number of offers.

Following that, there are N lines, each consisting of three values separated by spaces. The first value is a string, city_name, representing the name of a city. The second value is an integer, max_num_days, indicating the maximum number of days a traveler can stay in that city. The third value is an integer, cost_per_day, representing the daily cost of staying in the city.

Constraints

Output Format

Print two values — maximum number of days and minimum cost

Sample Input

5
Nyc 4 100
Bangkok 3 10
Nyc 2 15
Warsaw 1 12
Paris 3 80

Sample Output

9 400

Explanation

An optimal solution is to choose offers 1, 2, 3, and 5, allowing Mr. Agoji to spend three days each in New York City, Bangkok, and Paris for a total of nine days. This approach satisfies all the problem constraints and minimizes the cost of the entire trip, which comes out to be 400.

Sample Input

8
London 2 100
Delhi 1 50
Paris 3 200
Rome 2 100
London 1 40
Paris 1 80
Bangkok 5 170
Delhi 3 75

Sample Output

12 1430

Agojis Equal Day Trip — Solution

2. Search Result Ranking

Jump to the solution

Agoda has millions of hotels listed on its website. Each hotel has an id, a name, a location, and information about the type of accommodation it offers. To advertise these hotels on Elgo, Agoda has built a list of keywords that are relevant to each hotel. For example, the keywords for the hotel “The Grand Hotel” might be “luxury,” “spa,” “beach,” “grand,” “hotel,” “resort” etc.

Each keyword is associated with a score. The score is a positive integer indicating the keyword’s relevance to the hotel. For example, the keyword “grand” might have a score of 100, while the keyword “hotel” might have a score of 10. The score of a keyword is independent of the other keywords. It should be noted that the keywords are not unique, and a keyword can have different scores for different hotels.

Elgo is a search engine that allows users to search for hotels by search queries. A search query is a string of words. The search results are ranked by the relevance of the hotels to the search query. The relevance of a hotel to a search query is the sum of the scores of the keywords relevant to the hotel, i.e., the keywords present in the search query.

For example, suppose we have a hotel with id 1 and the keywords “grand” and “hotel” with scores 100 and 10, respectively. In that case, the relevance of the hotel to the search query “grand hotel”, “luxury hotel bangkok” and “spa in bangkok” is 110, 10, and 0 (irrelevant), respectively.

Elgo has a limit on the number of hotels that can be displayed in the search results. If the number of hotels relevant to the keywords exceeds the limit, Elgo will only display the hotels with the highest relevance sorted in descending order of relevance. If there are multiple hotels with the same relevance, the hotels with the lowest id will be displayed first.

Given lists of hotels, their keywords, and search queries, print a list of recommended hotels for each query.

Input Format

The first line contains two space-separated integers, N and M, where N is the number of hotels and M is the number of search queries.

The next N lines start with two space-separated integers, H and K, where H is the id of the hotel, and K is the number of keywords associated with the hotel. It is followed by K space-separated keyword-score pairs, where each keyword-score pair consists of a keyword and a score separated by a space. The keyword is a string of lowercase English letters. The score is a positive integer

The next M lines start with an integer L, representing the number of words in search query, followed by L space-separated words. Each word is a string of lowercase English letters.

Constraints

All hotel ids are unique

Keywords for each hotel are unique

Output Format

For each search query, print the hotel ids displayed in the search results. The ids must be printed in the order they appear in the search results. If there are no hotels that are relevant to the search query, print -1. If there are more than 10 hotels that are relevant to the search query, print only the first 10 hotels.

Sample Input

3 2
101 3 grand 100 hotel 10 center 5
201 3 luxury 100 bangkok 10 hotel 1
301 2 goa 50 resort 50
2 grand hotel
1 goa

Sample Output

101 201
301

Explanation

For search query “grand hotel”, the relevance of hotel with id 101, 201, and 301 are 110, 10, and 0, respectively. Since the first two hotels are relevant to the search query, they are displayed in the search results. The relevance of hotel with id 301 is 0, so it is not displayed in the search results.

For search query “goa”, the relevance of hotel with id 101, 201, and 301 are 0, 0, and 50, respectively. Since only the third hotel is relevant to the search query, it is displayed in the search results.

Sample Input

5 5
10 3 delhi 100 holiday 5 hotel 50
11 3 delhi 100 business 6 hotel 30
12 3 spa 100 luxury 20 hotel 5
14 3 delhi 100 luxury 9 hotel 10
15 3 london 500 luxury 8 hotel 30
3 luxury business hotel
3 cheap hotel london
3 delhi luxury hotel
4 vry qiravx heqpc deu
2 business holiday

Sample Output

10 15 11 12 14
15 10 11 14 12
10 11 14 15 12
-1
11 10

Search Result Ranking — Solution

3. Trip Planner

Jump to solution

Agoda’s objective is to provide the best price to customers, but it is not always easy. There are many factors that affect the price. For example, the price of a hotel room depends on the number of rooms available, the number of people who want to book the room, etc.

For each hotel room, Agoda has a price for each day of the year. Agoda offers discounts for long stays. It also offers “Agoda Cash” on specific days in the year to make customers happy and encourage them to book more.

Mr. Agoji, who always books hotels through Agoda is planning his next long holiday. Specifically, he wants to go to Agodaland, which has N hotels for D days. He knows the price of each hotel for each day. He also got a secret deal message from Agoda for a set of P hotels that if he books a hotel room Q for at least X consecutive days, he gets Y % discount on the total price of the consecutive stay at the hotel. The total discount is rounded up to the smallest integer not smaller than the discount itself. To make things more interesting, when he logged in to Agoda app on his phone, he got a notification of all available Agoda Cash for a list of hotel rooms and days.

He cannot wait to book the hotel rooms. He knows that he can maximize Agoda Cash and minimize the cost of staying in Agodaland by optimally selecting which hotel room to book for each day. However, there is another challenge for him. He must travel from one hotel to other, but not all hotels are connected to each other

Specifically, there are M bidirectional roads each connecting two hotels, U and V, with a cost C of traveling from one hotel to other. Mr. Agoji can travel from one hotel to another only if there is a sequence of roads connecting them. For this problem you can assume that traveling from one hotel to another is instantaneous.

Mr. Agoji has a superpower, on day one he can magically go to any one hotel. After that he can only travel from one hotel to another using the roads.

Mr. Agoji wants to know the maximum Agoda Cash he can get and the minimum cost of staying in Agodaland. Can you help him? It should be noted that you should maximize Agoda Cash first and then minimize the cost of staying in Agodaland.

Warning: Please note that if you’re using a slower programming language like Python, there’s a possibility that the code might exceed the time limit and result in a timeout error on large input.

Input Format

The first line contains three space-separated integers number of hotels N, number of days D, and number of roads M.

The next N lines contain D space-separated integers each. The Jᵗʰ integer in the ith line Priceᵢⱼ denotes the price of ith hotel on day J.

The next M lines contain three space-separated integers hotel U, hotel V and cost of traveling C.

The next line contains an integer P. The next P lines contain three space-separated integers hotel Q, number of consecutive days X, and discount Y(in percentage).

The next line contains an integer, the number of Agoda Cash K. The next K lines contains three space-separated integers hotel contain R, day S and Agoda Cash T.

Constraints

There are three types of testcases. Constraints on the number of hotels, N, and the number of days, D, are different for each type but constraints on other parameters are the same

Small Input

1 ≤ N , D ≤ 8

Medium Input

9 ≤ N , D ≤ 20

Large Input

21 ≤ N , D ≤ 250

Constraints on other parameters

0 ≤ M ≤ 1000

0 ≤ P ≤ N

0 ≤ K ≤ N × D

1 ≤ U, V, Q, R ≤ N

1 ≤ X, S ≤ D

1 ≤ Y ≤ 100

1 ≤ Priceᵢⱼ, T ≤50000

U ≠ V

All Q are distinct

All pair of (R, S) are distinct

Output Format

Two space separated integers, the maximum Agoda Cash, and the minimum cost of staying in Agodaland.

Sample Input

3 3 3
10 25 5
20 30 1
2 2 2
1 2 10
2 3 5
1 3 6
1
2 2 50
3
1 1 7
1 2 10
2 2 10

Sample Output

17 35

Explanation

There are several ways to maximize the amount of Agoda cash earned, but one optimal solution is to stay at hotel 1 for all three days, which would earn $17 in Agoda cash. However, the cost of this stay would be $40. After trying all possible combinations, it becomes clear that it’s impossible to earn more than $17 in Agoda cash.

However, it is possible to minimize the overall cost of the trip while still earning the maximum amount of Agoda cash. For example, the traveler could stay at hotel 1 on the first day, then travel to hotel 2 on the second day and stay there for the next two days. This would cost $10 for staying at hotel 1 on day 1, $10 for traveling from hotel 1 to hotel 2 on day 2, $31 for staying at hotel 2 on days 2 and 3, and a discount of $16 (50% of $31 rounded up for staying at hotel 2 for at least two consecutive days) for a total of $35.

Sample Input

2 5 1
25 25 50 50 50
100 120 60 60 60
1 2 20
1
2 2 20
6
1 2 30
1 3 40
2 1 20
2 2 30
2 3 40
2 4 10

Sample Output

100 309

Trip Planner — Solution

Special thanks to Shamshad Alam, Avi Mallick, Sunil Kumar Garg, Ozioma Ogbe, Angel Chen, Md Foyaz Rahman Akanda, Faisal Ahmed, Freeze Francis, Vince Luk, Gaurav Lalchandani and the rest of the Codegoda 2023 question team.

See you at the next Codegoda!