Welcome to A December of Algorithms (2021). After overwhelming responses from previous years, we present you with a new collection of algorithms to implement this December. Each Day, Each Algorithm ;) Finish them all to get a certificate :)
Send a pull request only after completing all 31 algorithms.
Please submit all PRs on or before January 10th 11:59 PM IST.
We have a small collection of algorithms, one for every day of the month. Scroll down to take a look at them. All you need to do is fork this repository, implement all 31 algorithms and send a pull request over to us. Check out our FAQ for more information.
- December 1 - Elegant facelift
- December 2 - Bingo!
- December 3 - Lotto!
- December 4 - Sandhya and her Tic-Tac-Toe love
- December 5 - Biscuit Bonanza
- December 6 - Save The Templars
- December 7 - Amy helps Pawnee
- December 8 - Anomalous Counter
- December 9 - Dream 11
- December 10 - Juicy Orange Field
- December 11 - Maze Festival
- December 12 - Ford vs Ferrari
- December 13 - Desert Shopping
- December 14 - The Math Test
- December 15 - Twinkling Bracelets
- December 16 - Catch Me If You Can
- December 17 - The Bossy Manager
- December 18 - Connections
- December 19 - Winter is coming
- December 20 - High Traffic Server(s)
- December 21 - Transform to Checkerboard
- December 22 - Richie Rich
- December 23 - Ant Got Track
- December 24 - Mayday Mayday!!
- December 25 - Ranthambore Diaries
- Maintainers
- FAQ
- There is a collection of necklaces where each necklace has various stones embedded in it. Each type of stone is designated by a lowercase letter in the range ascii
[a-z]. - There may be multiple occurrences of a stone in a necklace. A stone is called a
faceliftif it occurs at least once in each of the necklaces in the collection. - Given a list of stones embedded in each of the necklaces, display the number of types of
facelift's in the collection.
Input: arr = ['abcdde', 'baccd', 'eeabg']
Output: 2
Input: arr = ['abc', 'def', 'ghi', βjklβ]
Output: 0
- In sample input 1, only
aandboccur in every necklace. Therefore, the output is2. - In sample input 2, there are no characters repeating in the list. Therefore, the output is
0.
-
Your local community conducts a game night every Saturday and they want you to lead a game of Bingo this weekend. You must come up with numbers to be read out during the game. The numbers can be chosen on the basis of certain criteria.
-
Begins with a positive integer, sum of squares of digits must replace the number. Continue until the number is 1 or loops interminably without including 1.
-
The numbers which end in 1 are to be selected. Return βYESβ if the number is selected, and βNOβ if not.
Input: n = 2
Output: NO
Input: n = 19
Output: YES
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
- In a lottery game , each participant can choose a lucky board which is in the form of a 2D
(x x y)grid. He/she can win the lottery if they are able to find their name on the lucky board. Find whether a particular participant can win the game or not. Assume that there can be more than one winner who wins the lottery. - Return true if the participant wins else return false
- The name of the participant has to be arranged in a sequentially adjacent manner.
- The neighbouring alphabets can be horizontal as well as vertical
- Same alphabet cell cannot be used more than once while forming the name.
Input: [["D","J","O","G"],["W","B","H","S"],["T","Z","N","E"]], name = "JOHN"
Output: true
Input: [["L","N","A","C"],["W","B","A","D"],["T","Z","F","E"]], name = "DEV"
Output: false
- Sandhya likes to play tic-tac-toe (using
2x2matrix), and uses the elements0and1. She is wondering how many matrices withXrows andYcolumns there are. Everyone obviously knows that - it is just2Xβ Y. But what no one knows is that, she considers two identical matrices if and only if by permuting theXno.of rows and then permuting theYno.of columns, and the resulting matrix is transverse of itself. - Help Sandhya by finding the number of
XΓYmatrices which are distinct according to her definition (even though she doesn't know how to solve them). Since the answer can/may be quite large, compute it modulo 10^9+7.
Input: 1 5
Output: 6
Input: 10 10
Output: 508361223
According to Sandhya's definition, there are 6 different binary matrices.
This is because the number of 1-s uniquely identifies a 1Γ5 matrix and
the number of 1-s can take any value between 0 and 5 inclusive.
- A local biscuit store sells only
2types of biscuits: circular and rectangular biscuits. They are referred to by the numbers0and1respectively. The customers stand in a queue and they either purchase circular or rectangular biscuits. - The number of biscuits is equal to the number of customers. They are placed in a stack.
- At each step: If the customer at the front of the queue prefers the biscuit on the top of the stack, they will take it and leave the queue.
- Otherwise, they will directly go to the queue's end.
- Consider two integer arrays
customersandbiscuitswherebiscuits[i]is the type of theith biscuit in the stack (i = 0 is the top of the stack) andcustomers[j]is the preference of thejth customer in the initial queue (j = 0 is the front of the queue). This continues until none want to take the top biscuit and are thus unable to eat. - Return the number of customers that are unable to eat.
customers = [1,1,1,0,1]
biscuits = [1,0,0,0,1,1]
Customers that are unable to eat = 3
customers = [1,1,0,0]
biscuits = [0,1,0,1]
Customers that are unable to eat = 0
customers = [1,1,0,0,1,0]
biscuits = [0,1,0,1,1,1]
Customers that are unable to eat = 1
Input: customers = [1,1,0,0], biscuits = [0,1,0,1]
Output: 0
- Front customer leaves the top biscuit and returns to the end of the line making customers = [1,0,0,1].
- Front customer leaves the top biscuit and returns to the end of the line making customers = [0,0,1,1].
- Front customer takes the top biscuit and leaves the line making customers = [0,1,1] and biscuits = [1,0,1].
- Front customer leaves the top biscuit and returns to the end of the line making customers = [1,1,0].
- Front customer takes the top biscuit and leaves the line making customers = [1,0] and biscuits = [0,1].
- Front customer leaves the top biscuit and returns to the end of the line making customers = [0,1].
- Front customer takes the top biscuit and leaves the line making customers = [1] and biscuits = [1].
- Front customer takes the top biscuit and leaves the line making customers = [] and biscuits = [].
Hence all customers are able to eat.
- The conflict continues. The Templar Assasins
Tand the UndyingUare fighting to the death, but the bad is prevailing over the good. The Templars must band together in order to combat the Undying. - At the top of the Undying Resource tower, everyone is initially arranged in a circular path.
- The Templar Assassin at index 1 is in front of the Templar Assassin at index 2 and stands close to the Templar Assassin at index
n. - The Templars must band together in order to win the battle.
- The Templars have a particular ability that allows them to switch bodies with anyone.
- Assist the Templars in determining the least number of swaps required so that they can all stand together.
- Given the sequence of Templar Assasins
Tand the UndyingU, return the minimal number of swaps required.
Input: UUTUTUT
Output: 1
Input: UTUTTU
Output: 1
To get all U and T together in the sample test case, first replace the T at index 3 with U at index 6.
Second, we can combine all U and T by swapping U at index 3 with T at index 2.
- Amy Santiago is a pilot and she went to Pawnee for official work. She noticed that the city had a food shortage due to the devastating impact of COVID-19. So, she decided to help the people who are in desperate need of food by supplying them on their building with the help of her private jet-plane.
- All the buildings are represented by three pairs of points:
(a1, b1), (a2,b2) and (a3,b3). - The jet can fly in a direction either parallel to the
xaxis or theyaxis. It drops the food packets on every building Amy flies over in her flight. - The food packet will be wasted if it is dropped on the boundary of the building as it will fall down. No two buildings touch each other. Figure out the number of buildings that receive the food packets on each flight.
- A single line integer i.e the number of buildings that received the food packets on their roofs on each flight.
Number of Buildings: 3
Coordinates of the buildings:
1 0 0 2 2 2
1 3 3 5 4 0
5 4 4 5 4 4
Number of jet-planes: 3
x = 1
x = 2
y = 1
Buildings that received food:
1
1
2
Number of Buildings: 4
Coordinates of the buildings:
1 1 2 3 4 1
2 5 3 3 0 0
3 2 2 1 1 3
4 5 5 0 1 0
Number of jet-planes: 2
x=1
y=3
Buildings that received food:
1
2
- You found a rather bizarre counter around your area. You see that there are two dials, one is the cycle dial and another is the counter value dial.
- When you start the counter, you see in the counter dial that it starts with the initial value 3 and then you see the counter value decreases by 1 each second until the value becomes 1.
- In the next second you see that the cycle dialer is incremented to 1 and the counter value becomes twice the initial value of the counter in the previous cycle.
- You decided to invite your friends to play a guessing game, i.e to find the value displayed by the counter at a particular time(in seconds).
Input: time = 22
Output: counter value = 24
Input: time = 0
Output: counter value = 0
Input: time = 22
Output: 24
time=22 marks the beginning of the fourth cycle.
So the counter value is double the number displayed at the beginning of the third cycle(when time=10): 12X2 = 24.
This is shown in the diagram in the problem statement.
- As a Cricket coach, you have to pick `P` understudies to address your school. There are `N` understudies.
- The aptitude rating of `N` understudies has been given as input, which is a positive number indicating how gifted they are. Right away, it likely will not be possible to pick a sensible gathering, so you will give a piece of the understudies one-on-one educating.
- It requires one hour of preparing to extend the ability rating of any understudy by 1. The resistance season is starting very soon, so you'd like to notice the base number of extensive stretches of guidance you need to give before you can pick a sensible gathering.
- Output the base number of long periods of instruction required, before you can pick a reasonable group of `P` understudies.
N = 4, P =3
N = [3, 1, 9, 100]
Base number of periods required = 14
N = 6, P = 2
N = [5, 5, 1, 2, 3, 4]
Base number of periods required = 0
N = 5, P = 5
N = [7, 7, 1, 7, 7]
Base number of periods required = 6
- You are in a field of juicy oranges that is like a grid of size
n x n. You plan to collect most of the oranges in the field before the storm comes. Each cell can be any one of the following:- A cell can be empty (represented by 0), so you can pass through the cell.
- A cell that contains the orange trees where you can pick up the oranges and pass through to the next cell. (represented by 1)
- A cell covered with prickles and thorns that blocks your way to the next cell (represented by -1).
- As itβs a big field you have to follow certain rules to find the maximum number of oranges you can collect before the storm hits:-
- You begin at the first cell and you have to reach the last cell by moving right or down through valid cells (cells that do not contain prickles and thorns).
- After reaching the last cell, you have to return to the first cell by moving left or up through valid cells.
- When passing through a cell containing oranges, you pick it up, and the cell becomes an empty cell.
- If there is no valid path between the first and last cell, then no oranges can be collected.
Input: field = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5
Input: field = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5
You started at (0, 0) and went down, down, right right to reach (2, 2).
4 oranges were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]].
Then, the player went left, up, up, left to return home, picking up one more orange.
The total number of oranges picked up is 5, and this is the maximum possible.
-
On the occasion of Halloween, a grand corn maze puzzle has been set up in the fields of Hubbβs farm, New York. There are several mystery boxes hidden at each magic spot.
-
Assume that there are
Nmagic spots from1toNin the entire field. -
Given the points to the spots
PandQand the distance between themDand also a participant who choses the starting spotA, the path chosen to reach the final spotBand the final magic spotC. -
Identify whether the participant can reach the destination spot or not.
-
If yes print the minimum distance(shortest path) covered and the path taken by the participant to reach the final magic spot. Else print "NO PATH FOUNDβ.
-
Note: If a pathway connects
AtoBwith distanceDthen it means that it will connect fromBtoAwith the same distanceD.
Input:
N = 6
P Q D
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1
A = 1, B = 3, C = 6
Output: No path found
N = 10
P Q D
1 5 78
1 8 221
2 7 92
2 8 159
3 5 55
3 6 179
3 10 237
4 8 205
5 6 191
8 10 157
A = 6, B = 3, C = 2
Output: Shortest path = 692
Path taken = 6 3 5 1 8 2
Input:
N = 10
P Q D
1 5 78
1 8 221
2 7 92
2 8 159
3 5 55
3 6 179
3 10 237
4 8 205
5 6 191
8 10 157
A = 6, B = 3, C = 2
Output: Shortest path = 692
Path taken = 6 3 5 1 8 2
- In the 2nd test case there are 10 magic spots and 10 number of pathways which connects the spots.
The next 10 lines of input contains 3 numbers representing the names of start spot,
and destination spot, distance between them
for example, for the first magic spot
- starting spot is 1
- passing through spot is 5
- distance between 1 and 5 is 78
1
/ \
4 - 8 6 - 5
/ \ \ /
2 10 - 3
/
7
- For the user's input 6, 3, 2 representing starting, passing through,destination spots respectively there exits a shortest path to reach spot 2 from spot 6 passing through spot 3.
- The minimum distance travelled is 692
- Path followed is 6->3->5->1->8->2
- Two friends Carroll Shelby and Ken Miles are playing a game where they arrange all the toy cars in a row and run them in random directions.
- Each car has a certain superiority level associated with it and both max and sergio are aware of the superiority levels. They want to know the state of cars once they move them.
- We are given an array
carsof integers representing cars in a row. For each car, the absolute value represents its superiority, and the sign represents its direction (positive meaning right, negative meaning left). - Each car moves at the same speed. Find out the state of the cars after all collisions.
- If two cars meet, the less superior one will break. If both are of the same superiority, both will break. Two cars moving in the same direction will never meet.
Input: cars = [4,8,-2]
Output: [4,8]
Input: cars = [5,-5]
Output: []
Input: cars = [10,2,-5]
Output: [10]
Input: cars = [4,8,-2]
Output: [4,8]
- The car with superiority level 8 and -2 collide resulting in car with superiority level 8.
- The cars 4 and 8 never collide because they are moving in the same direction.
- Therefore, the ouptut is [4,8]
Resources (Spoiler)
- You are a diamond merchant in Dubai. You have
xunsold diamonds, and each diamondphas a purity levelmβ, and a minimum pricenβ. - You also have
zclients, and each clientjwants a diamond with a purity greater thankβ±Όand a price less than or equal torβ±Ό. - Each client can buy at most one diamond, and each diamond can have at most one buyer. What is the maximum number of diamonds you can sell?
Input:
z = 3, x = 3
kβ = 5, rβ = 110
kβ = 9, rβ = 500
kβ = 20, rβ = 400
mβ = 10, nβ = 100
mβ = 2, nβ = 200
mβ = 30, nβ = 300
Output: Maximum number of diamonds sold = 2
Input:
z = 2, x = 2
kβ = 3, rβ = 100
kβ = 5, rβ = 150
mβ = 4, nβ = 145
mβ = 2, nβ = 80
Output: Maximum number of diamonds sold = 2
In case 1:
- Client 0 will be interested in diamond 0 because it has more than kβ = 5 units of purity and costs less than rβ = 110 .
- Both of the other diamonds are outside of this client's price range.
- Client 1 will be interested in diamonds 0 and 2 , as both these diamonds have more than kβ = 9 units of purity and cost less than rβ = 500 .
- They will not be interested in the remaining diamonds because it's less pure.
- Client 2 will be interested in diamond 2 because it has more than kβ = 20 units of purity and costs less than rβ = 400 .
- They will not be interested in the other two diamonds because they are less pure.
- All three clients are interested in the same two houses, so you can sell at most two houses in the following scenarios:
- Client 0 buys diamond 0 and client 1 buys diamond 2.
- Client 1 buys diamond 0 and client 2 buys diamond 2.
- Client 0 buys diamond 0 and client 2 buys diamond 2 .
- Thus, we print the maximum number of diamond you can sell, 2, on a new line.
- Amy has her Math exam tomorrow and she has not prepared for it.
- There are
nchapters in her book andith chapter has chaptericoncepts. She hasxhours to prepare for the exam. She decides that she can studyynumber of concepts from the chapters in each hour. - If a chapter has less than
yconcepts, then she will cover all the concepts of that chapter and take a break for the rest of the hour. - Return a minimum integer
ysuch that she covers all the chapters of her Math book withinxhours.
Input: chapter = [3,6,7,11], x = 8
Output: 4
Input: chapter = [30,11,23,4,20], x = 5
Output: 30
She can study 4 concepts from her chapters per hour such that, she can cover all the concepts from the chapters within 8 hours.
- Pinky is a college student who works for her momβs online Bracelet store and sells amazing collections of bracelets on a daily basis.
- She takes a maximum number of
ndays for the bracelets to be delivered to the customers. - The
ith customer has orderedinumber of bracelets. - She prepares the bracelets according to the order in which she received the bookings. She schedules a maximum number of bracelets to be made and delivered in a day, such that she has sufficient time to manage her college work.
- Return the least number of bracelets that can be made in a day for them to be delivered in n days.
Input: number of bracelets = [3,2,2,4,1,4], n = 3
Output: 6
Input: number of bracelets = [1,2,3,1,1], n = 4
Output: 3
Pinky can make 6 bracelets and deliver them in a day such that she delivers all the orders within 3 days.
Day 1: 3, 2
Day 2: 2, 4
Day 3: 1, 4
-
Leo is a lion that escaped from the zoo, and
Xforest rangers are up for catching him. -
The rangers want to catch Leo no matter the cost, and Leo also wants to eliminate as many rangers as possible (preferably everyone) before getting caught (or before running away after eliminating everyone). Neither the rangers nor Leo will run away before accomplishing their goals.
-
Leo and the officers are on a one-dimensional grid with coordinates ranging from
β10ΒΉΒΊ to 10ΒΉΒΊ. Leo is initially standing at coordinateA, and theith ranger is initially at coordinateCi. The rangers and Leo then take turns to move, with the ranger team moving first. -
During their turn, rangers will have to move to an adjacent unoccupied cell one by one, in any order they want. Every ranger will have to move. At every moment of time, no two rangers can be in the same cell, and also no ranger can be in the same cell as Leo.
-
If the ranger is unable to move to an adjacent unoccupied cell, he is eliminated (and the cell he was in becomes unoccupied). Note that the ranger team will try to move to eliminate as few rangers as possible.
-
After the ranger team's turn, Leo also moves to an adjacent unoccupied cell, or gets caught if he cannot find any adjacent unoccupied cell.
-
The process then repeats until either Leo is caught, or all rangers are eliminated and Leo runs away.
-
You need to find out the maximum number of rangers that can be eliminated by Leo, and if Leo can run away or not.
Input:
T = 1, X = 2, A = 2
(C1 C2) = 1 4
Output:
1 -1
Input:
T = 1, X = 1, A=2
(C1 C2) = 1
Ouput:
1 1
For test case 1:
- Leo chooses to always move to the left (i.e. to the smaller coordinate); this forces the ranger at coordinate 1 to always move to the left, and eventually being
cornered and eliminated.
- However, the officer at coordinate 4 cannot be eliminated, and hence Chef will be caught at the end.
For test case 2:
Similarly, Leo chooses to always move to the left, and eventually eliminating the only ranger, thus running away at the end.
- Ram is an assistant manager in the bank. His boss, is very bossy and assigns him to tasks and asks him to complete them as soon as possible.
- This manager also has some parameters which are assigned to each and every task which he has to note. They are:
- The maximum number of tasks he can complete in a single go
- The time taken to complete the single task for that job
- The number of tasks each job can process
- And at last the manager asks Ram to calculate the minimum time needed to process a set of tasks for the given job. Ram did a course on data structures and using his knowledge on this subject he plans to complete this task in less time. Try helping Ram out and see if he can outwit his manager!
Input:
Task size = [3,2,5,7]
Processing time = [5,4,10,12]
Number of tasks = [10,6,10,5]
Output: The minimum time to process all the tasks is 20.
Input:
Task size = [4,3]
Processing time = [6,5]
Number of tasks = [8,8]
Output: The minimum time to process all the tasks is 15.
Task size = [4,3]
Processing time = [6,5]
Number of tasks = [8,8]
Queue 0 can process a maximum of 4 tasks in 6 minutes, and queue is 1 can process a maximum of 3 tasks in 5 minutes. Each queue has 8 tasks to process. The time required to perform the assigned tasks in the minimum possible time is calculated as follows:
For queue 0:
- At time = 0, a new batch of 4 tasks is initiated
- At time= 6, the first batch of tasks is processed and a new batch of 4 tasks is initiated.
- At time = 12, the second batch of tasks is processed. There are no more tasks left to process in this queue.
For queue 1:
- At time = 0, a new batch of 3 tasks is initiated.
- At time= 5, the first batch of tasks is processed and a new batch of 3 tasks is initiated.
- At time = 15, the third batch of tasks is processed. There are no more tasks left to process in this queue.
The minimum time to process all the tasks is 15.
- You are given an
n x nbinary matrix grid where1represents house and0represents wire. - A house is a 4-directionally connected group of
1's not connected to any other1's. There are exactly two houses in grid. - You may change
0's to1's to connect the two houses to form one house. - Return the smallest number of
0's you must flip to connect the two houses.
Input: grid = [[0,1],[1,0]]
Output: 1
Input: grid = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2
- Winter semester is about to begin. The previous semesterβs professors had already instructed the students that it is mandatory to take up a value added course in order to take up a subject course. There are a total of
numcourses to be taken and they are labelled from0tonum-1. Consider the arraycoursewherecourse[i] = [ai, bi]. - It is mandatory for a student to take up the value added course
aiin order to take up the subject coursebi.
Eg : the pair [3,8] says that one must take up the value added course 3 in order to take up the subject course 8.
- These mandatory courses can be indirect as well. Suppose, course
pis mandatory to take up courseqand courseqis mandatory to take up courser. Then, coursepis mandatory in order to take up courser. - Consider another array
answerwhereanswer[x] = [mx, nx]. You must answer if coursemxis mandatory in order to take up coursenxor not for thexthquery. - Return a boolean array
result, whereresult[x]is the answer to thexthquery.
Input: num = 2, course = [[1,0]], answer = [[0,1],[1,0]]
Output: [false,true]
Input: num = 3, course = [[1,2],[1,0],[2,0]], answer = [[1,0],[1,2]]
Output: [true,true]
Input: num = 2, course = [], answer = [[1,0],[0,1]]
Output: [false,false]
Input: num = 2, course = [[1,0]], answer = [[0,1],[1,0]]
Output: [false,true]
Explanation: The pair [1, 0] indicates that you have to take the value added course 1 before you can take the subject course 0.
Course 0 is not mandatory to take up course 1, but the opposite is true.
In your company there are n servers, numbered 0 to n-1, that are handling numerous requests at the same time. Each server has limitless processing power, but it can only handle one request at a time. The requests are routed to servers using the following algorithm:
- The
kth request arrives. Thatkth request is discarded if all servers are busy (not handled at all). - Assign the request to the
(k % n)th server if itβs available. - Otherwise, forward the request to the next server that is accessible. If the kth server is busy, for example, try routing the request to the
(k+1)th server, then the(k+2)th server, and so on.
You are given the arrival time of the requests and the load time(time taken to complete the request by the server). Your objective is to find the server which handles the most number of requests.
Input: n = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3]
Output: [1]
Input: n = 3, arrival = [1,2,3,4], load = [1,2,1,2]
Output: [0]
Input: n = 3, arrival = [1,2,3], load = [10,12,11]
Output: [0,1,2]
Input: n = 3, arrival = [1,2,3,4], load = [1,2,1,2]
Output: [0]
The first three requests are processed by the first three servers.
The third request has arrived. Because the server is accessible, it is handled by server 0.
Server 0 dealt with two requests, whereas servers 1 and 2 each dealt with one. As a result, server 0 is the busiest.
- You've been handed a
x*xbinary grid to work with. You can swap any two rows or columns with each other in each move. - Return the minimum number of moves to transform the board into a checkerboard. Return
-1if the task is impossible. - This is how a checkerboard is.
Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
Output: 2
Input: board = [[0,1],[1,0]]
Output: 0
Input: board = [[1,0],[1,0]]
Output: -1
Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
Output: 2
One potential sequence of moves is shown.
The first move swaps the first and second column.
The second move swaps the second and third row.
Check the above image for more context.
- Christian is a world renowned entrepreneur who has a lot of craze for maths. In order to exhibit his love for maths he decided to buy a land and design it in the form of an undirected simple graph with
Xvertices (numbered 1 throughX) andYedges (numbered 1 throughY). - For each valid
p, thepth edge connects verticesmβandnβ. Christian wants to show off his car and bike collection on the field and therefore wants to place his bikes and cars on the edges so that the graph would be perfectly balanced, which means that for each vertex, the number of bikes edges incident to it must be equal to the number of cars edges incident to it. - Obviously, Christian does not want to leave any edges blank, but he immediately realised that in such a case, it generally may be impossible to make the graph perfectly balanced, so instead he decided to display his helicopter collection on some of the edges, so that it is always possible to balance the graph.
- Since helicopters are the most expensive, Christianβs satisfaction with the graph will be greater when he uses fewer edges to display his helicopter collection.
- Can you help him choose what he has to display(bike,car or helicopter) on the edges so that he can show off his love for maths and his wealth in a perfectly balanced and satisfactory manner?
- Return an array, for each valid
p, thepth of these lines should contain the integer0if you want theith edge to be a helicopter,1if you want it to be a bike orβ1if you want it to be a car.
Input: X = 5, Y = 6
[mβ, nβ] = [[1, 2], [2, 3], [3, 1], [3, 4], [4, 5], [5, 3]]
Output: [-1, 1, 1, -1, 1, -1]
Input: X = 6, Y = 9
[mβ, nβ] = [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [3, 6], [4, 5], [5, 6]]
Output: [-1, 1, 0, 0, 1, -1, 0, 0, 0]
The graph can be perfectly balanced without using any helicopters on the edges.
Green colour - car on the edges.
Red colour - bike on the edges.
Thus, without using any helicopters on the edges the graph is perfectly balanced in this case.
- The National Ant Marathon Committee has decided to conduct this yearβs marathon. The committee has to decide the route that is cyclic and consists of 4 different roads.
- Their city has
Xintersections andYbidirectional roads.They want to hold it in all places throughout the city and make sure they cover a new route every day. - Two routes are said to be equal if their sets of component roads are equal.
- You need to determine the maximum number of days the marathon needs to be held such that every route travelled is different.
- Two arrays
AandBwhich define a bidirectional road connecting intersectionsAiandBi.
Input: X = 4, Y = 6
A B
1 2
2 3
3 4
4 1
1 3
2 4
Output: 3
Input: X = 3, Y = 4
A B
1 2
3 2
1 3
2 1
Output: 2
In case 1: There are 3 different cyclic routes that can be taken for the marathon.
1->2->3->4->1
1->3->2->4->1
1->2->4->3->1
Recall that each route is a set of intersections forming a cycle, so each unique route is the same regardless of which city on the route the ants start out at. Thus, we print 3 (the number of routes) as our answer.
- Lawrence is a delivery partner with grofers and due to the festive season his orders have increased and he is in a very dire situation. Please help Lawrence.
- Lawrence gets
Xorders. The orders are numbered from 1 toX. He gets orderiatRitime, and this order containsYinumber of groceries. Lawrence needs to deliver each of theseYigroceries beforeTitime and for each unit of groceries he cannot deliver before this deadline he needs to forfeitKiunit of his salary as penalty. - Given all of the orders, help Lawrence to minimize the amount of salary he will have to forfeit .
- Important Note: Lawrence can deliver at most one grocery at a unit time and for each grocery he needs exactly one unit of time to deliver. Also Lawrence can deliver a grocery instantly, when the grocery is available right next to the delivery address.
- If Lawrence wants to deliver a grocery at time
p, then the latest he can deliver that grocery is at time timep. In another words, for orderiLawrence can deliver the groceries at time unitsRi, Ri+1, Ri+2, ..., Ti-1. Please note that Lawrence cannot deliver groceries from orderiexactly at time unitTi.
Input: X=1
Rβ=1 Yβ=5 Tβ=6 Kβ=10
Output: 0
Input: X=2
Rβ=1 Yβ=5 Tβ=6 Kβ=10
Rβ=1 Yβ=5 Tβ=6 Kβ=10
Output: 50
Example 1: There is only 1 order and all of the groceries from this order can be served. So zero salary has to be forfeited.
Example 2: There are two orders and you cannot serve 5 groceries. You can select these 5 groceries from any order.
- Adhi and his friend Vishal decided to go camping in the forests of Ranthambore 5 years after their previous trip to the forests. However during the nights they can set up their tents only in the βresting areasβ designated by the government.
- The forest has
Xresting areas that they can set up their tents in. The resting areas are numbered from 1 toXand are connected withX-1roads. - Each road has its own length. It is known that between two resting areas there is exactly one* path that goes through the roads and resting areas such that no resting area appears in the path more than once. Roads do not intersect each other and it takes 0 time to pass through a resting area.
- During their last visit, Adhi and Vishal previously rested in resting areas
A1, A2, ..., AMso they will rest in one of these areas again. To make the camping trip more adventurous they do not agree on the resting area beforehand. Rather, Adhi will pick a random resting areaCfrom this list of resting areas and Vishal will independently pick a random resting areaJfrom this list of resting areas. Both random choices will be taken uniformly over the list of resting areas. - The day before the camping trip, Vishal was a little scared and he spoke with his brother about their plan and asked him to calculate the expected distance between resting areas that Adhi and Vishal randomly pick. Please remember that Adhiβs brother knows neither
CnorJ. Help him calculate this expected distance. - Return two integers
numeranddenom. These indicate the fraction numer/denom giving expected distance between the resting areas randomly chosen by Adhi and Vishal. This fraction should be reduced so that gcd(numer, denom) = 1 and denom β₯ 1.
Input: C=6 B=2
P=1 Q=3 R=1
P=2 Q=3 R=2
P=3 Q=4 R=3
P=4 Q=5 R=4
P=4 Q=6 R=5
A1=1 A2=5
Output: numer=4 denom=1
Input: C=6 B=6
P=1 Q=3 R=1
P=2 Q=3 R=2
P=3 Q=4 R=3
P=4 Q=5 R=4
P=4 Q=6 R=5
A1=1 A2=2 A3=3 A4=4 A5=5 A6=6
Output: numer=29 denom=6
| Nikhilesh S | Keerthana S | Harshitha | Pranav D | Nitya Samavedam | Nithish Kumar B | Madhumita R | Poujhit MU | Sahari Krithik | Vishnuvasan |
|---|---|---|---|---|---|---|---|---|---|
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
| π¨π§π | π | π | π | π | π | π | π | π | π |
Anyone who is passionate about coding and can dedicate a little time a day for the challenge for the next 31 days.
You don't need to submit it everyday. Just submit it once you're done with all 31 algorithms.
Not a problem. While coding every day is nice, we understand that other commitments might interfere with it. Plus its holiday season. So you don't have to solve one problem every day. Go at your own pace. One per day or 7 a week or even all 30 in a day.
Anything! New to GoLang? Best way to practice it. Wanna find out what all this hype about Python is? Use it! Any and all languages are welcomed. Maybe you could try using a different language for every problem as a mini-challenge?
If you are new to Git or GitHub, check out this out GitHub
Our code ninjas are hard at work preparing the rest of the problems. Don't worry, they'll be up soon.
We have a folder for each day of the month. Simply complete your code and move the file into that folder. Be sure to rename your file to the following format: language_username or language_username_problemname
Some examples:
python3_exampleUser.py
c_exampleUser.c
Please do not modify any existing files in the repository.
I forked the repository but some problems were added only after that. How do I access those problems?
Not to worry! Open your nearest terminal or command prompt and navigate over to your forked repository. Enter these commands:
git remote add upstream https://github.com/SVCE-ACM/A-December-of-Algorithms-2021.git
git fetch upstream
git merge upstream/mainIf you're curious, the commands simply add a new remote called upstream that is linked to this repository. Then it 'fetches' or retrieves the contents of the repository and attempts to merge it with your progress. Note that if you've already added the upstream repository, you don't need to re-add it in the future while fetching the newer questions.
This shouldn't happen unless you modify an existing file in the repository. There's a lot of potential troubleshooting that might be needed, but the simplest thing to do is to make a copy of your code outside the repository and then clone it once again. Now repeat the steps from the answer above. Merge it and then add your code. Now proceed as usual. :)
Open up an issue on this repository and we'll do our best to help you out.
