indy256's blog

By indy256, 8 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +32
  • Vote: I do not like it

By indy256, 10 years ago, In English

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) ?

Full text and comments »

  • Vote: I like it
  • +21
  • Vote: I do not like it

By indy256, 11 years ago, In English

The following code crashes Java8 on Codeforces:

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

http://codeforces.me/contest/427/submission/6539822

Maybe updating Java8 will solve the problem.

Full text and comments »

  • Vote: I like it
  • +27
  • Vote: I do not like it

By indy256, 11 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +16
  • Vote: I do not like it

By indy256, 11 years ago, In English

This post is about a simple way to operate on combinatorial sequences such as permutations, combinations, partitions, correct bracket sequences, etc., assuming O(n2) or in some cases O(n3) 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

Full text and comments »

  • Vote: I like it
  • +83
  • Vote: I do not like it

By indy256, 11 years ago, In English

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:

Full text and comments »

  • Vote: I like it
  • +40
  • Vote: I do not like it

By indy256, 11 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +388
  • Vote: I do not like it