trafficstars

Welcome to A December of Algorithms (2020). 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.

What Do I Do?

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.

Index

December 1 - Sherlock's Quest
December 2 - The Convo!
December 3 - Meet and Greet!
December 4 - Spoiled Or Not
December 5 - The Grand Master
December 6 - The Task Master
December 7 - Temperature Screening
December 8 - Movie Night
December 9 - Isle of Dogs
December 10 - Restore IP Addresses
December 11 - JSQL
December 12 - Recruitment Drive
December 13 - Check Your Spelling Sara!
December 14 - Puddles and Potholes
December 15 - Help Max shop!
December 16 - Max's Party
December 17 - Pokemon
December 18 - Is this a valid new user
December 19 - War on Wakanda
December 20 - Show up people!
December 21 - Test of Accuracy
December 22 - Closest Servers
December 23 - The Rise of the Knight
December 24 - Minify the damage
December 25 - Trapping Rain Water
December 26 - Lal's Jewels
December 27 - Covid in Godric's Hollow
December 28 - Who's the Winner?
December 29 - Amusement Park
December 30 - Superman vs Zod
December 31 - Captain Vaxx
FAQ
Maintainers

Algorithms

December 1 - Sherlock's Quest

Problem Statement

It's the final quest of Sherlock Holmes. The Moriarty wants Sherlock dead and is hiding behind a door on the same floor. To make sure he gets killed, Moriarty has filled all the rooms except the one he is in with poisonous gas.
The door number behind which he is hiding is designed in such a way that the sum of the left half and right half of the square of the number is equal to the number and is also a multiple of 3.

Sample Input/Output

 Room: 45
 Status: Safe

 Room: 36
 Status: Not Safe

Explaination

 45 is a multiple of 3
 45^2 = 2025
 20 + 25 = 45

December 2 - The Convo!

Problem Statement

Two friends were talking over the phone. They suddenly started to play a puzzle using the keypad.
The keypad contains digits from 2-9 inclusive. Develop a small algorithm to return all the possible letter combinations that the number could represent.

Note

Only 2 character combinations are allowed.
First you should display the character corresponding to the first number and then display the character corresponding to the second number.

Sample Input/Output

Input: 32
Output: ["da","db","dc","ea","eb","ec","fa","fb","fc"]

Resources

Backtracking

December 3 - Meet and Greet!

Problem Statement

Sundar is an employee at Google. He comes to office at 9:00 and leaves office at 17:00.
One day he got a sudden message from a employee to schedule a metting for 1 hour. He, Can choose any time between his working hours. But, Sundar is a busy employee already had several meetings on that day.
Develop an algorithm to finds an interval time which is greater than meeting time (i.e) 1 hour. So, Sundar can attend his meeting accordingly.

Sample Input/Output

Input: ["0930", "1100"],["1200","1330"],["1530","1630"]
Output: ["1100","1200"],["1330","1530"]

Explanation

He comes to office by 9:00 the first meeting starts at 9:30 so he can't assign a meeting.
The first meeting overs at 10:00 and the next meeting starts at 12:00. Now, He has 1 hour gap. So, he can assign a meeting in between that.
Again he has interval of 2 hour between 13:30 to 15:30 so he can assign a meeting at that time.

Note

All times are calculated in 24 hours format.
The working hour and meeting time is constant

Resources

December 4 - Spoiled Or Not

Problem Statement

You are given with a list of manufacturing dates of each ice cream and also a list of days for the expiry of each ice cream from the date of manufacturing.
On a given date find the number of ice creams spoiled. You may assume that all the dates are in DD/MM/YYYY format.
If an Ice Cream expires on the given day then the ice cream is not spoiled. You may assume that all months have only 30 days.

Sample Input/Output

 Number of Ice Creams : 3	                
 Manufacture Dates : [10, 01, 2020],[13, 01, 2020],[20, 12, 2019]    
 Best Befor days : 20 13 20          
 Given Date : [28, 01, 2020] 	
 
 No of ice creams spoiled: 2

Explanation

