ACM ICPC 2011

Some rights reserved by Kiewic

Well, am not a blogger.... But few hings compel you to pen it all down somewhere.... ACM ICPC was surely one of them.
What is ACM ICPC?
Its an international programming contest. Association for Computing Machinery International Collegiate Programming Contest.

I represented my college Modern College Shivajinagar, Pune here

What is it all about?

Well, it all starts from here. Archis Gore(one of the project mentors on www.peepaal.org) in his Introduction wrote about this competition (check the 8th line...:P) . When I read about it, the term was itself completely new to me. So I googled it. I read, it is held every year in IIT Kanpur in the month of December.

Registration

 I had then planned that I will be going here come what may. I then checked for the eligibility and found out that last year the eligibility was students born on or after 1988 were eligible. I figured it out that next year its going to be 1989 or later, so with great regrets I closed the search (cos I wont be eligible then). But I told my friends who did fit in the criteria to apply for the same. Due to exam schedule no one could check for the same. So out of no where did it come to my mind on 9th October 2011 to check what was the last date to submit the names for the competition. I went to IIT Kanpur Website and found that again the eligibility was DOB 1988 or later. I jumped out of my bed!!! I was eligible. I called my friends and told them the same and started looking for the more details. And then came the next attack!!!! Registration for IIT Kanpur CLOSED. There was a link on the same website which took me to the international competition website. Here I came to know that the regional competition is held at many centers out of which one is Kanpur and the final is held at different locations in the world. This time its in Warsaw, Poland.

I thought for a while and made up my mind that I will go for the competition in some other center if not IIT Kanpur (I was under the impression that Kanpur was the only center for India). So I started looking for the same and found Dhaka as one of the centers…. And I said to myself… I m going there…:D but when I scrolled down I found Amritapuri as one of the centers. The name sounded Indian I googled it and I got it that it was in Kerala. Checked the last date of registration 9^th October 2011 before 5 pm IST. I got a shock. Had to register today itself before 5 pm. I already knew the registration process as I read it on Kanpur website. The registration process was that only a college teacher or faculty member who has a college domain email address (abc@moderncollegepune.com) can register. The teacher will register as a coach and will add students. Three team members and one reserve can be added. The beauty of the day was that it was a Sunday. So college closed. I called up my placement coordinator(Mrs. Manisha Suryawanshi) and told her the whole story. She told me that principal was available in college today (luckily) cos teacher’s interviews were conducted that day. Went to the college, spoke to the HOD there with his help somehow completed the registration by 4.30 pm unfortunately couldn't register a reserve member because he didn’t get his password on time. Finally, registration was accepted.

Online Competition

There was an online competition on 16^th October out of which they would select around 200 teams for regional. 780 teams were registered. Most of them were from IIT’s. The online exam seemed easy but wasn’t really so. There were 5 questions and there was an online compiler (they call it mooshak) where we were supposed to submit the answer. The competition was for 4 hours 9 am to 1 pm. So we started coding compiler to be used was strictly gcc and OS ubuntu Linux 8.0 (recommended) . The worst ever result we ever had we could solve only 1 out of 5 questions according to their needs. We actually solved 4 out of 5. but the other 3 were rejected on the grounds of space and time complexity. So with that 1 solved answer we got selected for the regional competition which was held on 10^th December 2011.The reason we got selected in spite of solving just one question was the selection procedure. The procedure is such that those teams who do not solve even a single questions are eliminated. Out of the remaining teams those teams(who solved at least one problem) selection would be made based on per Institutions registration. E.g if from XYZ College 10 teams have registered, the team which solved maximum problems will be selected. The selection criteria clearly states that, though it sounds unfair, this rule is implemented for the contest cause ICPC's goal is to bring many universities together. Only 1 team out of 200 teams was supposed to be selected for finals at Poland. The finals would be sponsored by IBM. The best part I saw was the team who wins the competition is sure to be placed in Google, Microsoft or IBM. Last years winners are in Google now.

Problems for Online Competition

Problem A: Numerology

Numerology is a difficult branch of magic, involving converting words and names to numbers, and deriving mystical significance from them. Harry Potter, our hero, has never had a good head for maths, being more at home killing evil wizards or playing Quidditch, but his Divination teacher at Hogwarts school of witchcraft has assigned him a numerology project for the Progcon ceremony. She has given him two integers A and B, and has asked him to list all the numbers in the range [A...B] inclusive that contain no digit that occurs more than twice in it, in decimal representation. Harry could not figure out a magic spell to do this task, but you can perhaps help him with your 'compooter thingy' that Muggles* use. You just have to find the number of integers in the range [A..B] that contain no digit that occurs more than twice in it, in decimal representation.

Input (STDIN):

The first line contains the number of test cases T. Each of the next T lines contains two integers, A and B.

Output (STDOUT):

Output T lines, one for each case containing the required answer for the corresponding case.

Constraints:

1 <= T <= 10000
1 <= A <= B <= 10^18
Time limit: 4 seconds

Sample Input:

3
100 120
1000 1000
123 456

Sample Output:

20
0
331

Problem B: Count Dracula

Vampires are supposed to enjoy counting so much that in old Europe they would scatter some rice in coffins when they buried people, so that if the corpses came awake at night and became vampires, they would be kept busy until morning counting the grains of rice.

