ROUND 1 (DSA )
Problem 1
https://cses.fi/problemset/task/1194

Q) You and some monsters are in a labyrinth.
When taking a step to some direction in the labyrinth,
each monster may simultaneously take one as well.
Your goal is to reach one of the boundary squares without ever sharing a square with a monster.
Your task is to find out if your goal is possible, and if it is, print a path that you can follow.
Your plan has to work in any situation; even if the monsters know your path beforehand.
Input
The first input line has two integers n and m: the height and width of the map.
After this there are n lines of m characters describing the map.
Each character is . (floor), # (wall), A (start), or M (monster). There is exactly one A in the input.
Output
First print "YES" if your goal is possible, and "NO" otherwise.
If your goal is possible, also print an example of a valid path (the length of the path and its description using characters D, U, L, and R). You can print any path, as long as its length is at most n*m steps.
Constraints
• 1≤n,m≤1000
Example
Input:
5 8
########
#M..A..#
#.#.M#.#
#M#..#..
#.######
Output:
YES
5
RRDDR

SOLUTION
• Intuition : Use BFS for each monster, Flood Graph, Maintain Count of min steps any Monster will reach every cell
• Use BFS for person from start position, untill he reaches Edge condition.

L11 - MONSTERS | CSES PROBLEMSET SOLUTION | BFS ALGORITHM GRAPH THEORY

Problem 2
Q) Your task is to count for k=1,2,…,n the number of ways two knights can be placed on a k×k chessboard so that they do not attack each other.
Input
The only input line contains an integer n.
Output
Print n integers: the results.
Constraints
• 1≤n≤10000
Example
Input:
8
Output:
0
6
28
96
252
550
1056
1848

SOLUTION:

Intuition:
Total Ways - No of ways knights attack each other
Total Ways to place 2 Knights
• TotalWays = (N * N) * ( N*N - 1 ) / 2
• Divide by 2 because to remove duplicate such as
○ X _ X
○ X _ X

Every attack needs 23 matrix or a 32 matrix.
• Count total No of 23 matrices that can fit in NN board
( n - 2 ) * ( n - 1 )
• Count total No of 32 matrices that can fit in NN board
( n - 1 ) * ( n - 2 )
• TotalSubMatrices = 2 * (n-1) * (n-2)

Every (23 matrix or a 32 matrix) can have 2 attacks
K_ _
_ _K
OR
_ _ K
K _ _

Thus
TotalAttacks = 2 * TotalSubMatrices = 2 * 2 (n-1) * (n-2)

Finally
TotalNonAttackWays = TotalWays - TotalAttacks
= (N * N) * ( N*N - 1 ) / 2 - 2 * 2 (n-1) * (n-2)