Expiry Date of Ice cream 1 = [10, 01, 2020] + 20 days = [30, 01, 2020]	    
Expiry Date of Ice cream 2 = [13, 01, 2020] + 13 days = [26, 01, 2020]	    
Expiry Date of Ice cream 3 = [20, 12, 2019] + 20 days = [10, 01, 2020]	    

On the given date ([28, 01, 2020]) ice creams 2 & 3 has expired.

Optional Task

Try completing the problem in time complexity O(n/4).

Resources

December 5 - The Grand Master

Problem Statement

It was a dark and stormy night where an Oldman and his grandson were playing chess. The Oldman gave his grandson a problem, to check his knowledge and skills in chess.
He stated that, It was a square chessboard of A x B size, the position of Knight (C, D) and position of a target (E, F) is given.
Now the Grandson needs to find out the minimum steps a Knight will take to reach the target position.

Sample Input/Output

Dimension of Board : 6 6
Position of Knight : 1 1
Target Position :  4 5 

Minimum Steps : 3

Explanation

From the starting position of the Knight (1,1). The Knight can move to either (3,2) or (2,3). We choose (3,2).
From (3,2) the Knight can move to (5,1), (1,3), (2,4), (4,4), (5,3), (1,1). We choose (5,3).
From (5,3) the Knight moves to (4,5).
The Minimum steps required is 3.

Resources

December 6 - The Task Master

Problem Statement

Tim has lot of tasks to do but there are certain tasks which he must finish before doing others tasks and he wants to know the order in which he has to perform these tasks, for that he needs your help cause you are the task master.
Tim gives you a directed graph without any cycles, represented by a matrix where each index of the matrix represents a task. For example index 0 is task A, 1 is task B, 2 is task C and so on.
Each task will have an array of tasks which can be performed only after performing the current task (the character represented by the index is the current task).
Implement a function findCompletionOrderOfTasks(list*) that finds the order of completion of the tasks.

Sample Input/Output

findCompletionOrderOfTasks( [ ['B','C'], [], ['D'], [] ])

There are three possible solutions for the given input print any one of them.

A C D B
A C B D
A B C D

Explanation

The task A is not depended on any other tasks so it should be finished first.
Now there are two options either you can do task B or C as they depend only on task A which is already done.
If you finish task B after A, then you have to finish task C and then D because task D depends on C.
If you finish task C after A, then you have two options you can finish task B and then D or D and then B.

Resources

December 7 - Temperature Screening

Problem Statement

Due to strict quarantine, the Railways have included a queue to check the temperature of the passengers before boarding the train.
It takes 2 minutes for a ticket to be generated in ticket counter A, while it takes only 1 minute for a ticket to be generated in ticket counter B.
The queue for temperature check up is right next to ticket counter B, where the passengers from both the queues have to wait for their turn. Develop a small algorithm that specifies the position of the passengers in the temperature check up queue.

Sample Input/Output

 Counter A: Aditi  Gautham  Ravi  Shreya
 Counter B: Karthik  Neha  Suman  Prakash

Temperature Screening: Karthik  Neha  Aditi  Suman  Prakash  Gautham  Ravi  Shreya

Explanation

Since counter B is closer to the temperature screening queue, only after 2 people from counter B move to that queue, one person from counter A joins them.

Resources

December 8 - Movie Night

Problem Statement

A theatre has N x M seats, some of them are not in usable condition. Due to the pandemic, social distancing needs to be maintained, restricting only one person per row and column.
How can you maximise the tickets sold for this theatre?
Represent Usable condition as U, Non-usable condition as N.

Sample Input/Output

Input : 2
        3 3
        UUU
        UUU
        UUU
        
Output : 3

Input : 3 3
        UUU
        UNN
        UNN
        
Output: 2

Explanation

Case 1: People can sit on seats (1,1) (2,2) and (3,3)
Case 2: People can sit on seats (1,2) and (2,1)

Resources

Maximum Flow

December 9 - Isle of Dogs

Problem Statement

