Codegoda 2021 Problem Editorials
Official editorials for the problems in Codegoda 2021, a programming competition by Agoda.
What is Codegoda?
Watch the video below or read all about Codegoda 2021 here.
Table of Content
- Busy Day
- Origami
- Ransomware
- Codegoda City
- Which microservice failed?
- Hotel Hopper
- Agojiberries
- Agoji Print
- Find the Best Hotel
1. Busy Day
Agoda has made it to a parallel world where human life expectancy is exceedingly high, and people have lots of time to spend for holidays. So, a typical booking with Agoda can span tens of thousands of days!
You are a data scientist in this parallel world, and you would like to find Agoda’s busiest day, which is defined as the day with the highest total number of room nights from Agoda’s bookings. There are N bookings in Agoda’s system. Each booking has a check-in date and a check-out date. A room night is a measure of occupancy, where one room is occupied for one night.
For instance, here is an example of three bookings in the system:
- Check-in date = 2121–01–01 and check-out date = 2121–01–04
- Check-in date = 2121–01–02 and check-out date = 2121–01–05
- Check-in date = 2121–01–03 and check-out date = 2121–01–06
So, the total number of room nights per day is as follows:
- 1 on 2121–01–01
- 2 on 2121–01–02
- 3 on 2121–01–03
- 2 on 2121–01–04
- 1 on 2121–01–05
- 0 on 2121–01–06
Therefore, the busiest day is 2121–01–03 because it has the highest total number of room nights.
Input format
The first line is an integer N, for the number of bookings in Agoda’s system.
N lines follow, with each line containing a check-in date and a check-out date of a booking in yyyy-mm-dd format.
Constraints
1 <= N <= 40,000
0001–01–01 <= check-in date < check-out date <= 9999–12–31
The maximum number of days between each pair of check-in and check-out dates is 3,652,058 days.
Output format
Report the busiest day in yyyy-mm-dd format. (In the event of a tie, please report the earliest busiest day.)
Sample input 1
3
2121–01–01 2121–01–04
2121–01–02 2121–01–05
2121–01–03 2121–01–06
Sample output 1
2121–01–03
Sample input 2
2
2121–01–07 2121–01–09
2121–01–07 2121–01–09
Sample output 2
2121–01–07
Sample input 3
3
2121–01–01 2121–01–31
2121–01–10 2121–01–20
2121–01–20 2121–01–21
Sample output 3
2121–01–10
Explanation of Sample Output
First test case — omitted
Second test case, the total number of room nights per day is
- 2 on 2121–01–07
- 2 on 2121–01–08
- 0 on 2121–01–09
Hence, the earliest busiest day is 2121–01–07 because it is the earliest date with the highest total number of room nights
Third test case — omitted
Busy Day — editorial
2. Origami
Given a matrix of 𝑚×𝑛 and a folding direction, determine what the matrix will look like when folded in the given way.
Given four points on a piece of paper, assume the top left corner has a value of 1, and going in a clockwise direction, each corner increases in value by 1.
Input Format
- The first line is the number of test cases (𝑡)
- The first line of each test case is the size of the matrix (𝑚 𝑛)
- The second line of each test case is the folding direction from point 𝑐 to 𝑑
- For the next 𝑚 lines, each line is the row of that matrix with 𝑛 values
Constraints
- 1 ≤ 𝑐, 𝑑 ≤ 4 and 𝑐 ≠ 𝑑
- 1 ≤ 𝑚, 𝑛, 𝑡 ≤ 1,000,000
- 0 ≤ value inside the matrix (𝑣) ≤ 9
- When folded, if the value of 𝑣𝑖𝑗 that is folded over 𝑣𝑖’𝑗’ are not the same, we considered it asymmetrical (see Sample 3)
- If a side has the size of 1, we cannot fold perpendicularly to that side.
Output Format
For each test case, print the number of the test case starting with 1 followed by the list of the resulting matrix of the folded paper. Use a hyphen symbol (-) for disappearing spaces. If the paper cannot be folded symmetrically, list “error.”
Sample Input 1
Input:
1
1 1
1 2
0
Sample Output 1
1
error
Sample Output 1 Explanation
The matrix has the size of 1×1, so it’s not foldable.
Sample Input 2
1
3 3
1 3
0 1 2
1 3 1
2 1 0
Sample Output 2
1
- -2
- 31
210
Sample Output 2 Explanation
If we fold it from corner 1 to corner 3, the numbers match the opposite numbers, so we can fold it symmetrically. The top left part has disappeared, so it is replaced with a hyphen symbol (-) in the output.
Sample Input 3
1
- -1 2
- 1 2
5 6
Sample Output 3
1
error
Sample Output 3 Explanation
We have a foldable matrix. However, when we fold from corner 1 to corner 2, the values inside the matrix are different (5 and 6), so we cannot fold it symmetrically.
Origami — editorial
3. Ransomware
Your friend is a victim of a ransomware attack, and each message in his chat history has been encrypted. Each message was replaced by an encrypted message, plus the first 20 letters of the original message and a mysterious number.
Your friend would like to recover the chat messages but does not want to pay the attacker, so he asked for your help. You retrieved a copy of the ransomware, and after reverse-engineering it, you found the following:
The encryption was performed by swapping letter pairs in the message. For example, if the software decided to swap the letters “A” and “K,” then all “A”s would be replaced with “K”s, and all “K”s would be replaced with “A”s. Spaces are left intact, and each message is encrypted independently, meaning the letter pairs learned in the first message cannot be used to decrypt the second message.
The mystery number is a 31-bit integer computed from the original message using the following algorithm:
x = 424242
for each letter in the message:
x = ((x << 5) + x) + ch
x = x & 0x0FFFFFFF
Whereas:
- ch is the character in each message (space = 0, A = 1, B = 2 and so on)
- << is the bitwise left shift operator
- & is the bitwise AND operator
For example, the mystery number for “AB CD” is 145701404.
Input format
On the first line, the integer T represents the number of messages. Then for each message, there are three lines:
1. The encrypted message
2. The first 20 letters of the original message
3. The mystery number
Constraints
1 ≤ T ≤ 100
Each message contains only uppercase English letters (A to Z) and spaces. There is no punctuation.
Each message is at least one character long and no more than 1,000 characters long.
It is guaranteed that only the correct decryption of the message will result in the specified mystery number.
For each message, there are at most eight distinct characters for which their counterparts are not revealed in the first 20 letters of the original message.
Output format
The decrypted message (one line for each chat message)
Sample Input
2
UVKKQ UQX DIV BQH DIV BQH UDTTB XUDP DIV BQH AQRZM PURC XVVLVZA
HELLO HOW ARE YOU AR
62071285
CUSSD FDMSO
HELLO WORLD
55125742
Sample Output
HELLO HOW ARE YOU ARE YOU HAPPY WHAT ARE YOU DOING THIS WEEKEND
HELLO WORLD
Explanation of Sample Output
The input contains two messages, so the output must contain two lines.
The first line is the decrypted message from lines 2–4 of the input. The second line is the decrypted message from lines 5–7 of the input. (Since the example message is less than 20 letters long, it is the same as “the first 20 letters of the original message” given in the input.)
Ransomware — editorial
4. Codegoda City
Codegoda City is preparing to welcome back international tourists. The city is full of attractions, many of which can be reached through several bi-directional connections. However, some attractions are connected through only one pathway. These one-path connections are called Goji Connections, and the local mayor is concerned that once tourism is open, these connections may produce large crowds that inhibit social distancing.
The mayor wants to expand these one-path connections to create more connections and safer tourism. However, Codegoda City has never mapped all the Goji Connections. Please help the local mayor to find all the Goji Connections so international travel to Codegoda City can start again!
Input Format:
First line: N represents the number of cities.
Next N lines: city number, colon, then city numbers separated by commas.
Ex. 2:3, 4 means that City 2 is connected to City 3 and City 4.
Output Format:
First line: C — number of Goji Connections
Output Format:
C — amount of godgi connections path and the list s in ascending order by city.
#city1 — #city
Sample Input:
4
1: 2
2: 1, 3, 4
3: 2, 4
4: 2, 3
Sample Output:
1
1–2
Codegoda City — editorial
5. Which microservice failed?
Microservice architecture has gained more attention recently. In microservice architecture, one service needs to call other services (its dependencies) in order to get the data it requires to process a request. If one of its dependencies fails, it might not be able to process the request.
Example dependency diagram:
In the above example, A depends on B and C, and C depends on E and F, and so on.
In order to ensure that each of the microservices functions correctly, a monitoring system is used. Alerts are triggered whenever errors are detected in a service. The problem is, if a service fails, the service depending on it might fail as well, triggering several alerts. Having multiple alerts at the same time makes it difficult to know which service failed first. For example, if the alert for F is triggered, the alert for C and A might (or might not) be triggered as well.
Your task is to write software that can identify which service (or services) is the root cause of the failure. A failure is a root cause only when there are no other direct or transitive dependencies which also fail.
Input format
1st line: number of different test cases (NC).
2nd line: number of services (NS), followed by the name of each service separated by a space. The service names contain uppercase English letters only, underscore characters and numbers. Service names will be provided in lexicographical order.
3rd line: number of dependency relationships (ND), followed by the dependencies in the format of “A,B” meaning “A depends on B.” The letters should be separated by a space.
4th line: number of different alert cases (NA).
5th line: number of services with alerts, followed by the name of each service separated by a space.
* The 5th line repeats the number of times indicated on the 4th line.
* The 2nd through 5th lines repeat the number of times indicated on the 1st line.
Constraints
1 ≤ NC ≤ 5
1 ≤ NS ≤ 1000
1 ≤ ND ≤ 2000
1 ≤ NA ≤ 2000
Services shall not have direct or indirect circular dependency. In other words, if A depends on B, then B will not depend on A.
There will not be any duplicate dependencies in the input.
Output format
For each case, print the number of services that are identified as the root cause followed by the name of the services arranged lexicographically separated by spaces.
Example Input
1
6 A B C D E F
6 A,B A,C C,E C,F B,D E,D
4
1 E
3 A C E
2 A D
3 D E F
Example Output
1 E
1 E
1 D
2 D F
Explanation of Sample Output
The input has 1 test case, 6 services, 6 connections and 4 alert cases. It is the case shown in the diagram in the description.
In the first case, only service E has an alert. Thus, E is the root cause.
In the second alert case, services A, C and E have alerts. Since A depends on C and C depends on E, we don’t consider them the root cause. E has no dependency and has an alert. Thus, E is the root cause.
In the third case, services A and D have alerts. Since A depends on D through C, B and E, we still consider that the failure on service D might have caused a failure on service A even if the alerts on services C, B and E did not fire. Thus, D is the root cause.
In the fourth case, services D, E and F have alerts. E depends on D, so E is not the root cause. D and F do not depend on any services which failed, so they both are the root causes. This example shows that there can be multiple root causes. D must be listed in the answer before F because the output is expected in lexicographical order.
Which microservice failed? — editorial
6. Hotel Hopper
As the pandemic begins to wane, you’re looking forward to traveling again. There are many hotels offering discounted vouchers that you can buy today and use later in a given timeframe. You’re planning a holiday. (Let’s pretend there are no travel restrictions.)
There are ℎ hotels offering vouchers for future use. Each voucher can be used to stay at the hotel between the dates 𝑑 and 𝐷 (inclusive) and have a value of 𝑣.
You’re planning to stay at as many hotels as possible with the goal to maximize the value of each stay. You are guaranteed that if you go to the hotel and present the voucher, you’ll be able to stay between the dates 𝑑 and 𝐷 at no extra cost. Each of your vouchers is only valid for the given range, and you don’t plan to pay to extend your stay at any hotel. If you use a voucher, you must use on the date 𝑑 and check out on the date 𝐷. You cannot check in later or check out before the given dates.
What hotels will be on your itinerary?
Input Format
- The first line: number of scenarios (𝑛)
- For each scenario:
- A number of lines for the vouchers (𝑉)
- The start date and end date (𝑡, 𝑇) of your holiday are inclusive and separated by a space - For each line in the next 𝑉 lines:
- The hotel ID as a number (ℎ)
- The inclusive range of dates (𝑑, 𝐷) that you can use the voucher
- The value of the voucher as an integer (𝑣)
- The data, separated by spaces (ℎ 𝑑 𝐷 𝑣) - All of the date inputs are in the 𝚍𝚍 𝙼𝙼 𝚢𝚢𝚢𝚢 format
Constraints
- 0 ≤ 𝑉 ≤ 100,000
- 2022–01–01 ≤ 𝑑, 𝐷, 𝑡, 𝑇 ≤ 2030–12–31
- 𝑑 < 𝐷 and 𝑡 < 𝑇
- 0 ≤ ℎ, 𝑣 ≤ 1,000,000
- The voucher is only for the given range.
- The check-in and check-out time is12:00 (noon), so you can go from hotel to hotel seamlessly.
- It is guaranteed that there is an answer and at least one voucher will be used.
Output Format
- For each scenario, list the maximum amount of value you can obtain from using the vouchers.
- A hyphen surrounded by spaces to separate the maximum value and the hotel list
- List of the hotel IDs separated by spaces (ℎ₁ ℎ₂ ℎ₃)
- If there are multiple possibilities, choose a voucher that has earlier expiring date
Sample Input
3
1
2022 01 01 2022 12 31
1 2022 01 01 2022 12 31 5000
2
2022 01 01 2022 12 31
1 2022 01 01 2022 01 02 3000
5 2022 01 01 2022 01 02 5000
3
1 2022 01 01 2022 01 31 7000
12 2022 01 01 2022 01 30 7000
55 2022 02 01 2022 02 31 2000
Sample Output
5000–1
5000–5
9000–12 55
Sample output explanation
For the first test case, there is only one possible stay: 2022–01–01 at the value of 5000 at hotel 1.
For the second test case, both hotels 1 and 5 offer vouchers for 2022–01–01 to 2022–01–02, so since you have to choose one of them, you choose hotel 5 which offers a higher value.
For the last test case, you can enjoy all three hotels. Hotels 1 and 12 fall into an overlapping period, so you can follow the input order of 1,12,55.
Hotel Hopper — editorial
7. Agojiberries
Two Agoji friends, Red and Green, are playing their favorite game called Agojiberry Picking. (You can see examples of Agojis in the “Agoji Print” problem.)
Here are the rules of the game:
- There are N Agojiberry trees placed in a row. Each tree has a predetermined number of berries.
- Red and Green will take turns choosing one tree on either end of a row and pick all the berries from that tree.
- After the berries have been picked, the tree will magically disappear from the row, and berries cannot be picked from it again.
- Red always starts the game.
- The player who picks the most Agojiberries wins the game. The game is considered a tie if both players pick the same number of Agojiberries.
After playing the game for a while, both Red and Green decide they want to add a new rule:
- If the number of Agojiberries on the trees on both ends are the same, the players may pick all the berries from both trees. (They still can pick only one tree when both trees have the same number of berries.)
Red and Green are experts at this game and will play the game optimally.
Can you predict the result of each game before and after the introduction of the new rule?
Input format
The first line is the number of test cases (T)
The first line for each test case is the number of trees (N).
Followed by the second line will contain N numbers separated with a single space, representing the number of Agojiberries on each tree.
There will be at most 25 test cases.
For at least 60% of the test cases, there will be at most 100 trees.
For all test cases, there will be at most 500 trees, and the sum of all Agojiberries in all trees will not exceed 1⁰⁹.
Output format
Each line contains the winner of the game without the new rule, followed by the winner of the game with the new rule separated by a single space.
Use Red or Green to output the winner. In case of a tie, please list “Tie.”
Sample Input 1
2
2
1 1
3
1 999 1
Sample Output 1
Tie Red
Green Green
Explanation of Sample Output 1
For the first test case
2
1 1
In this game, there are two trees with one berry each.
Without the new rule, Red can pick from either tree and earn 1 berry. Green will then pick from the remaining tree, ending the game with each player having 1 berry.
With the new rule, Red can pick from both trees, leaving Green with no trees to pick from, which will end the game with Red having 2 berries and Green having none.
For the second test case
3
1 999 1
In this game, there are three trees.
Without the new rule, Red can pick from a tree on any end and earn 1 berry. However, after Red picks, Green will be able to pick from the tree with 999 berries, thus winning the game. (Note that a player must pick from at least one tree during the player’s turn.)
With the new rule, Red can now pick from trees on both sides of the row, as the number of Agojiberries is the same. However, with 2 berries, Red cannot win as Green will be able to pick from the tree with 999 berries.
Sample Input 2
3
1 999 1
Sample Output 2
Green Green
Explanation of Sample Output 2
In this game, there are three trees.
Without the new rule, Red can pick from a tree on any end and earn 1 berry. However, after Red picks, Green will be able to pick from the tree with 999 berries, thus winning the game. (Note that a player must pick from at least one tree during the player’s turn.)
With the new rule, Red can now pick from trees on both sides of the row, as the number of Agojiberries is the same. However, with 2 berries, Red cannot win as Green will be able to pick from the tree with 999 berries.
Agojiberries — editorial
8. Agoji Print
Agoda has its own line of emojis called Agojis, and because every Agodan loves Agojis, now everyone wants Agoji stickers! To fulfill this request, the People Team director wants to print N Agojis.
Agojis come in M unique styles, and for each style, there is a minimum A requirement and a maximum B requirement (A>0, B>=A) for printing.
In order to print the Agojis, you must calculate the number of distinct ways that N Agojis can be printed, while satisfying the minimum and maximum requirement for each unique style of Agoji. Since the answer could be a very large number, please calculate your answer using mod 1e9+7.
Input Format
The first line contains two integers, N and M (total Agojis and types of Agojis).
The second line (M) contains two integers, A and B (minimum and maximum requirements of 0<A <=B <=N for Agojis of i-th type in i-th line).
Constraints:
1<=N<=1e6
1<=M<=16
0< A <= B <= N
Output Format
A single integer (using mod 1e9+7) that represents the number of distinct ways the Agojis can be printed.
Sample Input 1
9 3
2 4
2 4
2 4
Sample Output 1
7
Sample Input 2
6 2
3 3
3 3
Sample Output 2
1
Sample Input 3
4 2
3 4
2 4
Sample Output 3
0
Explanation of Sample Output:
In the first test case, the requirement is to print 9 Agojis from three types of Agojis. Let’s say these Agojis are as follows:
For each Agoji, the minimum requirement is 2 and the maximum requirement is 4, so we can print them in the following combinations:
2 + 3 + 4
2 + 4 + 3
3 + 2 + 4
3 + 3 + 3
3 + 4 + 2
4 + 2 + 3
4 + 3 + 2
Now, we can see there are 7 ways in total to print the Agojis.
Agoji Print — editorial
9. Find the Best Hotel
Agoda is looking forward to expanding the business into a new country. This country has N cities that are connected using N-1 roads. The roads are built so that all cities are interconnected.
Agoda plans to launch a platform that will allow new hotels to register into the system. It also will allow tourists to search for hotels in which they want to stay.
Each tourist is in one of N cities. They want to find the cheapest cost for a one-night hotel stay, so they start searching on Agoda.
The total cost of staying in a hotel for one night comprises two parts:
- The cost of a taxi to go to the hotel (the cost of the gas times the distance from the tourist’s location to the hotel).
- The cost of a single room per night at the hotel.
Your task is to implement a program that supports two operations:
- H <name> <u> <c> A new hotel named name located at city u has registered into the platform. The hotel costs c for a single room per night.
- Q <v> A tourist located in city v asks the platform to find the best hotel price. In this operation, output the hotel which has the best total cost in a format of <hotel-name> <total-cost>.
Input format
- The first line: the number of cities (N) and the cost of the gas for the taxi ride to the hotel (G).
- The next N-1 lines: three values of u v d. This means there is a road between city u and v with a distance of d.
- The next line: the number of operations (K).
- The next K lines: each line contains the operation as described above.
Output format
For each query operation, output the name of the cheapest hotel and the total cost to stay at that hotel for a night.
Note:
- The first operation must be a hotel registration.
- Hotel names consist of only a-z, A-Z or 0–9.
- If multiple hotels cost the same to stay for a night, the platform will choose the hotel that registered first.
Constraints:
- N <= 50,000
- K <= 200,000
- The hotel name length combined <= 200,000
- The distance between cities <= 1⁰⁶
- The cost for a single room per night <= 1⁰⁶
Sample Input
5 2
1 2 1
2 3 1
3 4 1
4 5 1
4
H AgodaTestHotel1 3 10
Q 5
H AgodaTestHotel2 1 5
Q 5Sample Output
AgodaTestHotel1 14
AgodaTestHotel2 13Explanation of Sample Input/Output
In the first tourist query, there is only one hotel, so the cost of staying at that hotel, if the tourist is in city 5, is calculated as follows: 2 (for gas) x 2 (the distance from city 3 to city 5) + 10 (the cost of the room) = 14.
The second tourist query is made after another hotel registers into the system. If the tourist is in city 5, this hotel will cost 2 (gas) x 4 (distance from city 1 to city 5) + 5 (cost of the room) = 13, which is less than staying at the first hotel.
Find the Best Hotel — editorial
Special thanks to the Codegoda 2021 question team members Pakkapong, Narong, Nasorn, Papan, Pekka, Shamshad, Thammarith, Viktor, Phirasit and Pawit; our proofreaders Korina and Wesley; our VP of Data Idan; and all who helped make Codegoda 2021 possible.
See you at the next Codegoda!
