Google Code Jam - Java help

dlane99

I just tried to do the google code jam and got on lousy.
http://www.google.com/codejam/ (registration is closed.).
I tried the 250 point question and only got 96 points.
I cant figure out what i did wrong.
the problem statement is below along with my attempt.
If the input was 6 it would return 5 which was correct,
but the last example, the input was 1000 and it was suposed to return 64 but
it returned 65.
Its bugging me where i went wrong.

Any1 see the problem?
Thanks.

Problem Statement


Alex has a lot of contacts in his Hyper Instant Messenger (HIM), and therefore, it takes some time to find the right contact. HIM supports Contact Groups, and each contact can be placed into a group. However, HIM's group support is rather limited. It allows for only one of the following two scenarios: 1) Multiple groups, but every contact belongs to a single group, or 2) All contacts exist only in a global contacts list (and no groups are created).

It takes Alex k seconds to find an entry in any list of k entries. If groups exist, HIM will first show a list of all the groups, and once a group is selected, a list of all contacts within that group will be displayed. If groups do not exist, HIM will simply show a single list containing all the contacts in the global list. For example, if Alex has 5 contacts in the global list, it will take 5 seconds to find any one of them. If Alex splits those contacts into two groups with 2 and 3 users each, it will first take him 2 seconds to find the right group, and then 2 or 3 seconds to find the right contact depending on which group he chooses.

You will be given an int N representing the total number of contacts. Arrange the contacts optimally (either in one global contacts list or in several groups) such that the maximal time needed to find a contact is minimized. Return this time.
Definition

Class: IMGroups
Method: optimalTime
Parameters: int
Returns: int
Method signature: int optimalTime(int N)
(be sure your method is public)


Constraints
- N will be between 1 and 1000000, inclusive.
Examples
0)


5

Returns: 5

The example from the problem statement.
1)


6

Returns: 5

Alex can arrange the contacts into 2 groups with 3 contacts each. The total time needed to find any contact will be 2 seconds to find the right group plus 3 seconds to find the right contact within that group.
2)


1000

Returns: 64


My attempt:

public class IMGroups {
 public int optimalTime(int N) {
  int maxTime = N;
  int groups, members, newTime = 0;
  for (int i = 1; i < N; i++) {
   groups = i;
   members = N/i + N%i;
   newTime = groups + members;
   if(newTime < maxTime) {
    maxTime = newTime;
   }
   if(groups > maxTime) {
    break;
   }
  }
  return maxTime;
 }
}

pH

Any1 see the problem?

members = N/i [b]+ N%i[/b];

dlane99

pH wrote:

members = N/i [b]+ N%i[/b];

i appreciate the input.
not to be rude or anything but it would help if you gave the logic behind your input.

members / groups gives the number of members per group.
add the remainder is added cos one group ....

oh, i think i get what your saying.

i was adding all the remaining members to one group where as i should have spread em
out over the remaining groups?

thanks, will test it when i get a chance.

dlane99

I tested it and it works.
Thanks.
That was a stupid mistake to make.
Wasted 45 min of the hour looking for that bug.
ah well.
thanks again Ph.

pH

dlane99 wrote:

oh, i think i get what your saying.

i was adding all the remaining members to one group where as i should have spread em
out over the remaining groups?

thanks, will test it when i get a chance.

There you go.

Also if I may ...
The fundamental approach ... is it not obvious that you don't need to check all possible groups, the optimal solution is always going to be having the number of groups set to the square root of the number of contacts?

dlane99

pH wrote:

There you go.

Also if I may ...
The fundamental approach ... is it not obvious that you don't need to check all possible groups, the optimal solution is always going to be having the number of groups set to the square root of the number of contacts?

Nope, didnt cop that.
I considered checking the square root briefly,
but decided that checking all possibilities was safer.
well, not all possibilities.
I checked up untill the number of groups was larger than the current maxTime.

that was the 250 point q.

incase anyone wants to see the 750 point q here it is:
i have no desire to attempt it.

Problem Statement
You are given a square chessboard, and you must determine the number of ways you can place k bishops on the board so that no two bishops attack each other. Some of the cells on the board are destroyed, and a bishop cannot be placed on a destroyed cell. Two bishops attack each other if they are located on the same diagonal (even if there are destroyed cells between them).

You will be given a String[] board which represents the chessboard. The jth character of the ith element of board represents the cell at row i, column j. A '.' denotes an empty cell, and a '#' denotes a destroyed cell. Return the last four digits of the number of ways you can place k bishops on the board so that no two bishops attack each other.
Definition

Class: Bishops
Method: count
Parameters: int, String[]
Returns: int
Method signature: int count(int k, String[] board)
(be sure your method is public)

Constraints
- k will be between 0 and 64, inclusive.
- board will contain between 1 and 8 elements, inclusive.
- Each element of board will contain exactly n characters, where n is the number of elements in board.
- Each character of each element of board will be either '.' or '#'.
Examples
0)


1

{"."}

Returns: 1

1)


1

{
"...",
".##",
"..."}

Returns: 7

There are 7 free cells, and the bishop can be placed in any of those cells.
2)


3

{
"...",
"...",
"..."}

Returns: 26

3)


7

{
"........",
"......#.",
"........",
".#......",
"........",
".....#..",
"........",
"...#...."}

Returns: 5544

4)


4

{
"...",
".#.",
"..."}

Returns: 8

There are two basic possible placements of 4 bishops:

BBB B.B
.#. B#B
.B. ...

and the rotations of these two placements.
5)


0

{
"...",
"###",
"..."}

Returns: 1

There is exactly one way of placing 0 bishops.
6)


2

{
"....",
"....",
".#..",
"...#"}

Returns: 71

Talisman

The second problem is easier than you think. There are polynomial functions to calculate the number of ways that k non-attacking chess pieces can be placed on an M x N chessboard. There's a function for each of the pieces. In your case M and N are both the same and are in the range of 1..8, so you could code the function in to your solution or you could search the internet for the values and stick them in an array.

Then you are left with the easier problem of calculating how many solutions that the destroyed squares would affect and subtract that from the value you already have.