An outbreak of dog flu has spread through the city of Megasaki, Japan, and Mayor Kobayashi has demanded all dogs to be sent to Trash Islands. A young boy named Atari sets out to find his lost dog in the Trash Islands. But first, Atari needs help knowing how many islands are there to refuel his makeshift motorboat. Given an M x N 2D grid map of * (land) and _ (water), return the number of islands.
An island is always surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Sample Input/Output

Example 1:

Input: grid = [
  ["*","*","*","*","_"],
  ["*","*","_","*","_"],
  ["*","*","_","_","_"],
  ["_","_","_","_","_"]
]
Output: 1

Example 2:

Input: grid = [
  ["*","*","_","_","_"],
  ["*","*","_","_","_"],
  ["_","_","*","_","_"],
  ["_","_","_","*","*"]
]
Output: 3

Resources (Spoiler)

December 10 - Restore IP Addresses

Problem Statement

It's midnight, Gilfoyle received a call from Dinesh that he lost Pied Piper's entire network table after trying to "download RAM from the Internet". All Dinesh gives Gilfoyle is a string corrupted_log containing only digits, help Gilfoyle return all possible valid IPv4 addresses that can be obtained from corrupted_log. They can be returned in any order.
A valid IPv4 address must be in the form of xxx.xxx.xxx.xxx, where xxx is a number from 0-255 and cannot have leading zeros. For example, 0.2.1.132 and 192.168.1.1 are valid IPv4 addresses and 1.101.255.132, 192.168.4.312 and [email protected] are invalid IPv4 addresses.

Sample Input/Output

Example 1

Input: corrupted_log = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]

Example 2

Input: corrupted_log = "1111"
Output: ["1.1.1.1"]

Example 3

Input: corrupted_log = "0000"
Output: ["0.0.0.0"]

Example 4

Input: corrupted_log = "010010"
Output: ["0.10.0.10","0.100.1.0"]

Example 5

Input: corrupted_log = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

December 11 - JSQL

Problem Statement

Given a JSON file with table information, return the SQL statement to create the table and insert all the records into the table.
- You need not worry about key constraints.

Sample Input/Output

  Input:
  {
    "table name": "my_table",
          "headers": {
      "1": {
        "column name": "id",
        "data type": "integer"
      },
      "2": {
        "column name": "name",
        "data type": "varchar(30)"
      }, 
    },
    "records": {   
      "1": [1, "Josh"],
      "2": [2, "Mike"],
      "3": [3, "Tom"]
    }
  }

  Output:
    create table my_table (id integer, name varchar(30));
    insert into my_table values (1, "Josh");
    insert into my_table values (2, "Mike");
    insert into my_table values (3, "Tom");

Explanation

From the JSON file, we need to create a table my_table with 2 columns id', and age`.

Click here for more sample input

Resources

December 12 - Recruitment Drive

Problem Statement

Given a file of candidates selection based on GPA and work experience predict whether the new candidate will be selected or not
The file will have the following values GPA : 0-5 Work experience : Number in years Selection Status : 0-not selected 1-selected
Prediction calculation (where X₁ is GPA and X₂ is work experience):

$\large \frac{1}{1 + e^{-(b_{0} + b_{1}x_{1} + b_{2}x_{2})}}$

For each test case (Stochastic gradient) b₀,b₁,b₂ are initially zero and is updated using:

$\large b = b + 0.3 \times (y - prediction) \times prediction \times (1 - prediction) \times x$

- Output whether the candidate will be selected or not?

Input Format

The first line contains the address of the csv file. The csv file can be fetched from here
The second line consists of two values gpa and work_experience

Output Format

Print 'Selected' or 'Not selected' based on the prediction

Sample Input/Output

gpa,work_experience,selection_status
4,3,1
3.9,4,1
3.3,3,0
3.7,5,1
3.9,4,0
3.7,6,1
2.3,1,0
3.3,4,1
3.3,5,1
1.7,1,0

Input: 3.7 6
Output: Selected

Resources

Logistic Regression ML

December 13 - Check Your Spelling Sara!

Problem Statement

Sara was writing an essay on pollution due to urbanization. Due to her poor writing skills she made a lot of errors in her essay.
One character in the string is incorrectly replaced by another one. Example: She enters Equalety instead Equality.
Write a program to help her finish the essay by correcting the spelling mistakes.
The program should accept a list of correct words and the misspelt word as the input. Display the correct word as the output.

