Hi everyone! I am glad to announce that Zalando CodeSprint on HackerRank is scheduled on June 4, 2016, 12:00 PM CEST. Contest duration is 24 hours, but don't be scared by that. There will be 8 problems to solve.

Sign up here: https://www.hackerrank.com/zalando-codesprint

The prizes are:

• Rank 1: Pebble Watch, 200 Euro gift voucher of your choice, Hackathon Hoodie
• Rank 2-5: 200 Euro gift voucher of your choice, Hackathon Hoodie
• Rank 6-20: Hackathon Hoodie

Last SRM's div1-250-task raised two questions:

• how to calculate square root of a perfect square?
• how to do a perfect square test?

The following two methods solve these problems correctly in Java:

• long rootOfPerfectSquare(long xx) { return (long) Math.sqrt(xx); }

• boolean isPerfectSquare(long xx) { long x = (long) Math.sqrt(xx); return x * x == xx; }

What makes correctness non-obvious is implicit conversion of Math.sqrt() argument from long to double, where precision can be lost.

Correctness can be verified using the following code:

for (long x = 0; x <= Math.sqrt(Long.MAX_VALUE); x++)
    if (x != (long) Math.sqrt(x * x)) System.out.println(x);

Is there any explanation of why it works?
Does this method work in other languages, e.g. C++?

Can you prove or disprove the following statement: for any long x >= 0: (long) Math.sqrt(x) ?

The following code crashes Java8 on Codeforces:

public class Main {
    public static void main(String[] args) {
        java.math.BigInteger.valueOf(7).nextProbablePrime();
    }
}

http://mirror.codeforces.com/contest/427/submission/6539822

Maybe updating Java8 will solve the problem.

Hi. For those who like to solve CodeJam in multiple programming languages, here https://github.com/indy256/codejam-templates is a collection of templates which reveal basic language constructs.

Currenly there are 8 single-threaded templates in Java, C++, Ruby, Python, JavaScript, etc.

Contribution of additional languages is welcomed.

This post is about a simple way to operate on combinatorial sequences such as permutations, combinations, partitions, correct bracket sequences, etc., assuming O(n²) or in some cases O(n³) time complexity per operation is acceptable (n — sequence length).

To refresh your knowledge here are all 3-combinations of 4 elements: 012, 013, 023, 123. And here are all correct bracket sequences of size 6: ((())), (()()), (())(), ()(()), ()()().

The common tasks solved on combinatorial sequences are the following:

1. calculate total number of sequences
2. generate all sequences
3. given a sequence, find the next to it (like next_permutaion() in C++ STL)
4. given a sequence, calculate its number
5. given a sequence number, construct the sequence itself

This post is about memory requirements for fast range queries.

First, let's consider 2 following types of queries on a sequence x[0]..x[n-1] in O(logn):

• sum(a, b) — calculate x[a] + x[a+1] + ... + x[b]
• add(i, value) — x[i] += value

This is a well-known problem that can be solved using Fenwick tree.

What is good with Fenwick tree — is that it gives memory-optimal solution in the sense that it needs an array of only n elements, where each element has enough capacity to store any sum(a,b). Unlike Fenwick tree, any solution based on segment tree will use at least 2*n elements.

Now suppose we need range update and our query types become the following:

• sum(a, b) — calculate sum x[a] + x[a+1] + ... + x[b]
• add(a, b, value) — x[a]+=value x[a+1]+=value ... x[b]+=value

This is most often solved using segment tree with 2 arrays (something like sum[] and delta[]), each of 2*n or 4*n size. So the minimum memory consumption is 4*n which is far from optimal n.

We can improve. It was discovered that Fenwick tree can be altered to support both range queries and updates. All following solutions use 2*n elements:

• Petr blog: http://petr-mitrichev.blogspot.ru/2013/05/fenwick-tree-range-updates.html
• Topcoder forums: link1 link2
• habrahabr.ru (russian only): http://habrahabr.ru/post/170933/

Several recent problems on Codeforces concerned dynamic programming optimization techniques.

The following table summarizes methods known to me.

Name	Original Recurrence	Sufficient Condition of Applicability	Original Complexity	Optimized Complexity	Links
Convex Hull Optimization1		b[j] ≥ b[j + 1] optionally a[i] ≤ a[i + 1]	O(n2)	O(n)	1 2 3 p1
Convex Hull Optimization2	dp[i][j] = mink < j{dp[i - 1][k] + b[k] * a[j]}	b[k] ≥ b[k + 1] optionally a[j] ≤ a[j + 1]	O(kn2)	O(kn)	1 p1 p2
Divide and Conquer Optimization	dp[i][j] = mink < j{dp[i - 1][k] + C[k][j]}	A[i][j] ≤ A[i][j + 1]	O(kn2)	O(knlogn)	1 p1
Knuth Optimization	dp[i][j] = mini < k < j{dp[i][k] + dp[k][j]} + C[i][j]	A[i, j - 1] ≤ A[i, j] ≤ A[i + 1, j]	O(n3)	O(n2)	1 2 p1