I have written about my participation in Facebook hacker cup 2021 in a medium blog post.
https://shadek07.medium.com/facebook-hacker-cup-2021-experience-519f594bec7e
bfs
TOPCODER SRM 800 DIV2 MEDIUM (750 points)
Problem description here PoisonedSwamp
You should definitely know that this is a graph search problem. You can apply either DFS or BFS. However, the main challenge is to define the state meaning the vertex/node of this graph search problem. One key observation is that, you have to take poison count into consideration while you are visiting vertices/states.
So basically 3 parameters define a state: row number(x), column number(y), poison count acquired so far after stepping into cell(x,y) since the traversal started from cell(0,0). Another thing to note that, we don’t need to take care of poison count for more than 10 because the traveler is gonna die if he acquires >= 10 poisons.
I have implemented this using queue, in fact priority queue (it is not necessary as total state space is not so high). It is possible to solve this problem by a recursive dfs too.
My code during contest: https://community.topcoder.com/stat?c=problem_solution&rm=335435&rd=18497&pm=16768&cr=23058599
Codechef July’16 long challenge
1. Andrash and Stipendium (EGRANDR) [Problem link]
Simulate the problem description. Output is “No” if the student has failed in at least one subject or hasn’t got full score in at least one subject or the subject average is below 4. For all other cases, output is “Yes”.
Code
2. Chefland and Electricity (CHEFELEC) [Problem link]
Three possible cases to consider-
♦ string array starts with one or more 0’s (i.e 00001…)
All leftmost 0’s will be connected to the leftmost 1. Total length of wire needed in this case is the coordinate difference between first 0 with leftmost 1.
♦ string array ends with one or more 0’s (i.e ….10000)
All rightmost 0’s will be connected to the rightmost 1. Total length of wire needed in this case is the coordinate difference between last 0 with rightmost 1.
♦ string array contains some groups of 0’s surrounded by two 1’s in both side (i.e …10001…101..1001..)
These 0’s will be connected to either immediate left side 1 or immediate right side 1. More specifically, 0’s will be divided in at most two parts. Partition will be made in a position where we get minimum wire length. Left part of the group of 0’s connects with left 1 and right part of the group of 0’s connects with right 1. It is also possible that whole group of 0’s connects with either left 1 or right 1.
Code
3. Chef and Tetris (CHEFTET) [Problem link]
I solved this problem by backtracking with pruning.
What is the probable list of integers from which we get maximum integer such that all Ai‘s can be made equal to one of these integers? The list is quite small- {A1, A1+B1, A1+B2, A1+B1+B2}
Code
4. Chef and Robots Competition (CHEFARC) [Problem link]
This is a problem of finding min distance in 2D grid. I used BFS to find minimum number of moves needed to reach every grid cell for two robots separately from their initial positions. Now consider a particular grid cell (i,j). If 1st robot reaches this cell in x moves and 2nd robot reaches this cell in y moves, then minimum number of moves needed for both robots to be at cell (i,j) is P(i,j) = MAX(x,y). We need to find minimum from all P(i,j) ‘s [1 ≤ i ≤ N, 1 ≤ j ≤ M]
Code
SRM 664 (div2 medium)
Problem description here.
Problem summary
You are given three piles of stones each containing A, B and C (1 ≤ A,B,C ≤ 500) stones respectively. In a single operation, you can choose any two piles that have unequal number of stones (X,Y with X < Y). Then you have to change Y by Y-X and change X by 2*X. After zero or more operations, is it possible to have equal number of stones in each pile?
Topcoder SRM 620 div2 500
You are given four integers a,b,c,d where 1 ≤ a,b,c,d ≤ 1000. Consider (a,b) as a pair. By using zero or more steps is it possible to get (c,d)?
From (x,y) you can either jump to (x+y,y) or (x,x+y) which is a single step.
Idea 1:
By applying BFS with queue you can solve this. Each state in queue is a pair of integers. Initial state is (a,b) that is given in the input. If anytime you can reach (c,d) which is given in the input, return “Able to generate”. Otherwise “Not able to generate”. rumman_sust has solved this problem in this way here.
Idea 2:
If we start from (c,d) and try to go back to (a,b) size of code becomes smaller with some intuition.
In pair (x,y) both x,y are positive according to input. From (x,y) if you jump to (x+y,y) then x+y will never be equal to y. Again From (x,y) if you jump to (x,x+y) then x+y will never be equal to x. So you can handle the trivial cases in the following way:
if(a == c && b ==d) return "Able to generate"; if(c == d) return "Not able to generate";
from pair (c,d) if we go downward one step and get (x,y)
(x,y) = (c-d, d) if c>d
(x,y) = (c,d-c) if d>c
from (x,y) we will start the above process again. If anytime we reach (a,b) that is given in the input we are done. Otherwise Impossible.
Final code:
class PairGameEasy {
public:
string able(int a, int b, int c, int d)
{
if(a == c && b ==d)
return "Able to generate";
if(c == d)
return "Not able to generate";
while(c > 0 && d > 0)
{
if(a == c && b ==d)
return "Able to generate";
if(c > d)
c -= d;
else
d -= c;
}
return "Not able to generate";
}
Idea 3:
This problem can also be solved by dp by keeping a 2D array.
naseef_cuet has solved this problem in this way which is quite easy to understand.
int A[1011][1011];
class PairGameEasy {
public:
string able(int a, int b, int c, int d) {
for(int i=0;i<=1000;i++)
{
for(int j=0;j<=1000;j++)
{
A[i][j]=0;
}
}
A[a][b]=1;
for(int i=0;i<=1000;i++)
{
for(int j=0;j<=1000;j++)
{
if(A[i][j]==1)
{
if(i+j<=1000)
{
A[i+j][j]=1;
A[i][i+j]=1;
}
}
}
}
if(A[c][d]==1)
return "Able to generate";
else return "Not able to generate";
}
};
My long boring code during contest is here.
Discussion Forum 