Sample Input And Output

Input:
Correct Words: [Mango, Guitar, Automobile, Astonished, Unique]
Misspelt word: Guiter

Output:
Guitar

Input:
Correct Words: [December, Of, Algorithms]
Misspelt word: Algorythms

Output:
Algorithms

Resources

Applications of NLP

December 14 - Puddles and Potholes

Problem Statement

Due to improper road maintenance, some roads in ABC Nagar were broken and had potholes. The new delivery guy at Pizza House does not know about this situation.
To make things worse, the heavy rain last night has filled up these potholes and, there's no difference between a puddle of water and a pothole filled with water.
Given a map where the potholes are marked as 0 and the road marked as 1, help the delivery guy deliver his pizzas safely on time by choosing the best route for him.
The top left corner and the bottom right corner must be considered as Pizza House and the destination respectively.

Sample Input And Output

 Enter the map details:
  1 0 0 0
  1 1 0 1
  0 1 0 0
  1 1 1 1

Optimised Route:
  1 0 0 0
  1 1 0 0
  0 1 0 0
  0 1 1 1

Explanation

The given map details can be interpreted as given:
The blocks for the optimised route are mentioned as 1’s while the remaining blocks are mentioned as 0’s.

Resources

December 15 - Help Max shop!

Problem Statement

Max is deeply fond of fashion and he enters H&M in search of shirts and trousers.
The shirts and trousers are arranged in a single line (in disorderly fashion). Max wants to pick maxiumum number of continuous garments such that number of shirts and trousers are equal.
Can you help Max to find maximum number of garments he can pick given string gives arrangements of garments, s denotes shirts and t denotes trousers? Return a single line denoting maximum number of garments Max can pick.

Sample Input And Output

ststt
4

tsssst
2

tstts
4

Explanation

He can pick from index 0 to 3 (assuming indexing starts from 0)
He can pick from index 0 to 1 or from 4 to 5 (assuming indexing starts from 0)
He can pick from index 1 to 4 (assuming indexing starts from 0)

Resources

Hashing

December 16 - Max's Party

Problem Statement

The neighbourhood of greenwood want to throw an appreciation party for their beloved mailman max. They want to get word around, but dont want to spoil the suprise for max. So they decide to encrypt their letter.
They decide to use ROT encryption technique, which is a simple character substitution based on a shift/rotation of N letters in an alphabet to circulate their messages. Help the neighbourhood encrypt a string message with a Key using ROT encryption technique as demonstrated below.

Sample Input And Output

Message: "Hihow" 
Key: LLRHR

Encrypted Message: "nvGhg"

Step-wise Explanation

L: Hihow -> Ghgnv
L: Ghgnv -> Fgfmu
R: Fgfmu -> uFgfm
H: uFgfm -> vGhgn
R: vGhgn -> nvGhg
Therefore, the Derived Encrypted message for Hihow using the key LLRHR is nvGhg.
Key size should be greater than one and contains only L, H and R where,
- L stands for -1
- H stands for +1
- R stands for Rotate

Resources

ROT Cipher

December 17 - Pokemon

Problem Statement

A Pokemon battle between two teams (say A and B) is about to take place. Each teams consist of Pokemon from 1 to n. Each Pokemon has a power score.
A Pokemon can win the battle only if its power score is strictly greater than his opponents power score. Coach of team A is yet to arrive.
Team A needs your help. Come up with the maximum number of matches that team A can win if the fight the battle in a optimal manner if a Pokemon can only fight in one battle.

Sample Input/Output

Example 1

  No of pokemons: 4
  Team A power score: [7, 10, 3, 5]
  Team B power score: [4, 12, 2, 6]

  Output: 3

Explanation

Team A can win a maximum of 3 battles if they fight in the below order:
A1 fights with B4
A3 fights with B3
A4 fights with B1

Example 2

  No of pokemons: 5
  Team A power score: [4, 6, 7, 11, 8]
  Team B power score: [2, 5, 6, 13, 3]

  Output: 4