But not all vampires are evil, and the one in the picture has promised to help Harry Potter fight Voldemort, the evil Dark Lord. But instead of learning the magic spells Harry has listed for him, our Count gets distracted and starts to count the letters in the spells.

Can you help the Count count the letters in the spells quickly so that he can move on to actually learning and memorizing the spells?

Constraints

The word will have at most 1000 characters.
Time limit: 1 second

Input (STDIN):

The input contains a single word containing only lower-case letters.

Output (STDOUT):

Output each character followed by its count, separated by a single space. The characters should appear in order 'a' to 'z', and only the letters having a positive frequency should be output. There should be no extra white space at the end of each line.

Sample Input:

helloworld

Sample Output:

d 1
e 1
h 1
l 3
o 2
r 1
w 1

Problem C: The Way to the Sorcerer's Stone

Harry Potter has discovered that the Sorcerer's Stone of Immortality is hidden in a dungeon. Having beaten the three-headed dog to get to the dungeon, Harry discovers to his dismay that the stone is stored at the end of a long crooked corridor with N-1 bends. At each bend in the corridor (and at the start) is either a Hungarian Horntail dragon that our intrepid hero has to defeat, or a flask of magic potion that his teacher Snape has left for him. A dragon at junction 'i' takes away |S[i]| strength points from him, and a potion at junction 'i' increases Harry's strength by S[i]. If his strength drops to 0 or less, Harry dies, and no magical stone can revive him.

Note that Harry could be faced with a corridor having no bends (N=1) -- just one single straight section with a flask or a dragon at the start.

Harry has used magic before entering the corridor to determine which bends contain what, but lacks the basic simple mathematical skill to determine what minimum strength he needs to emerge from the corridor alive. Can you help him again with your compooter-thingy?

Input (STDIN):

The first line contains the number of test cases T. T cases follow. Each test case consists of N in the first line followed by N space separated integers on the next line. If the ith value is negative, it indicates that the ith segment has a dragon, otherwise it indicates a magic potion.

Output (STDOUT):

Output T lines, one for each case containing the required answer for the corresponding case.

Constraints:

1 <= T <= 100
1 <= N <= 100
-100 <= S[i] <= 100
Time limit: 2 seconds

Sample Input:

3
3
0 0 -1
3
-2 -3 -4
4
2 -2 3 -3

Sample Output:

2
10
1

Problem D: Sub-sequences

Having discovered that the Muggle-born* students of Hogwarts School of Witchcraft & Wizardry are all on Facebook, Headmaster Dumbledore decided to go with the flow and has hired an ICPC World Finalist to teach all the students about this 'compooter-thingy' and how to program it to do its 'automatic spells'. Harry is struggling with his latest homework assignment, which is as follows:

You are given a sequence of N numbers A[1..N]. Consider a sub-sequence** such that the bitwise AND of all the numbers of the sub-sequence is equal to the bitwise OR of all the numbers of the sub-sequence. Amongst all such sub-sequences, find the sub-sequence that has the maximum sum of the numbers, and print this maximum sum.

Can you help Harry finish his homework before he chews through all his writing quills in frustration?

*Muggle-born: Magical children born of non-magical parents.

Input (STDIN):

The first line contains the number of test cases T. T cases follow. Each test case consists of N in the first line followed by N space-separated integers on the next line denoting the values A[1..N].

Output (STDOUT):

Output T lines, one for each case containing the required answer(maximum sum as explained in the problem) for the corresponding case.

Constraints:

1 <= T <= 20
1 <= N <= 10000
0 <= A[i] <= 10000
Time limit: 3 seconds

Sample Input:

2
3
1 2 3
2
1 1

Sample Output:

3
2

Problem E: Append to Divide

Honeydukes' Sweet Shop has donated buckets of Bertie Bott's Every Flavor Beans (a kind of jelly bean) to the students of Hogwarts School of Witchcraft and Wizardry, one basket per House. But when the baskets (each labeled with the House number i) were delivered to the school, it was discovered that the number of sweets in each bucket were not exactly divisible by the number of students in that house A[i], and quarrels broke out about who got the extra sweets.
Harry Potter to the rescue! Harry suggested using magic to make sure that every bucket contained a number of sweets that were exactly divisible by the number of students in the corresponding House.
Can you tell us how many sweets were in the last bucket, given the way Harry's spell worked:

Given the number of students A[i] in each of the N houses, we define the array B[0..N] as follows. Initialize B[0] = 1 and for i = 1 to N, set B[i] to the smallest integer obtained by appending one or more digits (0-9) to B[i-1] such that B[i] is divisible by A[i]. Find the value of B[N] modulo 1000000007.

Input (STDIN):

The first line contains the number of test cases T. T cases follow. Each test case consists of N in the first line followed by N space-separated integers on the next line denoting the values A[1..N].

Output (STDOUT):

Output T lines, one for each case containing B[N] % 1000000007.

Constraints:

1 <= T <= 10
1 <= N <= 1000
1 <= A[i] <= 1,000,000
Time limit : 3 secs

Sample Input:

2
3
2 3 4
4
1234 56789 12345 6789

Sample Output:

1020
681070756

ONSITE COMPETITION IN MY NEXT POST......