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.

UVA - 11631 - Dark Roads

• ID : UVA - 11631 - Dark Roads
• Status : Accepted
• Type : Graph MST .
• Time : 30 Minutes to Submission.
• Language : Java
• Solution :
1. Add Total Costs of Edges.
2. Kruskal MST on Edges using Union-Find Algorithm
3. Subtract the MST cost from the Total cost.
• Problems :
1. Large Data Input so Buffered Reader & Scanner will give TLE
2. Don't Use Java Standard Input readers but use this Parser Instead.

Java Input Parser

This is a Fast Input Parser for Java Standard Input.
It's preferred to use this one instead of both Scanner & BufferedReader as your input reader
It's working for many problems and my recent one is UVa - 11631 - Dark Roads
Enjoy :) :)




this parser was implemented by Knightry

UVA - 10307 - Killing Aliens in Borg Maze

• ID : UVA - 10307 - Killing Aliens in Borg Maze
• Status : Accepted
• Type : Graph MST & BFS.
• Time : 5 Hours to Submission.
• Language : Java
• Solution :
1. Assume 'S' is a normal node as 'A'
2. BFS on all Nodes and Find all Edges.
3. Kruskal MST on Edges using Union-Find Algorithm
• Problems :
1. hashCode() Function shouldn't be implemented without equals()
2. Hashing should be avoided with pre-indexing.