Resources

December 18 - Is this a valid new user?

Problem Statement

During a hackathon, your friend Shyam is trying to add a user authentication feature.
He is asking you to implement an algorithm to validate and check the availability for a given username.
The rules for username validation are
1. It can contain characters a-z or A-Z.
2. It can contain numbers 0-9.
3. Special characters like period (.) underscore(_) or dash (-) is allowed, other special characters are not allowed.
4. It should not contain any whitespace characters.
5. The length of the username should not exceed 20.
Fetch the data from the fake users API to check whether the given username is available or not.

Sample Input/Output

Example 1

Input: Peter_Smith-24
Output: The username is valid and available.

Example 2

Input: Leopoldo_Corkery
Output: The username is valid but not available.

Example 3

Input: john $1-Samuel
Output: The username is not valid.

Resources

December 19 - War on Wakanda

Problem Statement

Thanos has declared war in Wakanda. The brave soldiers of Wakanda have been defending their country against attacks for a long time. There is a shortage of food amongst the citizens. The governor of Wakanda has ordered the army to drop food crates via helicopters.
Each helipad in Wakanda is located at the nodes of a Generic Tree. Due to constant attacks from Thanos, the dispatched helicopter cannot stay over civilian sky for long or it will be shot down by the enemy. The pilot has decided to cover the entire Helipad Tree with the least number of landings. Each Helipad node can cover the node connected to it by one edge.
If the number of landings exceed a certain number, the helicopter will be shot down by Thanos.
Since it is a high pressure situation, you have to help the pilot figure out the minimum number of times he needs to land his helicopter in order to cover the entire Helipad Tree without being shot and complete its mission (if possible).

Input Format

We need to input two things- Tree nodes and maximum allowed landings.
The first line of input contains data of the nodes of the tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.
Since data of each node is irrelevant, it will be taken as 1, representing that the node exists.
Second line of each test case will contain an integer K representing the maximum allowed landings.

Output Format

Print the minimum number of landings, and if the mission was Successful/Unsuccesful

Sample Input/Output

Input:
1 3 1 1 1 2 1 1 0 0 0 0
3

Output:
2 Mission Successful

Explanation

For the given input the tree formed is given below, which can be covered with minimum 2 landings, which is less than the maximum allowed landings.

Resources

Generic Trees

December 20 - Show up people!

Problem Statement

Given a positive integer n, return the number of all possible attendance records with length n, which will be regarded as acceptable The answer may be large, return it after mod 10^9 + 7.
A student attendance record is a string that only contains the following three characters:
- A : Absent.
- L : Late.
- P : Present.
A record is regarded as acceptable if it doesn't contain more than one A (absent) or more than two continuous L (late).

Sample Input/Output

Input: n = 2
Output: 8

Explanation

There are 8 records with length 2 will be regarded as acceptable:
PP , AP, PA, LP, PL, AL, LA, LL
Only AA won't be regarded as acceptable owing to more than one absent times.

Resources (Spoilers)

Dynamic Programming

December 21 - Test of Accuracy

Problem Statement

For the final test of accuracy in a shooting range, the players have to hit maximum number of targets using a single bullet.
The targets are placed at random positions with varying lengths.
The input consists of the left most coordinate (X,Y) of the target and the length L of the target.
Find the maximum number of targets that can be shot by the player from (0,0).

Sample Input And Output

Enter the no. of targets: 5
30 10 10
10 20 20
20 50 30
40 20 10
20 30 10

Targets shot in a single bullet: 3

Explanation

There is a way to shoot in such a way that it hits target number 2,3 and 5, hitting a maximum of 3 targets.

Resources

December 22 - Closest Servers

Problem Statement

George's company is working on a contract with a leading Cloud Service provider. They have to choose k locations for setting up cloud servers from n cities.
The locations should be chosen in such a way that the maximum distance of a city to a cloud server is minimum.

Sample I/O

  Input: distances = [
    [0, 4, 8,  5],
    [4, 0, 10, 7],
    [8, 10, 0, 9],
    [5, 7, 9,  0]
  ]

  Output: 0 2

