m_a_r_c_e_li_n_o For those that are new to Graph Theory (i.e. myself), take a bit of time to firmly understand the construction of a Graph using an adjacency list, and how to explore the adjacency list using a "Breadth First Search" algorithm. Only then you'll be able to comprehend why this problem was categorized as "easy". I know there are people here succesfully solving it through "Dynamic Programming", and it's a valid method, but if you take that route, you'll miss out on an elegant and simple "Graph Theory" solution that I would argue is the purpose of this challenge. Admins, perhaps it might not be the worse idea to include "Adjacency List" and "Breadth First Search" as topics for this problem.
At any rate, if you are struggling as much as I was, take a look at this: http://theoryofprogramming.com/2014/12/25/snakes-and-ladders-game-code/
savras New to Graph theory and the link helped me solve this. Took me a while but it was well worth it! :)
smith1023 I definately will look into it. I solved it with a markov chain, it seemed apropriate... or maybe the name in the problem statement misleaded me :3
Foxkmi In that link:
"... He assume that getting caught by a snake is always unfavorable, and will not add to the progress of a short path..."
That is false. Is easy find an example.
jatinshravan "getting caught by a snake is always unfavorable, and will not add to the progress of a short path"
This does not seem to be accurate. Suppose a ladder is from 2 to 82, a snake is from 84 to 62 and another ladder is from 62 to 99 and nothing else, the optimal solution is to take the ladder to 82, then the snake from 84 to 62 and then take the ladder from 62 to 99.
alebrozzo Not correct, as the statement says "No square will have more than one of the starting or ending point of a snake or ladder (e.g. snake 56 to 44 and ladder 44 to 97 is not possible because 44 has both ending of a snake and a starting of a ladder)" However, Foxkmi is correct, you could have six consecutive short ladders that impede you to reach a large ladder, and theonly way to get that ladder is by the way of a snake. EG: ladders 21 to 39, 22 to 38, 23 to 37, 24 to 36, 25 to 35, 26 to 34, 28 to 95 snake 40 to 27 Falling from snake 40 helps you reach the ladder on square 28 that takes you one roll away from the winning square
mahpat Ladder from 2 to 82, Snake from 84 to 63 Ladder from 64 to 99
zainul118 but 100-82 = 18 so 3 turns which is same as with snake : 82-> 84, 63->64, 99->100.
I_luv_KitKat Then what about
Ladder from 2 to 50, Snake from 52 to 20, Ladder from 25 to 99
then it has only 4 steps to 100 (1-2) (50-52) (20-25) (99-100)
meteabogdan Thanks for the awesome link!!!
rizkidwip Thank you so much for this link. It gaves me correct way to solve this, with C# using BFS (level by level search) :my first Graph
harshloomba1 Thanks for the wonderful link. Here is my solution in java entirely based on the idea provied in the link
import java.io.; import java.util.;
public class QuickestWayUpLadder { private static byte MAX_ROLL = 6; private static byte BOARD_LEN = 100; private static Map> adjencyMap=new HashMap>(); private static Map listSnakes=new HashMap(); private static Map listLadders=new HashMap();
public static void main(String[] args) throws IOException { final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//Create board final byte[] board = new byte[BOARD_LEN]; //For every test case for(byte T = Byte.parseByte(br.readLine()); T > 0; --T){ //Initialize board for(byte i = 0; i < BOARD_LEN; ++i){ board[i] = i; } //Get ladder for(byte N = Byte.parseByte(br.readLine()); N > 0; --N){ final String[] line = br.readLine().split(" "); final byte S = (byte)(Byte.parseByte(line[0]) - 1); final byte E = (byte)(Byte.parseByte(line[1]) - 1); listLadders.put(S,E); } //Get snakes for(byte M = Byte.parseByte(br.readLine()); M > 0; --M){ final String[] line = br.readLine().split(" "); final byte S = (byte)(Byte.parseByte(line[0]) - 1); final byte E = (byte)(Byte.parseByte(line[1]) - 1); listSnakes.put(S,E); } System.out.println(); for(byte i = 0; i < BOARD_LEN; ++i){ System.out.print(board[i]+" "); } createAdjacencyList(board); replace(); printAdjencyList(); breathFirstSearch(); //Solve and print output// System.out.println(getMinMoves(board)); } }
private static void createAdjacencyList(byte[] board){
for(byte i=0;i<board.length;i++){ for(byte j=0;j<7;j++){ if(i+j>99) break; if(adjencyMap.containsKey(board[i])) adjencyMap.get(board[i]).add(board[i+j]); else adjencyMap.put(board[i],new ArrayList(board[i+j])); } }}
private static void printAdjencyList(){ for(byte i :adjencyMap.keySet()){ System.out.println(); System.out.print("key: "+i+"values: "); for(byte temp: adjencyMap.get(i)) { System.out.print(temp+" "); } } }
private static void replace(){ for(Byte t: adjencyMap.keySet()){ List temp=new ArrayList();
for(Byte t1: adjencyMap.get(t)) { if(listLadders.containsKey(t1)){ temp.add(listLadders.get(t1)); } else if(listSnakes.containsKey(t1)){ temp.add(listSnakes.get(t1)); } else temp.add(t1); } adjencyMap.put(t,temp); }}
private static void breathFirstSearch(){ int count=0; byte i=0; while(i!=99){ List temp=adjencyMap.get(i); Collections.sort(temp); i=temp.get(temp.size()-1); count++; if(i>99) break; } System.out.println(); System.out.println("number of steps: "+count); } }
rakeshKM Thanks man, for the link it was really helpfull
mk9440 Solved using Dijkshtra algorithm :D
import java.util.*; import java.io.*; public class Solution { public static void main(String[] args){ Scanner in=new Scanner(System.in); int test=in.nextInt(); for(int h=0;h<test;h++){ int w[][]=new int[101][101]; for(int i=1;i<=100;i++){ for(int j=1;j<=100;j++){ if(i!=j &&i<j && Math.abs(j-i)<=6){ w[i][j]=1; } else{w[i][j]=1000000;} }} int ladder=in.nextInt(); for(int i=0;i<ladder;i++){ int x=in.nextInt(),y=in.nextInt(); w[x][y]=0; } int snake=in.nextInt(); int sn[]=new int[snake]; for(int i=0;i<snake;i++){ int x=in.nextInt(),y=in.nextInt();sn[i]=x; w[x][y]=0; } Arrays.sort(sn);int cnt=0; for(int g=0;g<snake;g++){if(g>0 && sn[g]-sn[g-1]==1){++cnt;}else{cnt=0;}if(cnt>=6){break;}} Stack <Integer> t=new Stack<Integer>(); int src=1,des=100; for(int i=1;i<=100;i++){ if(i!=src){t.push(i);}} Stack <Integer> p=new Stack<Integer>(); p.push(src); while(!t.isEmpty()){int min=989997979,loc=-1; for(int i=0;i<t.size();i++){ w[src][t.elementAt(i)]=Math.min(w[src][t.elementAt(i)],w[src][p.peek()]+w[p.peek()][t.elementAt(i)]); if(w[src][t.elementAt(i)]<=min){ min=(int) w[src][t.elementAt(i)];loc=i;} } p.push(t.elementAt(loc));t.removeElementAt(loc);} if(cnt>=6){System.out.println("-1");continue;} if(w[src][des]!=1000000){System.out.println(w[src][des]);} else {System.out.println("-1");} }}}
Noel7 [deleted]Noel7 [deleted]Noel7 [deleted]
pareek_kunal83 I think this one needs Djikstra to solve and not BFS as the top voted answer seems to suggest.
aleksander_wald1 I am only about to solve this problem but I think BFS is fine - all the edges in the graph have length of 1 (1 die roll to be precise) You should be fine doing BFS then.
alidanish Exactly I also did it with Dijkstra, but interesting thing is when cost of all edges are same in graph, then Dijkstra can be reduced to simple BFS with complexity of O(n). So Dijkstra is good but BFS gives better complexity as it is a special case of Dijkstra where cost of all edges are same.
12_gunank Thanks a lot for this link with amazing explanation!
saketk21 [deleted]
DOER96 helpful link...gives an exact idea ..all u need is the implementation of the code and finding distance using bfs.
cs33shivam Thanks For the Link Sir, really helped me to undersatnd the concept.
subhajit104 really appreacited. All I understand how well you make the adj list. Just implememt bfs and "BINGO".
f(i,100){ if(snakes[i] or ladders[i]) continue; f1(j,1,7){ if(ladders[i+j] != 0){ adj[i].pb(ladders[i+j]); } else if(snakes[i+j] != 0 ){ adj[i].pb(snakes[i+j]); } else { adj[i].pb(i+j); } } } bfs(1);
sidprasad It's a bigger challenge getting the input right, than solving the problem :P
AKSaigyouji I'm seeing some pretty crazy solutions for this problem (Dijkstra's, Bellman Ford, dynamic programming, etc.)
This is a straightforward BFS, and doesn't even require the explicit construction of a graph, just an array with 100 (or 101) slots. For each slot, place either the index of that slot (i.e. 5th spot has a 5 in it), or, if it has the head of a snake or start of a ladder, the endpoint of that snake/ladder.
The slots form an implicit graph where the connected vertices from a given slot are the 6 slots after the current one.
Running a BFS on this implicit graph will get you the solution.
The reason you don't need dijkstra's is that you're only measuring the number of die rolls: you don't care about distance travelled (edge weights). Similarly, you don't need bellman ford as that is an algorithm needed to handle negative edge weights.
onecrane Thanks for this - I was going to go Dijkstra, but it felt a little heavy for a graph with equal edge costs. I wouldn't have thought of BFS, and needed to think of how to apply it, but doing so gave me an addition to the toolbox!
ic3balandran This comment actually made more sense to me. Especially your last paragraph. I'm new to graph problems, I understand BFS and DFS, but I didn't know how to approach the whole die rolls. The key in the BFS is to enqueue its adjacent nodes based on the max die roll value which is 6 (Could be 12 if using two dice), but you need to watch out for snakes while doing it. Also for me I checked if there were 6 consecutive Nodes with a snake head and if I found that true I return -1, I did this before the BFS no need to do a BFS if there is no possible solution.
ryashin_egor Most useful hint! Thanks!
xdavidliu here's a simple java solution that does it according to your description
import java.util.Scanner; import java.util.ArrayDeque; import java.util.Queue; class Solution{ static final int squares=100; static final int nowhere=-1; static int solve(int[] trans){ boolean[] vis=new boolean[squares]; Queue<Integer> q=new ArrayDeque<Integer>(); final int start=0,dice=6,noSolution=-1,win=squares-1; q.add(start); vis[start]=true; int[] roll=new int[squares]; // q never contains spot with start of snake/ladder while(!q.isEmpty()){ int x=q.poll(); for(int i=1;i<=dice && x+i<squares;++i){ int j=x+i; while(!vis[j]){ vis[j]=true; if(j==win) return roll[x]+1; else if(trans[j]==nowhere){ q.add(j); roll[j]=roll[x]+1; } else j=trans[j]; } } } return noSolution; } static int[] transport(int[][] ladder, int[][] snake){ int[] tr=new int[squares]; for(int i=0;i<squares;++i) tr[i]=nowhere; for(int[] l: ladder) tr[l[0]]=l[1]; for(int[] s: snake) tr[s[0]]=s[1]; return tr; } static int[][] readEdge(int n, Scanner sc){ int[][] edge=new int[n][2]; for(int i=0;i<n;++i){ edge[i][0]=sc.nextInt()-1; edge[i][1]=sc.nextInt()-1; } return edge; } static void input(){ Scanner sc=new Scanner(System.in); int t=sc.nextInt(); for(int i=0;i<t;++i){ int n=sc.nextInt(); int[][] ladder=readEdge(n,sc); int m=sc.nextInt(); int[][] snake=readEdge(m,sc); int[] trans=transport(ladder,snake); System.out.println(solve(trans)); } sc.close(); } public static void main(String[] args){ input(); } }
mtanida This problem is sort of unintuitive for people who've never heard of Snakes and Ladders. I feel like the problem description and the example problem can be improved to explain the rules of the game more clearly.
hwu533 Agreed. I feel like if we have to spend time reading an external link, it should be a cool algorithm not the rules for a game.
ziggystar Why can't this problem use the usual space and newline separated format?
shashank21jHackerRank Admin updated :)
ShubhamV06 how is (-1) possible?
jcarlson08 Imagine a board where space 100 is the goal and spaces 99, 98, 97, 96, 95, and 94 are all snakes leading to previous positions.
ShubhamV06 Thanks!
lewis_yishi_liu Just a recommendation for the input for the test cases. While it makes thematic sense to separate the snakes and ladders, it actually just complicates the implimentation as they function identically in the problem solution (both are just directed edges). So instead of separating them as:
3
17 38
34 92
54 62
2
63 21
56 33
It would make things easier to just list the input as:
5
17 38
34 92
54 62
63 21
56 33
and then make the clarification that Snakes go from a higher index to a lower index while Ladders go from a lower index to a higher one.
_choc Remember that if you're taking a snake or ladder, that move costs 0 turns
itsbruce It simplifies the path-search code (and only very slightly complicates the input-processing code) if all moves have the same cost. So if there's a ladder from 12 to 98, don't think of it as 12 having a neighbour with no cost. Think of 6, 7, 8, 9, 10 and 11 having 98 as a neighbour (and no longer having 12 for a neighbour at all).
colonel_bishop This was missing for me. Thanks!
brocktane Hello,
Everyone's talking about using graph search algorithms. Isn't this problem best solved using DP (for O(n) run time)? Or am I missing some concept here?
PureEvil Agree with this. The problem is best solved using DP
abhiranjan And with any single source shortest path algorithm.
mehdi_raz not really. because we have to types of edges. edges with cost 1, and edges with 0 cost (those that are connected using ladder or snakes)
rgevorky This is a setback, but not a fatal one. I used BFS, but to make that work, you have to do the following: if you can get from square i to square j in one die roll and j begins a ladder or a snake to square k, add in your adjacency matrix A[i,k] = 1 and make A[i,j] = 0 (the idea is that if we can hop onto a ladder or snake, cut out the middleman and just go directly to its destination. Also we can't go to the space with the start of a ladder or snake because that would imply we didn't follow the ladder or snake to its destination). This way we do not need edge weights and so we can use simple BFS. Dikjstra's is a little overkill with only 1's and 0's.
rgevorky Note also that you would need to additional work if a ladder or snake could end where another ladder or snake began. You would need to follow the entire path until we reached a square without the beginning of a ladder or snake. Fortunately the problem states that this is guaranteed not to happen so we don't have to worry about that here.
aviben [deleted]
abhi134 Even i'm trying to solve it by DP, but the problem i'm facing is the snakes cases. We need to update the square with tail of snake with the mouth of snake but we don't have that value yet. Please ping me if you thought of something, @brocktane and @PureEvil .
AbhishekVermaIIT DP gives an efficient solution to the problem (solves all test cases in 0s with C). The basic idea is as follows :
1) Calculate number of minimum moves required to reach each every square, starting from 1 till 100 (square 100 gives the answer). Initialize all the sqaures with a "very high value" to begin with.
2) Ladders : If the current square is starting-point of ladder, update the square at the end-point of the ladder (note : end-point of ladder > start-point of ladder). If the minimum moves required to reach the current square is "c" and the current value of square at the end-point of ladder is "x" then the updated value should be min(c,x).
3) Snakes : If the current square is starting-point for snake, update the square at the end-point (tail) of the snake only if the moves required to reach the current square is less than the "value of square at the tail of the snake". If the value is updated, start calculating the moves from the tail of the snake (end-point for snake < start-point for snake).
This allows you to ignore being at the tail of snake, because the tail will be updated (if required) when you'll reach the head of the snake and everything is recalculated. Also, since tail is updated only on getting lower value, no such tail will be updated more than once usually.
While implementing, you need to consider all the three points mentioned above simultaneously for each square. Also, do remember to consider the current value of the square to find minimum each time.Happy Coding !!!
abhi134 You didn't consider the tail part rigorously here.
If the tail value is updated, all the values are reevaluated. This update could lead to another snake-head value update, in turn leading to another series of updates because of the corresponding new-tail update. Thus, the time complexity doesn't remain linear anymore, rather can go as high as exponential. (okay, i didn't put thought in it, i'm just guessing)
But DP isn't a very efficient solution to this.
AbhishekVermaIIT Actually, it won't ever happen because of two reasons : First, tail is updated only if the value at head is smaller than the value at tail. Second, if we reach the head of snake again (without some other tail update), we can't get value smaller than the tail (Perhaps running through some example can help clarify it more). Thus, ensuring no tail of snake will be updated more than "number of other tails updates" (which is usually once), and hence, giving a linear solution.
In fact, I found DP very convenient and efficient for this particular problem. I gave this solution since you mentioned that you were stuck with DP because of snakes-case and were looking for some idea. Have a look if it helps you, else, its perfectly fine if you like some alternate approach :)
Sapta89 I thik it's better to update the next 6 cells also ahead of the end of ladders (only if it has higher value than start) with min of current and (1+start of ladder). This will elliminate the need of recalculation lot of in between squares if a snake is used to come down a long. It'll automatically take into consideration improvements made by the ladder discovered till that square. Then just consider the tail of the snake and get min of current or head of the snake, as we iterate the squares increasingly. each square is considered once only.
AbhishekVermaIIT Just consider "minimum of previous six squares" while updating current sqaure. Everything else will be handled automatically.
InfiniteCoder What is this DP algorithm? I never heard of this, does it have any other name(or full form)?
AbhishekVermaIIT DP stands for Dynamic Programming. It is a design technique (e.g. Divide and Conquer) rather than some particular algorithm.
Hackerrank has a complete subdomain entirely dedicated to it, you might want to have a look : https://www.hackerrank.com/domains/algorithms/dynamic-programmingInfiniteCoder Thanks. I thought you were discussing about some algorithm ;)
aakash_balaji I thought that as well, thanks for clarifying.
tikt4ever Thanks, following these hints worked for me. I feel dirty in that I needed to look at hints (and spend hackos to examine failed test cases), but I solved it...
AbhishekVermaIIT Glad that it helped :)
shivaaryan_p7475 we have to also consider the case when there is a ladder which can jump though countinous snakes..
AbhishekVermaIIT No, that isn't required.
Please check the Constraints, it mentions : No square will have more than one of the starting or ending point of a snake or ladder.
shivaaryan_p7475 actually i had a case in my mind 1 1 37 99 7 98 40 97 41 96 42 95 43 94 44 93 45 92 46 in this case reaching hundred is possible where as if we dont have the ladder reaching hundres is impossible
AbhishekVermaIIT In this case : since ladder is present to 99, you'll definitely get solution because of second step "Ladders" as described in previous comment above. Else if there was no solution (no ladder to 99) just print
-1as mentioned in problem statement.
Ayelis The constraints of the problem say there will always be at least 1 ladder, regardless of how helpful it may be.
If there's no helpful ladder, you'll still get to 100 in 17 rolls. How is 17 not the solution in that case? I could see the need for -1 though, as if six squares in a row have snakes, you can't get past without a ladder.
AbhishekVermaIIT You are right, thats exactly what the case was. Actually, it was reply to shivaaryan_p7475 for the particular case : "consecutive squares at the end (98-92) having snakes". Please see the comment just above that.
Ayelis Ah, I see what shivaaryan_p7475 is saying. He says you can't JUST count for 6 consecutive snakes, because even if Square 10 to Square 90 is ALL SNAKES, you could still have 1 ladder that goes from square 2 to square 99, and win easily.
But there will never be 0 ladders. The problem states this clearly.
"1 <= Number of Ladders <= 15"
AbhishekVermaIIT Oh, now I get your point. You are just trying to say that I shouldn't have written "no ladder" because there will always be one ladder atleast. Actually, shivaaryan was discussing about the solution I proposed, and he was curious if the solution would be able to handle all the cases well. Hence, he gave me following case (as you can see in his comment) :
Ladder : 37->99 Snakes : 98->40, 97->41, 96->42, 95->43, 94->44, 93->45Thus, I replied that this particular case would be handled well by the "2nd step Ladders" of the solution. While clarifying it further, I wrote : even if that ladder(37->99) wasn't present, we'll still get the answer "-1". So, "no ladder" just meant "no ladder to 99", because of this particular case with just one ladder.
I am also aware the problem states that there will be atleast one ladder, but, I was just discussing that particular case there. Though, its a valid point that it can confuse someone-else too, hence, I have modified "(no ladder)" to "(no ladder to 99)" to avoid any further misinterpretations.
POD_codemore Hey thanks a lot for this approach, I had written something similar :) Had missed certain conditions! This works perfectly fine! Kudos for nice explanation! Need to look out for some tricky cases to print -1!!
AbhishekVermaIIT Good to know that it was helpful :)
etayluz C solution with dynamic programming below. This took me a few hours to get right - and debugging is difficult with recursion. What made it easier to debug was to avoid recursion by using a queue to pile on new cells whose count has been updated. Recursion also has a way of leading to stack overflows.
int transition[100]; int boardCount[100]; int queue[100]; int size = 0; void calc(int cell) { //printf("cell = %d, count = %d\n", cell, boardCount[cell]); size--; for (int i = 0; i < size; i++) { queue[i] = queue[i+1]; } for (int i = 1; i <= 6; i++) { int newCell = cell + i; int newCount = boardCount[cell] + 1; if (newCell < 100 && newCount < boardCount[newCell]) { boardCount[newCell] = newCount; if (transition[newCell] != 0 && boardCount[transition[newCell]] > newCount) { boardCount[transition[newCell]] = newCount; queue[size++] = transition[newCell]; } else { queue[size++] = newCell; } } } } int main() { int t; scanf("%d", &t); while (t--) { int ladders; for (int i = 0; i < 100; i++) { boardCount[i] = 1000; transition[i] = 0; } scanf("%d", &ladders); for (int i = 0; i < ladders; i++) { int start, end; scanf("%d %d", &start, &end); transition[start-1] = end - 1; } int snakes; scanf("%d", &snakes); for (int i = 0; i < snakes; i++) { int start, end; scanf("%d %d", &start, &end); transition[start-1] = end - 1; } boardCount[0] = 0; size = 1; queue[0] = 0; while (size) { calc(queue[0]); } printf("%d\n", boardCount[99] == 1000 ? -1 : boardCount[99]); } return 0; }mk9440 Solved using Dijkshtra algorithm :D
import java.util.*; import java.io.*; public class Solution { public static void main(String[] args){ Scanner in=new Scanner(System.in); int test=in.nextInt(); for(int h=0;h<test;h++){ int w[][]=new int[101][101]; for(int i=1;i<=100;i++){ for(int j=1;j<=100;j++){ if(i!=j &&i<j && Math.abs(j-i)<=6){ w[i][j]=1; } else{w[i][j]=1000000;} }} int ladder=in.nextInt(); for(int i=0;i<ladder;i++){ int x=in.nextInt(),y=in.nextInt(); w[x][y]=0; } int snake=in.nextInt(); int sn[]=new int[snake]; for(int i=0;i<snake;i++){ int x=in.nextInt(),y=in.nextInt();sn[i]=x; w[x][y]=0; } Arrays.sort(sn);int cnt=0; for(int g=0;g<snake;g++){if(g>0 && sn[g]-sn[g-1]==1){++cnt;}else{cnt=0;}if(cnt>=6){break;}} Stack <Integer> t=new Stack<Integer>(); int src=1,des=100; for(int i=1;i<=100;i++){ if(i!=src){t.push(i);}} Stack <Integer> p=new Stack<Integer>(); p.push(src); while(!t.isEmpty()){int min=989997979,loc=-1; for(int i=0;i<t.size();i++){ w[src][t.elementAt(i)]=Math.min(w[src][t.elementAt(i)],w[src][p.peek()]+w[p.peek()][t.elementAt(i)]); if(w[src][t.elementAt(i)]<=min){ min=(int) w[src][t.elementAt(i)];loc=i;} } p.push(t.elementAt(loc));t.removeElementAt(loc);} if(cnt>=6){System.out.println("-1");continue;} if(w[src][des]!=1000000){System.out.println(w[src][des]);} else {System.out.println("-1");} }}}
maxballard333 [deleted]
sivakavitha18397 why transition variable are used above.. and transition[start-1] = end - 1; i dont understand this line i am new to program..
yousuf_1991 I did the whole thing top down with memoization. Even I was stuck with the infinite loop that was the wretched snake. To update the tail, I needed to go through the head, and the head eventually led to the tail, and so on. To solve this, I just removed the entire snake from the array (hashmap in my case) after processing it's tail, and it worked. "Also, since tail is updated only on getting lower value, no such tail will be updated more than once usually." - No tail will EVER be update more than once? Not sure if we're talking about the same thing. Came here to see how other people solved this. Nice to see your answer.
AbhishekVermaIIT You are absolutely right Yousuf, the tail might be updated more than once. That's why I wrote "more than once usually". Assuming the above algorithm is followed, the probability that the same tail is updated more than once, is really low (can be confirmed by counting tail-updates for various test case). This is mentioned in the other comment that it has (very loose) upper bound of "number of other tail updates". Though, since tail is updated only when we take "lesser moves" in spite of going through snake, even single update isn't that probable. Glad to know that you felt good for the solution :)
yousuf_1991 Oh no, you have me totally wrong, I meant that I believe no tail will ever get updated more than once. At least that's the premise of my implementation. After I process a tail, I remove the snake entirely. Maybe I'm wrong here?
AbhishekVermaIIT Oh buddy, in that case I guess our algorithms differ slightly. Consider the following case :
Ladders Snakes 5 -> 70 63 -> 42 16 -> 61 75 -> 62 43 -> 99For the above mentioned case, 5 moves are required.
42 (tail of snake) gets updated twice. First time because of the ladder 16->61 and second time because of (5->70, 75->62). This happens as per algorithm I described above. Though if you are filling top-down, it would update only once !
yousuf_1991 Cool, I get it now. Thanks man!
liuxuan30 [deleted]
JuanDavidCanti Thank you very much friend
I spent hours thinking about how to make the challenge and had been unable to achieve. I read the implementation of dynamic programming, and I take only 2 minutes to implement in java and upload does not take almost no time to solve test cases.
Muchas Gracias amigo
Estuve horas pensando en como hacer el reto y no habia podido lograrlo. Leà la implementacion sobre programacion dinamica, y me tomo tan solo 2 minutos implementarlo en java y al subirlo no toma casi nada de tiempo en resolver los casos de prueba.
SpencerMKSmith I agree with you, I just solved it using DP and it was much more efficient than the BFS solution is. The only tricky part was figuring out the snake part, but a pretty simple recursive function helped me get it. Was a fun problem! I definitely don't think it deserves the "easy" label that the site gives it.
mehdi_raz I tried the DP, but had the same problem as @abhi134 had. I think DP cannot solve this type of problems since we may have to move forward to backward. This means we cannot create sub-problems because when trying to find the minimum # of roll to reach to ith cell, we may need to calculate k k>i (because of ladder) or need to access jth cell (j
contact_tbrooks Even if there is a more efficient DP solution - this is a graph problem. I think part of the challenge really should be to constrain yourself to the scope of the problem for personal growth working within that domain. That's what I think, anyway. =)
rgevorky That's a fine variation. Note though that BFS is also O(n). |E| <= 6*100 if you construct the adjacency matrix so that a ladder/snake from i to j means all squares a die roll from i are adjacent to j and not adjacent to i. This means in effect any additional edge created by a snake or ladder is balanced out by the deletion of a die roll adjacency.
BFS has time complexity O(|V| + |E|), and so if we alter the problem slightly so that |V| = |N| can be an arbitrary number and the number of ladders/snakes is linear in n then O(|V| + |E|) = O(N + O(N)) = O(N).
pdog1111 BFS is also O(n)
itsbruce Dijkstra's algorithm is DP. What makes you think the two categories are mutually exclusive?
jackstro I'm using python3 and trying to solve the problem using a BFS approach. I am timingout on test 2 and 6 and I can't seem to find out why. Any thoughts?
contact_tbrooks I fully solved it using Bellman-Ford and a full graph structure. It's a very fat solution and could use a lot of cleaning up, there were quite a few caveats to handle. Overall this challenge was really hard for me, I really don't think it should be marked easy, even though I am amateurish with graphs (as this challenge has thoroughly proven). If you're having a hard time like I did, don't give up! You CAN do it! The test cases were extremely well thought out, don't try to 'cheat' your way through it - if the solution doesn't seem elegant it probably won't pass further test cases.
Here is the Bellman-Ford function I used - hopefully it will help:
// No bool bellmanFord( Graph* graph, int src, vector<int>& dist, vector<pair<int,int>>* prev = nullptr ) { int V = graph->vertices.size(); int E = graph->edges.size(); dist.resize( V ); if( prev ) prev->resize( V ); // Step 1: Initialize distances from src to all other vertices // as INFINITE for (int i = 0; i < V; i++) dist[i] = INT_MAX; dist[src] = 0; (*prev)[src] = make_pair(-1,-1); // Step 2: Relax all edges |V| - 1 times. A simple shortest // path from src to any other vertex can have at-most |V| - 1 // edges for (int i = 0; i < V-1; i++) { for (int k = 0; k < E; k++) { int u = graph->edges[k].a->index; int v = graph->edges[k].b->index; int weight = graph->edges[k].distance; if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; if( prev ) (*prev)[v] = make_pair( u, k ); } } } // Step 3: check for negative-weight cycles. The above step // guarantees shortest distances if graph doesn't contain // negative weight cycle. If we get a shorter path, then there // is a cycle. for (int i = 0; i < E; i++) { int u = graph->edges[i].a->index; int v = graph->edges[i].b->index; int weight = graph->edges[i].distance; if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) { return false; } } return true; }Note that this is a modified version of the function provided here: http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/ Please take the time to read this artictle and watch some videos explaining the algorithm, it takes a bit to grasp fully but it's good stuff to know! I'll leave it to you to figure out how to interpret a path from the information provided here.
You will need to handle several edge cases. What happens if it is more efficient to roll a higher number than do a hop? For instance, if we roll 2 and have a ladder that takes us to 4, we might as well have rolled a 5 or 6 (assuming no snakes). Also bear in mind situations where there are 6+ snakes with no empty slots between them - unless there is a ladder to bypass them, that grid is unsolvable. Bear in mind, also, the case in which you might take a ladder - then a snake - to save on distance costs... but could have had fewer ROLLS by bypassing the ladder entirely!
Again, best of luck and keep at it! I wanted to quit several times but forced myself to keep going and I'm glad I did. =D
mk9440 Solved using Dijkshtra algorithm :D
import java.util.*; import java.io.*; public class Solution { public static void main(String[] args){ Scanner in=new Scanner(System.in); int test=in.nextInt(); for(int h=0;h<test;h++){ int w[][]=new int[101][101]; for(int i=1;i<=100;i++){ for(int j=1;j<=100;j++){ if(i!=j &&i<j && Math.abs(j-i)<=6){ w[i][j]=1; } else{w[i][j]=1000000;} }} int ladder=in.nextInt(); for(int i=0;i<ladder;i++){ int x=in.nextInt(),y=in.nextInt(); w[x][y]=0; } int snake=in.nextInt(); int sn[]=new int[snake]; for(int i=0;i<snake;i++){ int x=in.nextInt(),y=in.nextInt();sn[i]=x; w[x][y]=0; } Arrays.sort(sn);int cnt=0; for(int g=0;g<snake;g++){if(g>0 && sn[g]-sn[g-1]==1){++cnt;}else{cnt=0;}if(cnt>=6){break;}} Stack <Integer> t=new Stack<Integer>(); int src=1,des=100; for(int i=1;i<=100;i++){ if(i!=src){t.push(i);}} Stack <Integer> p=new Stack<Integer>(); p.push(src); while(!t.isEmpty()){int min=989997979,loc=-1; for(int i=0;i<t.size();i++){ w[src][t.elementAt(i)]=Math.min(w[src][t.elementAt(i)],w[src][p.peek()]+w[p.peek()][t.elementAt(i)]); if(w[src][t.elementAt(i)]<=min){ min=(int) w[src][t.elementAt(i)];loc=i;} } p.push(t.elementAt(loc));t.removeElementAt(loc);} if(cnt>=6){System.out.println("-1");continue;} if(w[src][des]!=1000000){System.out.println(w[src][des]);} else {System.out.println("-1");} }}}
Sort 155 Discussions, By:
Please Login in order to post a comment