GCJ 2011 experience

Here is my Google Code Jam 2011  experience. I thought i would blog about it .Below is what was going through my mind during whole contest.

Candy Spliting : (Click to view problem statement)

Not getting any slick approach.One coming to my mind is to go through all the possible subsets using recursion and check which yields maximum answer.But would it fit time constraints ? Small test case N=15 so total number of subsets to be scanned 2^15-1=32767 ,so this would definitely work ..cool lets work this out.Implemented the whole code .Didn't get accepted .What i am doing wrong?.Ah..missed to add string "Case #X:" ,did this change. So finally passed and made my first submission.

Well for long test data N=1000 this mean total number of subsets is equal to the number with ceil(log(2^1000))-1 digits, (assuming the acm style scenario ,10^8 operations per sec this means tx=(60*60*24*365*(10^8)) ..['^' is used for power operation], operations per year ,total time in years to solve candy splitting with this approach would be (2^1000-1)/tx years that too assuming a subset can be generated in 1 operation :O ,probably that would take many many code jams if my math isn't wrong) and this is for single case there will be 100 testcases .This wont gonna work for long test data.But didnt getting any other approach.I'll leave this now.Would come back to this prob later.

GoroSort: (Click to view problem statement)

Somewhat similar to Bogosort.But not  able to reach any solution.Well i would go for this one once i complete rest three.I guess this is tougher than previous one .

Magicka : (Click to view problem statement)

Some sort of simulation.I think if I implement the code in the way exactly mentioned in the statement it would be able to pass for both large and small.Two grids each of size 26x26 could be used to store the combine and oppose relationships .Need to take care of the fact that relationships are symmetrical .So if com[i][j]=1then com[j][i]=1 ,com is the name of grid where i am storing combine relationship same for oppose grid.After this i just need to add element to the list and check the rest of the list for further oppose or combine relations.Implemented the code .Submitted for both small and large test data.Passed for small.Result for large would be available at the end of the contest.

Bot Trust : (Click to view problem statement)

I guess this is the easiest one .Just need to go through the sequence in which both the robots move.And take care of the fact that both the bots can move in parallel.For example in sequence list present move is of blue bot and it moves net distance of 5 units and the next orange bot move require to move next distance of 2 unit so we can move the orange bot to 2 units .Incase the orange bot requires to move 8 units then it would move only 5 units since at present the Blue but is under consideration and it can move only 5 units.Implemented the code but didnt got accepted .Did some mistake in implementation part in calculating net distances ,corrected it and passed for small.Large's statues unknown.

Back To Candy Splitting:

Hmm...What should i try some sought of 0-1 knapsack ,what i am thinking ?aint gonna work.There is something in XOR operation.Should i count the number of times a specific value occured but what i would do with this information.One thing is for sure the solution would only exist if XOR of all the values is zero.Oh my god....I just need to check if XOR of all values is zero and subtract the minimum value of all given values from the sum of all values.Cant believe my code for large data is much small and faster than my code for small data. WOW that feels really nice.

Should I go for Gorosort again ?Have no specific ideas .Plus don't want to work more on this.

Finally all of them passed .70 points out of 100 this year and rank 4509 .Not bad in comparison with my last performance (stood somewhere around 9900 and scored 10 points only).For the First time qualified for   round 1.

Participated in all sub rounds of Round 1 .But missed all time ,mostly due to late submissions for the problem I need to code fast. More precisely get with the correct approach fast. And frame more good solutions.

Was able to solve 1 problem (for both small and large test data) in all sub rounds of round 1 and one more for small test data which was good but not good enough. Well let’s see what happens next time :-).

EDIT: GCJ 2012 was relatively easy .Attempted only few problems to get eligible during  quals
 Did well in round 1 this time (rank 1918)  as compared to last year rank (2000 something)  .But still wasnt eligible for round 2 as it takes top 1000 coders. Hope i can make it next year (or not ?)|:D

SECOND CHANCE

I haven't blogged for long.Actually i was unable to figure out what to blog about.Few weeks ago i watched a show on NGC (national geographic channel) on a true incident.Its about how life gives you second chances(which is very very rare) and how you use them.