Explanation

distances[i][j] is the distance between city i and city j.
The maximum distance of a city from a cloud server is minimized when the two servers are placed at cities 0 and 2 with the distance being 5 units.
The distance of a city from a center is the distance between that city and its closest center.

December 23 - The Rise of the Knight

Problem Statement

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. He dies immediately if his health point drops to 0.
Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0s) or contain magic orbs that increase the knight's health (positive integers). To reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.
Write a function to determine the knight's minimum initial health so that he can rescue the princess.
Note that the knight's life has no upper bound, and any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Sample Input/Output

  Input:
	 -2(K)	-3	3
	 -5	-10	1
	 10	 30    -5(P)

  Output: 7

Explanation

Input is the dungeon where K represents the Knight and P represents the Princess.
Output 7 indicates that the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

December 24 - Minify the damage

Problem Statement

You are in a game where you have to fight some enemies. You are given an array of integers where each index represents an enemy and the value at each index represents the damage per second that the enemy can cause.
You have k number of rounds and you have to fight with equal number of enemies in each round such that
- There are no two enemies with equal damage per second present in the same round.
- The sum of the difference between the maximum and minimum damage per second caused in each round is minimum.
Return the minimum sum, or return -1 if it is not possible. Note that the array length is divisible by k.

Sample Input/Output

Example 1:

Input: [1,2,1,4], k = 2
Output: 4

Explanation:

The optimal distribution of enemies is [1,2] and [1,4].
The sum is (2-1) + (4-1) = 4.
Note that [1,1] and [2,4] would result in a smaller sum, but in the first round there are 2 enemies with the same damage per second which is not allowed.

Example 2:

Input: [6,3,8,1,3,1,2,2], k = 4
Output: 6

Explanation:

The optimal distribution of enemies is [1,2], [2,3], [6,8], and [1,3].
The sum is (2-1) + (3-2) + (8-6) + (3-1) = 6.

Example 3:

Input: [5,3,3,6,3,3], k = 3
Output: -1

Explanation:

It is impossible to distribute the enemies for 3 rounds where no two enemies have equal damage per second in the same round.

December 25 - Trapping Rain Water

