dfs

TOPCODER SRM 800 DIV2 MEDIUM (750 points)

| Shadek

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

ACM ICPC 2017

| Shadek

Download the problems from here: https://icpc.baylor.edu/worldfinals/problems/icpc2017.pdf

Discussion on two easy problems:

Problem F: (Posterize)

This problem can be solved using standard dynamic programming approach. One thing to notice in this problem is that only 256 (d) (0 to 255) different red values are possible and number of allowed red values (k) is at most d. This observation directs us to solve the problem using 2d DP table with dimension of 256 x 256.

Here is the code

In the code, mat[i][j] denotes the sum of squared error when current chosen red value in posterized image is i and number of distinct red values already chosen in the image is j. And we are only required to take care of red values from the input which are greater than i. The base case in the DP table is when we have used up all the allowed number of red values. In this case imagine that final chosen red value is prev. So from the input, all red values greater than prev will be replaced by prev.

Problem I: (Secret Chamber at Mount Rushmore)

The problem can be solved using Floyd-warshall algorithm to find the reachability between the letter pairs. Here is the code

SRM 664 (div2 medium)

| Shadek

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?

Continue reading →