There was a guy(i would call him X as i don't remember his name) who was in bad company from his early teens Later at age of 19-20 he started robbery at the stores in Dallas . All this became his habit, like he don't know anything else
Also there was no one around him to tell him that what he is doing is wrong. He was caught by cops in his
early 20s.As mentioned in the show ,there were very strict laws for offenses like robbery during those
days in US by strict mean term of 80 years of imprisonment,which was the punishment of that guy.
According to him life was bit unfair to him as he wasn't aware that he could be jailed for such a long time
and he had no one around him to stop him from doing all the bad stuff and he never intended to kill anyone one
and he never did that.

After spending few weeks in a maximum security prison that guy decided to escape from the prison.Which was a very difficult task but he was fully determined that would to do that.He started analyzing the prison parameter,modeling it with cards,coffee cups ,chess pieces. He managed to find a cutter which he could use to cut the fences but the handles of the cutter were small by which he cant get the grip to cut the fences so he added two pipes to the handles of cutter which provide him sufficient grip he later hide that tool in cold storage .


He involved 2 more convicts in his plan.They managed to arrange a rough map about the area from which they get the idea about the whole geography of the area and how much effort would be needed to get out from the jail.They observed that even if they somehow manage to cross all the fences they'll need to run a distance of minimum 5 miles in a very small time so that they can get out of the reach of cops.For that they decided that they'll do some running every morning .But X was the only one who actually did the running the other two guys didn't.Just few days back before the escape the observed that they need to sabotage the jail power supply both the main supply and backup so that their escape become easy and safe.At the night of escape all three of them assembled during dinner .The generator room was near the mess so a member of team managed to get in the generator room15 minutes passed but there was no power cut so X decided to go to generator room.There he saw his team member was still talking to the guy at generator room.He quickly rushed and hit the guy at generator room and tied him with the shirt and warned him not to make noise.He first sabotaged the backup and later the main supply.After that all of them started to cut the first fence . When they came to second fence X realize this may take some more time so he suggested that they should climb the fence while the other two said its risky and X should cut the fence .X replied if that cutter is making them think that they should cut the fence then he'll throw the cutter on the other side of fence and he actually did that X then said to both of them now we don't have any option .So all three of them started climbing X and one more guy did that in very less time while the trousers of third member of the gang was facing some problems in crossing the fence X get back to him and helped him to get out of fence
Both of them were sighted by a cop and he started shooting at them But they managed to escape
Now they needed to run as fast as they can to get out of the jail parameter.Here the training of running really helped X as he was the only one who managed to run such a long distance in less time while the other two guys struggled and that is why both of them were caught with in next 24 hours.But X finally made it.

Now in my opinion he realized that he did a bad stuff and wanted to live a good and clean life So that is why he get succeeded in this.But there was a twist .

As soon as he get out of the prison he first robbed an old man later bought a toy pistol which looked almost same as real one
and robbed a store. Once he got decent amount of money he started doing the robbery frequently .The cops were smart as usual
and reached the conclusion that X would go to his hometown first .And he actually did that and also started frequent robberies there so this led the cops to reach him and very soon they caught him at a night club.

After watching the show i thought That what would have happened if X had started living a good and a clean life?I don't mean that his prison escape was a right thing.But if he didn't had started the bad stuff there was a small possibility that he could have led a better life. In my opinion super power above showed some mercy on him but he totally wasted it.

WROTE A CODE TO GENERATE ALL POSSIBLE PERMUTATIONS OF A SET OF 9 ELEMENTS
HAVE A LOOK

import java.io.*;

import java.util.*;

class gpint{

public static void main(String args[])throws Exception

{

int i=0,min=0,max=0,j=0,k=0;

String s="",mi="",ma="",t="",t1="";

boolean bo = true, bo2 = false;

System.out.println("enter the elements of set for generating the permutations (upto 9 elements)");

BufferedReader b=new BufferedReader(new InputStreamReader(System.in));

s=b.readLine();

if (s.equals(""))

{

System.out.println("no elements inserted");

System.exit(0);

}

System.out.println("****************************************************************************");

int a[]=new int[s.length()];

char b1[]=s.toCharArray();

char b2[]=new char[b1.length];

for (i = 0; i <>

b2[i] = ("" + (i + 1)).charAt(0);

Arrays.sort(b1);

for(i=0;i

mi=mi+1;

ma=ma+s.length();

}

min=Integer.parseInt(mi);

max=Integer.parseInt(ma);

for(i=min;i<=max;i++)

{bo=true;

t=""+i;

t1="";

char b3[]=t.toCharArray();

for(j=0;j

{bo2=false;

for(k=0;k

if(b3[j]==b2[k])

{

bo2=true;

break;

}

if(!bo2)

bo=false;

}

if(!bo)

continue;

else{

for(j=0;j

System.out.print(b1[Integer.parseInt(""+t.charAt(j))-1]);

System.out.println();

}

}

}}

other solution generating permutations without repeated elements

import java.io.*;

import java.util.*;

class gpint2{

public static char a[]=null;

public static void main(String args[])throws Exception{

BufferedReader b=new BufferedReader(new InputStreamReader(System.in));

System.out.println("enter the elements of set whose permutations are to be generated");

a = (b.readLine()).toCharArray();

Arrays.sort(a);

System.out.println("************GENERATED PERMUTATIONS*****************");

perm(0);

}

public static void perm(int i)

{char t='*';

int j = 0;

for (int n = i; n <>

{

if (i == n)

print();

else

{

for (j = i+1; j <>

{ t = a[i];

a[i]=a[j];

a[j] = t;

perm(i + 1);

t = a[i];

a[i] = a[j];

a[j] = t;

}

}

}

}

public static void print()

{

for (int i = 0; i <>

System.out.print(a[i]);

System.out.println();

}

}

BigInteger Tutorial (java.math.BigInteger)

BigInteger Tutorial

From a long time I was wondering what should be my next blog topic…..since in last few months I used lot of java.math.BigInteger class in most of my programs that’s why I have decided to write a small tutorial for it…. So here we go

You might be aware of the total storage capabilities of different data types which are used to store integer values in java … to brush up you can have a look at following grid (u can skip this section :) )

Java stores all integers in memory as binary numbers.

type	Size		Range
name	bytes	bits
byte	1	8	-128 to +127
short	2	16	-32768 to +32767
int	4	32	-2147483648 to to +2147483647
long	8	64	9223372036854775808 to +9223372036854775807

[Source: http://leepoint.net/notes-java/data/basic_types/21integers.html]

There may be cases when we are interested in computation involving the numbers >2⁶⁴ so what data type should we use in that case. Java (I think 1.4.2 and higher) package comes with a BigInteger class which is designed to perform normal mathematical operation on 20-21 digit number or even high…..

Now in order to instantiate BigInteger class we can use any of the constructors specified in the following program

import java.math.BigInteger;

class Btest

{

public static void main(String args[])

{//1.BigInteger(byte[] val)

byte a[]={1,2,3,4};

BigInteger a1=new BigInteger(a);

System.out.println( a1);

/*2.BigInteger(int signum, byte[] magnitude) used to translate the sign magnitude of the BigInteger into BigInteger

signum - signum of the number (-1 for negative, 0 for zero, 1 for positive).

magnitude - big-endian binary representation of the magnitude of the number. */

BigInteger a2 = new BigInteger(1, a);

System.out.println( a2);

/*3.BigInteger(String val,int radix)

translates the String representation of BigInteger in the specified radix into a BigInteger

one can use optional minus "-"sign in the string parameter

*/

BigInteger a3 = new BigInteger("346433", 10);

System.out.println(a3);

/*4.BigInteger(String val)

translates decimal representation of a bigInteger specified in the string into corresponding BigInteger

*/

BigInteger a4=new BigInteger ("1231431543534");

System.out.println(a4);

/*5.BigInteger(int numBits,Random rnd)

this constructor generates a random BigInteger within interval [0,anitlog(numbits*log2)-1 ] */

java.util.Random r=new java.util.Random ();

BigInteger a5 = new BigInteger(32, r);

System.out.println(a5);

/*BigInteger(int bitLength,int certainty,Random rnd)

this constructor specifications leads to a randomely generated BigInteger which is probabaly prime.

Paramater bitlength specifies the bitlength of the desired BigInteger .

Parameter certainity specifies the certainity that could be tolerated by the caller

Parameter rnd is the source of random bits used to select candidates to be tested for primality.

*/

BigInteger a6 = new BigInteger(8, 56, r);

System.out.println(a6);

//Some other initialization techniques

BigInteger a6 = new BigInteger(8, 56, r);

System.out.println(a6);

BigInteger a7 = BigInteger.ONE;//can also use BigInteger.ZERO

System.out.println(a7);

BigInteger a8=BigInteger.valueOf(54353263);

System.out.println(a8);

}

}

OUTPUT

16909060

16909060

346433

1231431543534

94655163

191

1

54353263

Now we come to various methods which could be applied on BigInteger Objects. I have a written following program which involves most of the BigInteger methods however there a some more methods which are not given in program .You can get their detail here

import java.math.BigInteger;

class Btest1

{

public static void main(String args[])

/*--------------------------------Arithmetic and logical Methods--------------------------------*/

BigInteger x =BigInteger.valueOf(10);

BigInteger y = BigInteger.valueOf(8);

//add

x = x.add(BigInteger.valueOf(4));

x = x.add(y);

System.out.println(x);

//subtract

x = x.subtract(BigInteger.valueOf(4));

x = x.subtract(y);

System.out.println(x);

//divide

x = x.divide(BigInteger.valueOf(1));

x = x.divide(y);

System.out.println(x);

//multiply

x = x.multiply(BigInteger.valueOf(1));

x = x.multiply(y);

System.out.println(x);

//remainder

x = x.remainder(BigInteger.valueOf(4));

x = x.remainder(y);

System.out.println(x);

//divideAndRmainder

x = BigInteger.valueOf(43);

BigInteger s[] = new BigInteger[2];

s = x.divideAndRemainder(BigInteger.valueOf(5));

System.out.println("x/5="+s[0]+" "+"x%5="+s[1]);

s = x.divideAndRemainder(y);

System.out.println("x/y=" + s[0] + " " + "x%y=" + s[1]);

/*methods for Comparison */

//equals :returns true if parameter is equal to specified BigInteger

System.out.println (x.equals(BigInteger.valueOf(43)));

System.out.println (x.equals(y));

/*comapreTo :returns -1,0,1 depending on the value give as parameter is lesser than

,equal to,greater than the BigInteger for which the method is used */

System.out.println(x.compareTo(BigInteger.valueOf(42)));

System.out.println(x.compareTo(BigInteger.valueOf(43)));

System.out.println(x.compareTo(BigInteger.valueOf(44)));

//toString :used for String conversion

System.out.println(x.toString());

//to print corresponding byte,int,double,float,short value

System.out.println(x.byteValue());

System.out.println(x.doubleValue());

System.out.println(x.intValue());

System.out.println(x.floatValue());

System.out.println(x.shortValue());

byte x2[] = x.toByteArray();

for (int h=0;h

System.out.println(x2[h]);

/*isProbablePrime :returns true if the given BigInteger is prime ,

returns false if the given BigInteger is composite one has to menation integer value as the

parameter ,this integer value called "certainity" gives the measure of uncertainity which could be

tolerated */

System.out.println(x.isProbablePrime(23));

//pow :for raise to the power operation

System.out.println(x.pow(45));

//abs :used to return the absolute value

System.out.println(x.multiply(BigInteger.valueOf(-1)) + " " + x.multiply(BigInteger.valueOf(-1)).abs());

//negate returns -1*BigInteger

System.out.println(x.negate() + " " + x.multiply(BigInteger.valueOf(-1)).negate());

//hashCode:returns hashcode for the given BigInteger

System.out.println(x.hashCode());

//signm :Returns the signum function of the BigInteger.

System.out.println(x.signum());

/*------------------------------Bit Methods------------------------------*/

//shiftLeft

System.out.println(x.shiftLeft(4));

//shiftRight

System.out.println(x.shiftRight(4));

//bitCount returns the number of bits in two's complement notation apart frm the sign bit

System.out.println(x.bitCount());

//bitLength :returns the number of bits in minimal two's complement notation leaving the sign bit

System.out.println(x.bitLength());

//getLowestSetBit :returns the index of righmost one bit in the given BigInteger

System.out.println(x.getLowestSetBit());

//and

System.out.println(x.and(y));

//or

System.out.println(x.or(y));

//xor

System.out.println(x.xor(y));

//andNot

System.out.println(x.andNot(y));// returns x&~y

//not

System.out.println(x.not());

//testBit :returns true if designated bit is set

System.out.println(x.testBit(4));//test if ((x&(1<<4))!=0)>

/*setBit :returns a BigInteger which is generated by setting the specified bit of

the equivalent bit representation of Given BigInteger*/

System.out.println(x.setBit(4));// calculates x | (1<<4)

/*clearBit: returns a BigInteger which is generated by clearing the specified bit of

the equivalent bit representation of Given BigInteger*/

System.out.println(x.clearBit(4)); //calculates x&~(1<<4)

/*flipBit:returns a BigInteger which is generated by flipping the specified bit of

the equivalent bit representation of Given BigInteger*/

System.out.println(x.flipBit(4));//calculates x^~(1<<4)

}

}

OUTPUT

22

10

1

8

0

x/5=8 x%5=3

x/y=5 x%y=3

true

false

1

0

-1

43

43

43.0

43

43.0

43

43

true

32068636955638964644302091603013447460711607634633358021240791550942692443

-43 43

-43 43

43

1

688

2

4

6

0

8

43

35

35

-44

false

59

43

59

Till now you would be able to use the BigInteger class as per your needs .Following is a small code which I wrote to calculate the factorial of large values and store it in a text file generated at at C drive C:/fact.txt I have calculated the value of 40000!..which is incredibly huge …lol and uploaded the generated file here

import java.io.*;

import java.math.BigInteger;

class ffact

{

public static void main(String args[])throws Exception

{

BufferedReader b = new BufferedReader(new InputStreamReader(System.in));

System.out.println("enter a value");

BigInteger a = new BigInteger(b.readLine());

BigInteger a1 = BigInteger.valueOf(1),a2=BigInteger.valueOf(1);

for (a1 = BigInteger.valueOf(1); a1.compareTo(a) <= 0; a1 = a1.add(BigInteger.valueOf(1)))

a2 = a2.multiply(a1);

File f2 = new File("c:/fact.txt");

if (!f2.exists()) f2.createNewFile();

PrintWriter p = new PrintWriter(new BufferedWriter(new FileWriter(f2.getAbsolutePath())));

p.println(a2);

p.close();

}

}

Anyways its 2:10 am … i guess I need some sleep now …hope I’ll come wid a new topic soon thinking to come up with internal working of BigInteger class next time Or I’ll come up wid some other topic …..