Problem Statement

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Sample Input/Output

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Explanation: The above elevation map (black section) is represented by array [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

December 26 - Lal's Jewels

Problem Statement

Lal is a jwellery dealer who buys long chains of Diamonds, Rubies, and Emerlads. He cuts them into small chains and sells them for a profit.
He gets very nice bonus if, the chain has a palindromic order of stones.
The price is determined as follows:
- A single diamond D costs $500
- A single ruby R costs $250
- A single emerald E costs $100
- Price is multiplied n times, for palindromic chains, where n is the length of the chain.
Given the whole chain, find the maximum profit lal can make, cutting out a palindromic chain.

Sample Input/Output

Example 1

Chain: "RDEREDRRRD"
Output: $7250

Explanation:

The longest palindromic chain is "RDEREDR", the prices are added and 7 is multiplied as a bonus.

Example 2

Chain: "DERRREDERREDEREDR"
Output: $24,000

Explanation:

The longest palindromic chain is "REDERREDER", the prices are added and 10 is multiplied as a bonus.

Resources (Spoiler)

December 27 - Covid in Godric's Hollow

Problem Statement

There has been a outbreak of covid 19 at Godric's Hallow. Scienctis need to find out if the outbreak is from a single source or a multiple sources. If it is from multiple sources, then they have to issue lockdown orders for the village.
Coordinates for infected and non infected households are provided. If you can from a circle with only the infected houses and no healthy households, we can conclude that the source is singular.
If the infected circle contains healthy households, we can conlude that the outbreak is from multiple sources and order a lockdown.
The first line of the input contains n, number of households followed by the coordinates (x,y) of the houses and its infected status Y/N. Display if a lockdown is required or not.

Sample Input/Output

Example 1

Input:
7
0  0   Y
1  0   Y
0  1   Y
4  4   N
4  -4   N
-4  4   N
-4  -4  N

Output: No lockdown required

Example 2

Input:
7
0  0   Y
1  1   N
2  0   Y
0  2   Y
4  4   N
4  -4   N
-4  4   N
-4  -4  N

Output: Lockdown required

Resources (Spoiler)

December 28 - Who's the Winner?

Problem Statement

Koushik and Mahesh decided to have a race with each other from point A to point B. The map is an n x m matrix which specifies a path as . and an obstacle as x.
Since the race was being conducted in an area which was familiar to Koushik, he knew some k number of secret passages, at some coordinates (x,y).
To make the race fair, Mahesh had a headstart of 3 minutes.
To move from one point to another it takes 1 minute for both of them.
Point A is the top left point of the map and Point B is the bottom right point of the map.

Input and Output Format

The first line of the input must consist of n,m and k.
The successive n lines must have the map of the area along with the obstacles.
The next k lines must have the coordinates of the secret passage (x,y).
The output should be the name of the winner.

Sample Input/Output

Example 1:

Input: 5 5 2
       . x . . .
       . x . x .
       . . . x .
       x . . x . 
       . . . x .
       3 0
       4 3
Output: Koushik

Explanation:

Using the secret passage, Koushik takes 8 minutes to reach point B. Even if Mahesh has a headstart of 3 minutes, the total time taken by Koushik is 11 minutes.
Koushik takes 12 minutes to reach point B without the help of the secret passages.

Example 2:

Input: 4 4 1
       . . . x
       x x . . 
       . x . x
       x x . .
       1 1

Output: Mahesh

Explanation:

Even though the secret passage is used,for the shortest path it takes 6 minutes for both of them to reach Point B from Point A. Since, Mahesh has a headstart, he wins the race.

December 29 - Amusement Park

Problem Statement

The Christmas holidays have begun! So Chris and Kate have decided to enjoy their time in an amusement park.
The park is represented as a matrix a with n lines and m columns and a[i][j] represents the time spent in the ride in ith row and jth column.
Chris starts with the ride located at line 1 and column 1 and needs to finish with the ride a[n][m]. After finishing ride a[i][j], he can go to ride a[i + 1][j] or a[i][j + 1].
Similarly, Kate starts with ride a[n][1] and she needs to finish with ride a[1][m]. After finishing the ride from cell a[i][j], she goes to either a[i][j + 1] or a[i - 1][j].
There is one additional condition - that is they have to meet in exactly one ride of the park. At that cell, none of them will enjoy the ride but have a quick chat and then both of them will move to the next ride.
Plan the ride map for Chris and Kate such that they enjoy maximum time in the amusement park. Note, that each ride has different speeds, so the number of rides that they use to reach the final location may differ.

Input Format

The first line of the input contains two integers n and m (3 ≤ n, m ≤ 1000). Each of the next n lines contains m integers: j-th number from i-th line denotes element a[i][j] (0 ≤ a[i][j] ≤ 10 ).

Output Format

The output contains a single number — the maximum time spent.

Sample Input/Output

Input:
3 3
100 100 100
100 1 100
100 100 100


Output: 800

Explanation

Chris will choose exercises a[1][1] → a[1][2] → a[2][2] → a[3][2] → a[3][3]. Kate will choose exercises a[3][1] → a[2][1] → a[2][2] → a[2][3] → a[1][3].

December 30 - Superman vs Zod

Problem Statement

There is a fight between Superman vs Zod. Superman is having a hard time in the fight and is about to die. He somehow manages to contact other Supermans for help.
However, the Supermans are spread across several galaxies and therefore have different time availabilities.
Help Superman find the maximum number of Supermans available in the same hour!

Input

The first line contains the integer n, the number of galaxies (1 ≤ n ≤ 105).
On each of the next n lines, there will be two space-separated integers, a and b (0 ≤ a<b ≤ 24).
This means that the Supermans of this galaxy are available from the beginning of the a-th hour to the beginning of the b-th hour.

Output

Print the maximum number of Supermans available in any timeslot of one hour.

Sample I/O

Output: 3

Explanation

The timeslots in which 3 Supermans are available are: 9:00 - 12:00, 15:00 - 16:00, and 16:00 - 18:00.
No one-hour timeslot has more than 3 Supermans available. Therefore, the answer is 3

December 31 - Captain Vaxx

Problem Statement

Captain Vaxx is bringing a shipment of vaccines to Westeros by plane. The citizens want to get there vaccinations sorted as soon as possible so that they can back to fighting for the throne and try to make ammends for the season 9 disaster.
Problem is Captain Vaxx is lost over Westeros and doesn't know where to land. Help him find the airport by giving him directions over radio to the nearest airport he can safely land.
Given the coordinates of his postion and the airports nearby with their runway length, give him directions to safely land at the airport. Note, the only instructions you can give are Straight, Left and Right. With each command he moves unit length in the graph
The input is given as follows:
- The first line consists of the plane's coordinates followed by its required runway length.
- The next line contains the contains the coordinates of the airports and its runway length.
Output the directions to the airport.

Sample Input And Output

Straight Straight Right Straight Straight (Or any other valid permutation)

Explanation

The airport with the coordinates -2,1 maybe the closest airport, but 2,2 is the closest airport with the required landing length.

Maintainers

Krishnakanth	Mahalakshumi	Dhiraj	Aravind	Tarun	Ashik	Harshini	Ganesh	Sandhya	Shruti	Nikhilesh

:hammer::construction::pencil:	:hammer::construction:	:warning::pencil:	:pencil:	:pencil:	:pencil:	:pencil:	:pencil:	:pencil:	:pencil:	:pencil:

FAQ

Who can join the Challenge?

Anyone who is passionate about coding and can dedicate a little time a day for the challenge for the next 31 days.

When should I submit the pull request?

You don't need to submit it everyday. Just submit it once you're done with all 31 algorithms.

What if I'm not able to code every day?

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.

What language should I use to code?

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?

Fork? Pull request? What is all that? I don't know how to use GitHub!

If you are new to Git or GitHub, check out this small tutorial from our team and GitHub

Where are the rest of the problems?

Our code ninjas are hard at work preparing the rest of the problems. Don't worry, they'll be up soon.

How should I complete these programs?

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-2020.git
git fetch upstream
git merge upstream/main

If 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.

I received a merge error. What do I do?

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. :)

