indy256's blog

By indy256, 14 months 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

Read more »

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

By indy256, 3 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) ?

Read more »

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

By indy256, 3 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.ru/contest/427/submission/6539822

Maybe updating Java8 will solve the problem.

Read more »

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

By indy256, 3 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.

Read more »

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

By indy256, 4 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

Read more »

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

By indy256, 4 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:

Read more »

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

By indy256, 4 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
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

Read more »

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

By indy256, 4 years ago, In Russian,

Невозможно просмотреть некоторые исходники, например http://codeforces.ru/contest/86/submission/466916

Это связано с временным ограничением части функционала ?

Read more »

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

By indy256, 5 years ago, In Russian,

Есть желание, чтобы архивы задач давали просматривать чужие решения. Естественно после того, как сам сдал задачу.

Просмотр чужих решений мог бы стать дополнительным стимулом решать архивы. К тому же в этом есть большая образовательная польза.

Чтобы исключить возможные проблемы с rejudge, просмотр исходников можно отключать для свежих (возраст менее года или двух) задач.

Вариант типа "попросить админа скинуть исходник", конечно, не устраивает.

Интересно, какие есть существенные основания у админов, чтобы не поддерживать такую опцию.

Такая фича могла бы стать хорошей рекламой и добавить посещений, что особенно актуально для откручивающих рекламу архивов типа spoj.

**UPD1:** Как заметил Bugman, есть проблема с рейтингом лучших (обычно по времени) решений.

Read more »

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

By indy256, 6 years ago, In Russian,

Поделитесь пожалуйста исходником для задачи E. Array Transformer

Read more »

Tags uva
 
 
 
 

By indy256, 7 years ago, In Russian,

У кого будет желание - напишите разбор тренировки.

В первую очередь интересно  D (как нужно было искать максимальный LCM), A, C, G.

Read more »

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