Codegoda 2022 Problem Editorials
Official editorials for the problems in Codegoda 2022, a programming competition hosted by Agoda.
What is Codegoda?
Codegoda is a global programming competition organized by Agoda. It offers fun challenges and brings together all the coder communities from around the world.
Watch the video below to learn more or read all about Codegoda 2022 here.
In Codegoda 2022, there were 6 problems for participants to solve within 3 hours. The editorials for all problems can be found below.
Table of Content
1. Company Group
Booking Holdings is looking to acquire a new company for the group. Joe is the one assigned to gather the information in the market. One of the most popular questions for Joe is whether these two companies are in the same company group or not. Your job is to help Joe answer this question quickly.
Input
line 1: C, R, Q — number of companies, number of relationships, number of questions
line 2 — (R+1): ai, bi — pair of parent company and subsidiary, means that company ai is a parent company of company bi
line (R+2) — (R+2+Q): xj, yj — asking if xj and yi are in the same group or not.
Constraint:
- 0 < C < 100,000
- 0 <= R <= C(C-1)/2
- 0 < Q < 100,000
- 1 <= ai, bi, xj, yj <= C
Output:
Q lines, each line shows either
YES when associated xj and yj are in the same group
NO, when associated xj and yj are not in the same group
Sample Input
5 3 5
1 2
1 3
3 4
1 2
2 3
1 4
2 4
2 5
Sample Output
YES
YES
YES
YES
NO
CODE — Company Group Solution
2. Happy Tourism
It’s World Tourism Day, and Agoda has launched a special promo code. With each hotel booking a person makes, they can get a cashback randomly and uniformly distributed from the range [1, maxCashBack] in integer USD. A person will start with 0 cashback and can keep applying this promo code until they secure a minimum of M USD in total across all their future bookings.
To keep the customers happy, Agoda wants to ensure that most people can make at least H USD from this promo code.
For this, Agoda has requested your help to calculate the probability of a customer not being happy (total cashback received < H) with this promo code given M, MaxCashBack, and H.
Please note that a user will keep applying this promo code for all his bookings as long as allowed. Please return answers accurate up to 5 decimal places.
INPUT
The input will consist of 3 space-separated integers M, MaxCashBack and H.
0 <= M <= H <= 10⁴
1 <= MaxCashBack <= 10⁴
OUTPUT
The calculated probability
Sample Input
1 10 11
Sample Output
1.00000
CODE — Happy Tourism Solution
3. Merge and Break
You are given N arrays of distinct positive integers. The ith array has size K[i] (1 <= i <= N). You want to form a single array out of them, sorted in ascending order. However, you can only perform 2 kinds of operations:
Break
Choose any of the available arrays with size > 1, and then break it at any point, so that array is divided into 2 non-empty parts.
For example, an array of size x & the 2 divided parts have sizes x1 and x2 respectively x1 + x2 = x , x1 > 0 , x2 > 0. Then the cost of this operation is min(x1, x2).
Merge
Choose any 2 arrays and merge them, interleaving their elements without rearranging the elements of individual arrays. In other words, if the 2 arrays merged had sizes x1&x2, the merged array will have size x1 + x2, and both the individual arrays will be present as disjoint subsequences in the merged array.
For example, 2 arrays merged had sizes x1 & x2 (x1 > 0 , x2 > 0). Then the cost of this operation is x1 + x2.
You have to find out what is the min cost to create a single sorted array out of them.
INPUT
The first line contains an integer T — the number of test cases. Then T test cases follow. The first line of a test case contains a single integer N, the number of arrays you have. Then N lines follow. The first integer in the ith of the next N lines is K[i], the size of the ith array, and is followed by K[i] space-separated integers representing elements of ith array. All the numbers in each of the arrays are integers in the range [1,1e9]. Within a single test case, all the numbers in the array are distinct. The sum of K[i] in any input file will not exceed 4 * 1e5.
Constraints
1 <= T <= 7
1 <= N <= 100000
1 <= K[i] <= 100000
1 <= I <= N
Sample Input
3
2
2 1 3
1 2
1
3 3 2 1
1
3 1000000000 7000 900000
OUTPUT
For each test case, print on a new line, a single integer denoting the minimum cost required to create a single sorted array using the operations mentioned in the problem statement.
Sample Output
3
7
4
CODE — Merge and Break Solution
4. Shuffled String
Mr Agoji is given a shuffled string made by randomly shuffling a special string.
A string is special only if it is formed by joining some special words any number of times. Special words are mapping of numbers (0 <= number < 10) to their words, for example, mapping of ‘0’ to ‘zero,’ mapping of ‘1’ to ‘one,’ and so on.
Mr Agoji is asked to convert the shuffled string to the smallest special number. A special number is a number formed using numbers (0 <= number < 10) without any leading zeroes.
Mr Agoji, who is not so good with numbers and strings, has asked for your help.
INPUT
The first line of the input will contain T, number of test cases. For each test case, there will be a, s shuffled string, on a separate line.
1 <= T <= 100
1 <= s.length <= 100000
OUTPUT
For each test case, on a new line, the smallest special number is in the string format.
Some notes on output:
Shuffled string will always be able to convert into at least one valid special string.
Shuffled string will only contain small English alphabets.
If shuffled string contains only zeroes, you should output “0”.
Sample Input
2
“ewtooetzrowon”
“ttnrwoooeeefurh”
Sample output
1022
1234
CODE — Shuffled String Solution
5. Stone Game
Mr Agoji was bored in lockdown, so he designed a game for himself. The game is played on a sequence of piles of stones. Let's say there are N integers s1, s2, …., sn, describing the number of stones in each pile. On each turn, Mr Agoji picks a pair of non-empty adjacent piles i and i+1 and takes 1 stone from each. If a pile(ith) becomes empty, then its adjacent piles(i-1th and i+1th) do not become adjacent.
The game ends when Mr Agoji can’t make a turn anymore. He wins if he can clear all the piles. We consider a sequence of piles winning if Mr Agoji can start with it and win the game. You are given a sequence of integers s1, s2, s3, …., sn. You have to find out how many subsegments of this sequence are winning. A subsegment is defined as a continuous sequence from L to R, i. e. sL, sL+1, ….., sR, given 1 <= L < R <= N.
INPUT
The first line of the input contains number of test cases, T. The next T test cases follow an integer N, denoting the number of piles of stones. Next line contains N integers, s1, s2, s3,……, sn describing the number of stones in each pile.
1 <= T <= 10⁵
1 <= N <= 10⁵
0 <= si <= 10⁹
OUTPUT
Print a single integer for each test case — the answer to the problem.
Sample Input
6
2
2 2
3
1 2 3
4
1 1 1 1
4
1 2 2 1
4
1 2 1 2
8
1 2 1 2 1 2 1 2
Sample output
1
0
4
2
1
3
CODE — Stone Game Solution
6. Best Hotel
Mr Agoji plans to travel to a new city for his vacation. There are N number of hotels available in that city. Each hotel has information on the price/night and rating. Mr Agoji has a tight budget for his trip, so he can’t afford to book a costly hotel but wants the best experience in his budget range, so he plans different budgets for his trip.
There are Q different budget options for hotel booking in his budget plans. Mr Agoji, who is not that good at calculations, has asked for your help to decide on the best-rated hotel in his budget.
You are given a list of hotel names, the price per night, and the hotel’s rating. For different budget ranges, you have to find the best-rated hotel for Mr Agoji.
Note that if two hotels in that range have the same rating, you should output the one with the lowest booking price per night, and no two hotels should have the same price per night.
INPUT
The first line contains an integer T — the number of test cases. The first line of a test case contains a single integer N, the number of hotels you have and an integer Q, the number of budget ranges. Then N lines follow. A string s, the hotel name, integer p, price of the hotel per night and a double r, rating of the hotel. These will be space separated.
Note that the hotel name does not contain any spaces. Next, Q lines follow two space-separated integers L, lower limit of budget range and U, upper limit of budget range. Note that the budget range is specifically for hotel booking and not for the whole trip.
Constraint
1 <= T <= 7
1 <= N <= 100000
1 <= Q <= 100000
1 <= s.length <= 1000
1 <= p <=100000
0.1 <= r <= 10.0
1 <= U <= 100000
0 <= L <= U
OUTPUT
For each test case, for each query, print on a new line, a string denoting the best-rated hotel in the budget range of the query.
Sample Input
1
3 3
a 1000 8.1
b 800 7.6
c 1200 7.9
600 1400
700 900
300 12000
Sample output
a
b
a
CODE — Best hotel Solution
Special thanks to the Codegoda 2022 question team members: Satendra Tiwari, Tanmay Banage, Rapeepat Sriwichai, Abhishek Sharma & Namit Maheshwari
See you at the next Codegoda!