I'm facing difficulties with/need help understanding a particular question.

Open up an issue on this repository and we'll do our best to help you out.

[Back to Top]

wave

A-December-of-Algorithms-2020 A-December-of-Algorithms-2020 copied to clipboard

Metadata

What Do I Do?

Index

Algorithms

December 1 - Sherlock's Quest

Problem Statement

Sample Input/Output

Explaination

December 2 - The Convo!

Problem Statement

Note

Sample Input/Output

Resources

December 3 - Meet and Greet!

Problem Statement

Sample Input/Output

Explanation

Note

Resources

December 4 - Spoiled Or Not

Problem Statement

Sample Input/Output

Explanation

Optional Task

Resources

December 5 - The Grand Master

Problem Statement

Sample Input/Output

Explanation

Resources

December 6 - The Task Master

Problem Statement

Sample Input/Output

Explanation

Resources

December 7 - Temperature Screening

Problem Statement

Sample Input/Output

Explanation

Resources

December 8 - Movie Night

Problem Statement

Sample Input/Output

Explanation

Resources

December 9 - Isle of Dogs

Problem Statement

Sample Input/Output

Example 1:

Example 2:

December 10 - Restore IP Addresses

Problem Statement

Sample Input/Output

Example 1

Example 2

Example 3

Example 4

Example 5

December 11 - JSQL

Problem Statement

Sample Input/Output

Explanation

Resources

December 12 - Recruitment Drive

Problem Statement

Input Format

Output Format

Sample Input/Output

Resources

December 13 - Check Your Spelling Sara!

Problem Statement

Sample Input And Output

Resources

December 14 - Puddles and Potholes

Problem Statement

Sample Input And Output

Explanation

Resources

December 15 - Help Max shop!

A-December-of-Algorithms-2020
A-December-of-Algorithms-2020 copied to clipboard