Sunday, January 29, 2012
My Facebook Hacker Cup 2012 Round 1 - Squished Status answer (Java)
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Scanner;
public class C {
public static void main(String[] args) throws FileNotFoundException {
Scanner in = new Scanner(new File("input.txt"));
PrintWriter out = new PrintWriter(new File("output.txt"));
int T = in.nextInt();
for (int i = 0; i < T; i++) {
String s = new C().solve(in,i+1);
out.println(s);
System.out.println(s);
}
out.close();
}
HashMap<Integer,Long> hash1=new HashMap<Integer,Long>();
HashMap<Integer,Long> hash2=new HashMap<Integer,Long>();
private void printDebug(HashMap<Integer,Long> hash1)
{
for(Entry<Integer,Long> e:hash1.entrySet())
{
System.err.println(e.getKey()+","+e.getValue());
}
}
synchronized private String solve(Scanner in, int caseid) {
int m = in.nextInt();
String s = in.next();
int i=0;
// System.err.println("m="+m+",s="+s);
hash1.clear();
int c=(int)s.charAt(0)-48;
if(c>0)
hash1.put(c, 1l);
for(i=1;i<s.length();i++)
{
c=(int)s.charAt(i)-48;
// System.err.println("c="+c);
hash2.clear();
for(Entry<Integer,Long> e:hash1.entrySet())
{
int s0=e.getKey();
int s1=s0*10+c;
int s2=c;
long c0=(hash1.get(s0)!=null)?hash1.get(s0).intValue():0;
long c1=(hash2.get(s1)!=null)?hash2.get(s1).intValue():0;
long c2=(hash2.get(s2)!=null)?hash2.get(s2).intValue():0;
hash2.put(s1,(c1+c0)%0xfaceb00c);
hash2.put(s2,(c2+c0)%0xfaceb00c);
if(s1<=0||s1>m)
hash2.put(s1,0l);
if(s2<=0||s2>m)
hash2.put(s2,0l);
}
hash1.clear();
for(Entry<Integer,Long> e:hash2.entrySet())
{
if(e.getValue()>0)
{
hash1.put(e.getKey(), e.getValue());
}
}
// printDebug(hash1);
}
long res=0;
for(Entry<Integer,Long> e:hash1.entrySet())
{
res=(res+e.getValue())%0xfaceb00c;
}
return "Case #"+caseid+": "+res;
}
}
Subscribe to:
Post Comments (Atom)
Hey Kevin...its me again :)
ReplyDeletecan u plz recommend me some books for dynamic programming and algorithms....nd other useful books which will help me in programming in java....cheers
Adhiraj,
DeleteI think you have 3 sub-questions in your question. :)
I just learnt those things from google:
1. Dynamic programming
- http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html
2. Algorithms
- http://mat.gsia.cmu.edu/orclass/integer/integer.html
- http://www.vogella.de/algorithms.html
3. Java
- I just learnt java from examples. e.g. http://www.java-examples.com
Thanx a ton man....i im thinking of buying "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson....for learning algorithms....after watching Stanford videos of "Design and Analysis of Algorithms I" by Tim Roughgarden....i hope im not troubling you...im 17 years old, but i want to learn as much as possible about programming before going off to college :)
ReplyDeleteI had read this book when I was a computer science student long long time ago.:) But actually, I just read a few pages of it in my life time. Because you can get the most of the same knowledge mentioned in this book from Google search and Wikipedia. Honestly, if I were you, I will save the money and paper.
DeleteI think your purpose is to increase java programming skill and algorithm knowledge. I will suggest you to join www.topcoder.com and play their SRM. After a few month, you will advance your skill a lot.
http://en.wikipedia.org/wiki/TopCoder
http://www.topcoder.com/
Thanx A Lot !!...really needed someone to guide me. :) :)
ReplyDeleteTry this:
ReplyDeletehttp://jayengineteam.blogspot.com/2012/02/solution-to-top-coder-srm-531-non.html