UVA - 10305 - Ordering Tasks

• ID : UVA - 10305 - Ordering Tasks
• Language : Java , C++
• Status : Accepted - Accepted
• Type : Topological Sort.
• Time : 6 Hours.
• Solution :
1. Source Removal Method or DFS
2. Calculate in Degree.
3. Use a queue and insert at first all edges with 0 in Degree those who must be finished first.
4. Dequeue every time a node and decrease the in-degree of all it's neighbours as this node is considered to be removed from the queue or the task is done
5. each time you decrease the degree of the node. check if this task is available now ( i.e it's degree is zero that means that all of it's dependencies is already finished.
• Problems :
1. Check for special cases in the input. the m could be a zero and that what stopped me for 6 hours and I don't know what's wrong with my solution. I discovered that I have to remove the  m!=0  condition from the while loop statement.
2. I wasn't able to submit the DFS solution don't know what's the reason. but I decided to solve more problems for this period and come to this later
• Code :
1. http://snipt.org/wnmnm

UVA - 10147 - Highways

• ID : UVA - 10147 - Highways
• Language : Java , C++
• Status : TLE - Accepted
• Type : Graph MST.
• Time : 10 Hours.
• Solution :
1. Find All Edges
2. Kruskal's MST.
• Problems :
1. JAVA TLE Sometimes has no solution so don't waste your time in trying to get a Java solution Accepted.
2. Make sure the second minimum MST is larger than the Original MST.
• Solutions :
1. http://snipt.org/wnlgg

28th Feb Summary

• Problem Solved :
1. UVA - 10307 - Killing Aliens in Borg Maze - MST - Accepted
2. UVA - 11631 - Dark Roads - MST - Accepted
3. UVA - 10600 - ACM Contest and Blackout - MST - Accepted
4. CodeForces - 63A - Sinking Ship - Adhoc - Accepted
5. CodeForces - 63B - Settlers' Training - Adhoc - Accepted
• Problems Trails:
• NONE

• Readings:
• NONE
• Contests :
1. Codeforces Beta Round #59 (Div. 2)
• Rating : 1266 ( -76 )
• Problems Solved : 2  
• Score : 1090
• Notes from mistakes today :
1. On UVA always re-check multi-input problems weather I reset the storage or not.
2. hashCode() & equals() must be implemented together.
3. Use the custom Parser for Java Std Input in large data input problems to avoid TLE.
4. keep a minimum rate of a new topic daily.

UVA - 10600 - ACM Contest and Blackout

• ID : UVA - 10600 - ACM Contest and Blackout
• Status : Accepted
• Type : Graph MST .
• Time : 2 Hours to Submission.
• Language : Java
• Solution :
1. Find MST
2. Find MST in every time you remove an edge from the Original MST
• Problems :
1. Make sure the MST is not the Original MST by removing the edges from the original MST and looping through all edges.
2. Make sure the second minimum MST is larger than the Original MST.