Most of us are familiar with google codejam, those who don’t visit https://code.google.com/codejam for more information. This is the first problem from Online Round 1B 2013, top 1000 from this round will be eligible for next online round.
Problem Statement
Armin is playing Osmos, a physics-based puzzle game developed by Hemisphere Games. In this game, he plays a “mote”, moving around and absorbing smaller motes.
A “mote” in English is a small particle. In this game, it’s a thing that absorbs (or is absorbed by) other things! The game in this problem has a similar idea to Osmos, but does not assume you have played the game.
When Armin’s mote absorbs a smaller mote, his mote becomes bigger by the smaller mote’s size. Now that it’s bigger, it might be able to absorb even more motes. For example: suppose Armin’s mote has size 10, and there are other motes of sizes 9, 13 and 19. At the start, Armin’s mote can only absorb the mote of size 9. When it absorbs that, it will have size 19. Then it can only absorb the mote of size 13. When it absorbs that, it’ll have size 32. Now Armin’s mote can absorb the last mote.
Note that Armin’s mote can absorb another mote if and only if the other mote is smaller. If the other mote is the same size as his, his mote can’t absorb it.
You are responsible for the program that creates motes for Armin to absorb. The program has already created some motes, of various sizes, and has created Armin’s mote. Unfortunately, given his mote’s size and the list of other motes, it’s possible that there’s no way for Armin’s mote to absorb them all.
You want to fix that. There are two kinds of operations you can perform, in any order, any number of times: you can add a mote of any positive integer size to the game, or you can remove any one of the existing motes. What is the minimum number of times you can perform those operations in order to make it possible for Armin’s mote to absorb every other mote?
For example, suppose Armin’s mote is of size 10 and the other motes are of sizes [9, 20, 25, 100]. This game isn’t currently solvable, but by adding a mote of size 3 and removing the mote of size 100, you can make it solvable in only 2 operations. The answer here is 2.
Input
The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case gives the size of Armin’s mote, A, and the number of other motes,N. The second line contains the N sizes of the other motes. All the mote sizes given will be integers.
Output
For each test case, output one line containing “Case #x: y”, where x is the case number (starting from 1) and y is the minimum number of operations needed to make the game solvable.
Limits
1 ≤ T ≤ 100.
Small dataset
1 ≤ A ≤ 100.
1 ≤ all mote sizes ≤ 100.
1 ≤ N ≤ 10.
Large dataset
1 ≤ A ≤ 106.
1 ≤ all mote sizes ≤ 106.
1 ≤ N ≤ 100.
Sample
| Input | Output |
4 |
|
Notes
Although the size of motes is limited in the input files, Armin’s mote may grow larger than the provided limits by absorbing other motes.
Osmos was created by Hemisphere Games. Hemisphere Games does not endorse and has no involvement with Google Code Jam.
Osmos problem Google codejam Online Round 1B 2013 solution with explanation
At any point of time, if current mote is bigger than next mote, we can eat it immediately without any extra moves. If we are smaller we should get the number of operations required to become > next mote size. Also, at any point of time, Number of extra moves required can not be greater than total number of motes, as to begin with, we can remove them all.
Here is the Java code for Osmos problem in Google codejam Online Round 1B 2013
package googlecodejam2013;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.Reader;
import java.util.ArrayList;
import java.util.Collections;
public class Osmos {
private static int moteAfterOperations = 0;
public static int getMinimumOperations(int mote, ArrayList<Integer> moteList){
int operations =0;
int totalMotes = moteList.size();
if(mote == 1){//Special case: as here we cant add any motes, so remove all the motes
return totalMotes;
}
Collections.sort(moteList);
int count =0;
for(int nextMote: moteList){
count++;
int temOperations = getOperations(mote, nextMote);
// If required operations are greater than or equal to remaining motes,
// remove all remaining motes
if(temOperations >= totalMotes -count+1){
int temp= operations+(totalMotes -count+1);
// This check is very important, my submission was InCorrect because of this check.
if(temp > totalMotes){
temp = totalMotes;
}
return temp;
}
if(temOperations > 0){
operations += temOperations;
mote = moteAfterOperations;
}
mote = mote + nextMote;
// At any point of time if number of operations is greater than total number of motes,
// return total number of motes, as we can remove them all to begin with
if(operations >= totalMotes){
return totalMotes;
}
}
return operations;
}
/*
* Returns the number of operations required to become > nextMote
*/
private static int getOperations(int mote, int destMote){
int ret = 0;
while(destMote >= mote){
ret ++;
mote += (mote-1);
moteAfterOperations = mote;
}
return ret;
}
public static void main(String[] argv) {
try {
long startTime = System.currentTimeMillis();
Reader reader = new FileReader("sample.in");
BufferedReader bufReader = new BufferedReader(reader);
String x = bufReader.readLine();
int numOfTestCases = Integer.parseInt(x);
int count = 0;
File file = new File("Sample.out");
FileWriter writer = new FileWriter(file);
for(count =1; count<= numOfTestCases; count++) {
ArrayList<Integer> firstLine = getIntegerList(bufReader.readLine());
ArrayList<Integer> secondLine = getIntegerList(bufReader.readLine());
String output = getMinimumOperations(firstLine.get(0), secondLine)+"";
writer.write("Case #" + count + ": " + output+"\n");
System.out.println("Case #" + count + ": " + output);
}
writer.close();
System.out.println("Total time = " + (System.currentTimeMillis() - startTime));
} catch (Exception e) {
e.printStackTrace();
}
}
private static ArrayList<Integer> getIntegerList(String s) {
ArrayList<Integer> intList = new ArrayList<Integer>();
String[] strArr = s.split(" ");
for (String str : strArr) {
intList.add(Integer.parseInt(str.trim()));
}
return intList;
}
}
