There is a section explaining the scoring system in the FAQ. ( https://code.google.com/codejam/resources/faq )

They take in consideration your earliest attempt that passed the visible tests, and your latest attempt, and give you points/penalty based on the better of the two.

So for your examples, you would get +1 penalty in Case 1, and get no penalty in Case 2.

3 -2 3 -2 1 2 1

Answer: 2

The constraints are small enough that you can just simulate reading every page. No need for some fancy solution :)

EDIT: I forgot that div1 exists, my mistake... :)

Because of symmetry, you can fix the first vertex of the angle, and itterate the other 2 vertices. To avoid O(N^2) complexity, you can only itterate the second vertex, and find the optimal third vertex using binary-search. All you need is a function that calculates the angle of 3 given vertices in a regular n-gon.

I solved it by checking the length of the interval, and if the interval is small (say R-L <= 100) then I brute-force the solution with simulation, and if the interval is bigger, I just calculate the worst case and print that.

To maximize bananas, you always want the bottom left point of the rectangle to be at point (0, 0). All that's left to do is find the upper right point of the rectangle.

the line intercepts the Y-axis in the value b, so you have at most 10000 possible y values for that point. Iterate through all those 10000 y values and find the maximum value for x at that y by solving y = -x/m + b for x and rounding down the solution to an integer value.

You also need a count_bananas function that for given x and y of the upper right point of the rectangle calculates the number of bananas in the rectangle. the formula for this is:

(sum from 0 to x) * (y + 1) + (sum from 0 to y) * (x + 1).

So you just iterate every possible y value, find the corresponding x value, and calculate the number of bananas for that pair, and print the max bananas at the end. At least this is how I solved it, there might be a better O(1) solution using math.

I think complexity of 100M (10^8) should be able to pass in 2 seconds. That's only 50M in a second which is passable.

Of course it depends on the code and language, but generally it should pass. I've seen some optimized codes where complexity of 100M passes in one second.

So you suggest using arraylist to solve this problem? I think that approach also has some downsides since the elements aren't together in memory, and it still has the same problem of wrapping and unwrapping Integer objects. As far as I know there are three workaround to the problem:

-use Integer[] arr instead of int[] arr.

-use ArrayList

-use int[] arr, but do a random shuffle on the elements before sorting.

Personaly, I don't think using Integer[] instead of int[] is such a big problem.

DP on trees? If you are reffering to div1A, it was just a matter of finding all edges that connect vertices of different color, and seeing if all those edges share a same vertex.

Just count the sum of ones, and if the sum is even, add 1 to the answer (you need to flip 1 bit), if the sum is odd it's ok.

The sum of the flips has to be odd because once you make 1 cycle, if the flips are odd, the next cycle every piece will be flipped, but if the sum is even, they will pass every cycle with same orientation.

Sets by definition don't keep duplicates (duplicate keys in this case). So when you put (a, a) the value a is mapped to key a, and then when you put (a, b), the old value for key a is erased and overwritten as b.

You probably didn't do the divisions in half. I had WA test 8 as well until I fixed that.

Both of you are developing problem solving skills, mathematical thinking, tenacity, etc, but he is doing so while advancing human knowledge while you are solving problems that already have known solutions.

By studying algorithms and data structures you can advance human knowledge too. Finding some undiscovered shortcut for solving TSP, or discovering some new data structure that can handle big data in particular ways can have big practical impacts. I really don't get how you can say that studying math theory can be very useful while studying cs theory is a waste of time...

My approach was, first I split all N numbers in two queries by taking groups of 1:

1 3 5 7 9... and 2 4 6 8 10...

then I take groups of 2:

1 2 5 6 9 10... and 3 4 7 8 11 12...

then take groups of 4:

1 2 3 4 9 10 11 12... and 5 6 7 8 13 14 15 16...

and so on.

With this queries you can test every element in the matrix, and get the minimums.

Here's a java code that I've written that does this. However I don't really understand the algorithm, I just implemented the pseudo-code that I found in the original source (Computing Binomial Coefficients, P. Goetgheluck). You can look it up if you are interested in how it works.

http://pastebin.com/ev1g3hb7

My greedy solution passed the sys tests (to my surprise). I put all numbers in a binary tree, and then i repeat this:

1) remove the max element from the tree

2) divide that element by 2

3) check if this number is already in the tree, if it isn't put it in the tree, and go to 1), else continue dividing by going to 2) while the number is bigger than 0.

When a number can't be inserted in the tree with this algorithm (i.e. you keep dividing untill you reach 0) break from the loop, and print all the contents in the tree.

Before you hack, you need to lock your solution to the problem you wish to hack. You can hack by going to your room, and double clicking on someone's solution that you wish to hack. Then you see their code, and if you think their code is wrong and doesn't work for all cases, you can click on the button hack, and give a test case for which you think the solution would produce wrong answer. If you are correct, you gain +100 points, if you are wrong you lose 50 points.

Here's a hack case for your code.

6 3 ab ac abc abd abcd abcf abcd

The 5 sec pause that happens after k tries should be calculated globaly, but you are calculating it inside of the loop, and you get inaccurate results when the division isn't exact (in this case the count of sz[2], sz[3] and sz[4] is 2, and k=3, so the division always returns 0, but if you calculate it globally, it would be (6-1)/2 = 1 pause)

Every pythagorean triple (a, b, c) can be written as:

a = m^2 — n^2

b = 2mn

c = m^2 + n^2

for some integers m and n.

From here, it's only a matter of finding a combination of integers m and n that will satisfy one of the three equations and then just substituting to find the other 2 sides.

For example if the given side is even, it can always be substituted in the b equation where m = 1, and n = b/2. And if the given side is odd, it can be substituted in the a equation: a = (m^2 — n^2) = (m-n)(m+n) ==> 1*a = (m-n) * (m+n) ==> m-n = 1 and m+n = a.

The problem statements were really ambiguous. Even if we ignore the mistake in English statement A that was wrong for whole 10 mins, and made the problem unsolvable for English reading coders, why did you feel the need to include: "but not necessarily it should be the last one". It adds no clarification or help to the problem, and only confuses the competitors.

And for problem B, you should've specified that we should use the pictured alphabet to determine what the mirror images of certain characters are. Since it really depends on the font we use. For example: the letter l in some fonts mirrors it self, but here it doesn't, the same happens with the letter i.

You probably forgot the backwards paths from point i to point i-1. I had the same mistake :)

Long.MAX_VALUE should be a safe bet I think.

If a tree has n nodes, then the centroid of that tree is a node such that when you remove that node (and its edges), the remaining graphs that are left from the tree all have at most n/2 nodes.

You can just sort the animals with bubble sort, and just print all the swaps you do. Since bubble sort has complexity n^2 it is guaranteed to do no more than n^2 swaps. From the constraints of the problem, the maximum value for n is 100, so the bubble sort will do at most 10000 swaps (less than that really, but it doesn't matter). So you are always guaranteed to make less than 20000 swaps.

Any info on the T-shirt winners?

I just sent the same solution but with ArrayList instead of int array, and it passed. Are Collections.sort() and Arrays.Sort() different?

EDIT: nvm, I read that sorting primitives is in quick sort, while sorting objects is in merge sort. Hmm a weird design choice if you ask me...

Is B even solvable in Java? My solution was literally the same as the solution in the editorial. I even modified it to use BufferedReader and String.split(" ") and it still fails on the last test case...

Any ideas how to speed up the input?