SRM 475, 300 point

RabbitStepping

The field size is at most 17, so we can solve this problem by bruteforce. We just need to try all possible initial combination and simulate the rabbit’s movement. To generate all possible initial combination, we can iterate from 0 to 2ⁿ-1 and work on its binary representation.

for ( int bit = 0; bit < (1 << n); bit++ ) {
  for ( int i = 0; i < n; i++ ) if ( bit & (1 << i) ) {
    // there's a rabbit at cell i
  }
}

Remember, the number of rabbit is r, so we should process only bit which has r hamming weight.

Hamming weight
Hamming weight of binary number is the digit sum of the binary representasion of a given number (the number of digit ‘1′ in its binary representation). For example, 11 in binary is 1011₂, so the hamming weight of 11 or h(11) is 3.

There are various method to calculate hamming weight.

int h(int n) {
  int ret = 0;
  while ( n != 0 ) {
    ret += n % 2;
    n  /= 2;
  }
  return ret;
}

or using bitwise operator…

int h(int n) {
  int ret = 0;
  while ( n != 0 ) {
    ret += (n & 1);
    n  >>= 1;
  }
  return ret;
}

The simplest one that I know is this:

int h(int n) {
  if ( n == 0 ) return 0;
  return 1 + h(n&(n-1));
}

The last one comes from an observation that n-1 will make the most right ‘1′ turn into ‘0′ and any digit that lies right to it become ‘1′. For example, 616 is 1001101000₂ and 615 is 1001100111₂. So n & (n-1) will erase one ‘1′ from n, ie. the right most one.

C/C++ also has this hamming weight (or population-count/popcount) implementation:

int x = __builtin_popcount(n);

I took only about 10-15 minutes to code this problem, but *damn* I spent more than 30 minutes to find bugs in my code T_T. By the time I submitted the solution, it was 15 minutes left before the contest end.

I didn’t manage to think any solution for 600pt, so I ended with 117.29 point till the end of the contest. Yeah, my rating goes down again (-11).

Here is my 300 code, the time complexity is O(2ⁿ * n * r):

#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
struct RabbitStepping { double getExpected(string field, int r); };
 
int h(int n) { return n ? 1+h(n&(n-1)) : 0; }
 
double RabbitStepping::getExpected(string field, int r) {
  double ret = 0.0;
  int n = field.size(), cnt = 0;
  REP(bit,1<<n) if ( h(bit) == r ) {
    cnt++;
    vector <int> move(r), prev(r);
    vector <int> pos;
    REP(i,n) if ( bit & (1 << i) ) pos.push_back(i);
    int s = n;
    while ( s > 2 ) {
      REP(i,pos.size()) if ( pos[i] != -1 ) {
        if ( pos[i] == 0 ) move[i] = 1;
        else if ( pos[i] == s - 1 ) move[i] = s - 2;
        else if ( pos[i] == s - 2 ) move[i] = s - 3;
        else if ( field[pos[i]] == 'W' ) move[i] = pos[i] - 1;
        else if ( field[pos[i]] == 'B' ) move[i] = pos[i] + 1;
        else if ( field[pos[i]] == 'R' && s == n ) move[i] = pos[i] - 1;
        else if ( field[pos[i]] == 'R' && s != n ) move[i] = prev[i];
      } else move[i] = -1;
      prev = pos;
      int rabbit[20] = {0};
      REP(i,move.size()) if ( move[i] != -1 ) rabbit[move[i]]++;
      REP(i,move.size()) if ( move[i] != -1 ) {
        if ( rabbit[move[i]] > 1 ) pos[i] = -1;
        else pos[i] = move[i];
      }
      s--;
    }
    REP(i,pos.size()) if ( pos[i] != -1 ) ret ++;
  }
 
  return ret / cnt;
}

fushar and agus.mw increases their rating and back to yellow, congratz to them

I decided to write this write up because of Felix Halim. He has set his IM status to “SUSU BLOG!!” for almost one year (man.. he’s so persistent), and I got annoyed everytime I online and saw my IM list. Not to mention Ilham who sometimes buzz me just to remind me about this write up >.<

click image to enlarge

I haven’t writen this write up before because I’m not quite “familiar” with the problem. By “familiar” I mean not all problem have been verified and solved by me (I fallen ill and have not fully recovered when ICPC).

You can found The ICPC 2009 Jakarta Site link here, and I hope it will not be deleted. The top three teams are:
1. UESTC_floyd from University of Electronic Science and Technology of China.
2. dota from National Taiwan University.
3. Dongskar Pedongi from Institut Teknologi Bandung.

The best team from BINUS (Aeon) got 9^th rank, too bad.. hopefully we can perform better this year.

There are some problems that I don’t fully understand the solution yet. I will add any necessaray review later.

You can download the complete problemset here:
ACM-ICPC 2009 Jakarta - Problem Set (537 KB)

• Problem A - Mystic Craft
• Problem B - Top-10
• Problem C - Random Simple Polygon
• Problem D - Alien
• Problem E - A + B
• Problem F - 1:1000000000000…
• Problem G - The Puzzle Board from God
• Problem H - Hero’s Adventure
• Problem I - Spam Detection
• Problem J - Favorite Time

Thanks to all authors: Ryan Leonel Somali, Felix Halim, Ilham Winata Kurnia, Timotius Sakti, Andoko Chandra, Gunawan Lie, Surya Sujarwo and Ardian Kristanto Purnomo who have helped me prepare all the problemset, solution and testdata.

At that time, ACM-ICPC training was only intended for BNPC-CS winners. Our coach was Peter Wijaya, an ex-contestant. Actually, he never taught us anything, he chose some problems from UVA and let us solve them by ourselves. This training was the first time when I learned about algorithm, and I find it very interesting. I never knew how to code BFS before or what dynamic programming is. At that time, I coded a lot! I used Felix Halim’s tools to find easy problems on UVA. He had also created a ranklist page for Indonesian coder in UVA, which made me more enthusiastic to solve more and more problems, so I can get a better rank than others. Around October 2005, I was selected to participate in ACM-ICPC Manila site, together with Ang Ing Ing and Evan Leonardi. At that time, I had solved more than 300 problems in UVA.

Manila 2005 was my first experience in ACM-ICPC. My team only managed to get 14^th rank, worse than Felix’s team, 10^th rank. As I recall, the problems was not too hard, and I think I can solve all of them by now (though some problems have unclear statements).

In 2006, Yen Lina asked me to become a new coach, and I agreed. I never had a proper training before, so I just follow Peter Wijaya’s style of coaching: select some problems and solve them. But this time, I also tried to solve the problems I’ve selected and helped those who can’t solve them. I used to say: “Any problem that I can solve, you have to be able to solve it. Any problem that I can’t solve, you might better try to solve it” :)). Though I were a coach, I think I learn a lot at that time. I began to read Introduction to Algorithm and many other books, and I also joined TopCoder. I learned about network flow algorithm, number theories, and many graph theories. I used to spend my weekend to code or compete in online contests.

After I had solved a lot of problems, I began to refine my coding skills. I used to code just to get an accepted answer, but later I began to analyze my code, proof, and rewrite an eficient code. My experience in TopCoder has also helped me improve my speed and accuracy a lot (”one hit AC”).

Well, that’s a bit about my problem solving background.

Let A be a 1 x 2 matrix which consist of f₀ and f₁ (ie. 0 and 1) and B be a 2 x 2 matrix which consist of {(0,1),(1,1)}. If we multiply A and B, we will get a 1 x 2 matrix C which consist of f₁ and f₀+f₁ (= f₂). If we multiply C with B, then we will get a matrix D which consist of f₂ and f₁+f₂ (= f₃). By doing this, we can obtain f_n by multiplying A with B for n-1 times.

Matrix multiplication is associative, so we can compute f_n by multiplying A with B to the power of n-1. We know that aⁿ can be computed in O(lg n) and multiplying two matrixes needs O(s³) where s is the size of the matrix, hence the total time complexity would be O(s³ . lg n).

Here is an example code of computing the last digit of n^th fibonacci number.

typedef vector<vector<int> > vvi;
const int mod = 10;
 
vvi mul(const vvi &a, const vvi &b) {
  vvi ret(a.size(),b[0].size());
  REP(i,a.size()) REP(j,b[i].size())
    REP(k,a[i].size()) ret[i][j] = (ret[i][j] + a[i][k] * b[k][j]) % mod;
  return ret;
}
 
vvi power(const vvi &a, int p) {
  if ( p == 1 ) return a;
  vvi x = power(a,p/2);
  if ( p % 2 == 1 ) return mul(a,mul(x,x));
  return mul(x,x);
}
 
int main()
{
  vvi a(1,2), b(2,2);
  a[0][1] = 0, a[0][1] = 1;
  b[0][0] = 0, b[0][1] = b[1][0] = b[1][1] = 1;
 
  int n;
  scanf( "%d", &n );
  printf( "%d\n", n == 0 ? 0 : mul(a,power(b,n))[0][0] );
 
  return 0;
}

Now let’s consider another problem. Given a graph G of k node, how many distinct path of length n are there that starts from node 1? This problem could also be solved by matrix multiplication.

Let A be a 1 x k matrix which consist of the number of path that end in each node, for the initial case of course it will be (1, 0, …, 0). Let B the adjacency matrix of graph G. If we multiply A with B, we will get a matrix C which consist of the number of path of length-1 that end in each node. If we multiply C with B again, we will get a matrix D which consist of the number of path of length-2 that end in each node, and so on.

There are 3 + 1 + 1 + 2 = 7 paths of length 2 in the graph above:
A - B - A
A - C - A
A - D - A
A - D - B
A - D - C
A - B - D
A - C - D

Exercises:
TJU 2169 - Number Sequence
TJU 2871 - Magic Bean
UVA 11149 - The Power of Matrix
SPOJ SEQ - Recursive Sequence
Live Archieve 4332 - Blocks for kids

Testdata bisa didownload di sini:
INC 2009 - Testcase (ZIP - 992KB)

Pembahasan solusi bisa dilihat di sini:

• Problem A - General Election
• Problem B - Liar Game
• Problem C - Why is Math Book So Sad?
• Problem D - Noodle Team Contest
• Problem E - Palapa Number
• Problem F - New House

Testdata bisa didownload di sini:
BNPCHS 2009 Final Round - Testcase (ZIP - 3091KB)

Pembahasan solusi bisa dilihat di sini:

• Problem A - Teks Fibonacci
• Problem B - BeSaR DaN KeCiL
• Problem C - Rentang Terbesar
• Problem D - Merakit Komputer
• Problem E - Mario Bros
• Problem F - Kaca Patri
• Problem G - Jumlah Pembagi
• Problem H - Drum Minyak Pak Ricat
• Problem I - Jumlah Pangkat
• Problem J - Ordo Keprimaan
• Medalist

Well anyway, Babak Penyisihan BNPCHS 2009 baru saja berlalu. Penyisihan kali ini jatuh pada hari Sabtu, 21 November 2009. Mengapa hari Sabtu? Biasanya lomba-lomba di BINUS selalu hari Minggu, tapi tanggal 22 November 2009 ada Ujian Saringan Masuk BINUS, makanya lombanya digeser ke hari Sabtu.

Babak Penyisihan terdiri dari dua tahap: Multiple Choice dan Programming. Babak Multiple Choice terdiri dari 50 soal dengan masing-masing soal bernilai 3 point, sedangkan babak Programming terdiri dari 3 soal dengan masing-masing soal bernilai minimal 70 point.

Mengenai babak multiple choice, soalnya ntar diupload belakangan, belum dirapiin.

• Problem A - Bujur Sangkar Ajaib
• Problem B - Menghitung Palindrom
• Problem C - String Prima

Daftar finalis dapat dilihat di sini.

1. Student ID (NIM) 2. Full name 3. Email address 4. Major (jurusan) 5. Regular course schedule (jadwal kuliah) 6. Last GPA 7. Grade for these subjects (if there’s any):     [ - ] Algoritma dan Pemrograman     [ - ] Struktur Data     [ - ] Perancangan dan Analisis Algoritma

click the image if you can’t read it

As usual, there won’t be any entrance test but you should already know how to code because we’re not going to teach you how to write a loop or to create an array in C/C++. BTW, I am in charge with the registration but not with the training. You will be trained by Ricky Winata, 3rd place winner from local team of ACM-ICPC Jakarta 2008. He is smart.

Registration will end at 4 April 2009 and the training will start at 20 April 2009. I’m a little bit curious… 20 April is the first week of Midterm Exam, are they sure about this? In case the training is postponed, then the end of registration date will be too early.

I know that there isn’t much information you can get from that nice poster. Knew it from last year and it happened again this time.

Schedule
The training will be conducted once a week with two shifts per week, 2 x 100 minutes. The schedule will be arranged based on the participants’ schedule (that’s why you should submit yours). Consider it like another (but interesting, challenging and fun) course or club activity. Some students asked me about this last year and they thought the training would be similar to software laboratory assistant’s training where you would be trained 12 hours a day in three or four weeks. No, it was far from their imagination :-).

Training Method
The purpose of this training session is to introduce problem solving for programming contest. CompSci’s students may find it similar to “kuis-online”, of course with different kind of problemset (in fact, kuis-online was built based on programming contest style). We give you some problems, you work on those problems, and then we discuss them. We will refresh topics if you need them (for example, when you forget what is sorting or binary search). Here we will not let you know the solution for each problem before you work on it. You should think which approach you can use to solve the problem (can you solve it directly, or would sorting the data helps you, or is there any smarter way to solve the problem, etc). And then we will discuss the effectivity and efficiency of your approach. It’s quite different from what you can find in your normal algorithm/programming class in BINUS where you usually learn a subject by memorization so you can get a good score in exam, and never learn why you should learn it.

It’s fun and challenging :-).

EDIT: rephrased by flanflygirl.

1. Write ABS function which takes an integer N as input and return the absolute value of N. Your function should be one-liner (one statement) and may contain only +, -, *, /, (, ), numbers, and variable (ie. N). You’re not allowed to call any other functions (including built-in functions).

2. Write MAX function which takes two integers A and B as input and return the largest value between A and B. Your function should also be one-liner and may contain only +, -, *, /, (, ), numbers, and variables (ie. A and B). You’re allowed only to call one function: ABS.

It took me a while to figure out how to write such ABS function. I googled several sites and found only ABS function that exploit negative numbers’ representation in computer, which means it needs bitwise operator such as << and >> (breaking the rule!), and there’s also compiler problem (16-bit or 32-bit).

Here is my solution for ABS:

int abs(int n) { return n * ((2 * ((n*n+n)/(n*n+1))) - 1); }

The key idea is to multiply n by 1 if n > 0, and multiply n by -1 if n ≤ 0. Then the problem is, how to map any n > 0 into 1 while any n by -1 if n ≤ 0 will be mapped into -1 by the same operation?

n² + n :: always give a non-negative result for any integer n.
n² + 1 :: always give a positive result for any integer n (it’s important to have a non-zero function as denominator).
(n² + n) / (n² + 1) :: always give 1 if n > 0, because (p² + p) ≥ (p² + 1) and (p² + p) < 2 * (p² + 1) for any positive integer p (n = p).
(n² + n) / (n² + 1) :: always give 0 if n ≤ 0, because (p² - p) < (p² + 1) and 0 ≤ (p² - p) for any non-negative integer p (n = -p).

From (n² + n) / (n² + 1), we will receive either 1 (if n > 0) or 0 if (if n ≤ 0). Mapping {1, 0} into {1, -1} is an easy task :-D.

For the second question (MAX), there is a simple solution which use ABS function:

int max(int a, int b) { return (a + b + abs(a - b)) / 2; }

I’d like to know if there is any easier way to do ABS or MAX, but I can’t think straight right now… okay, good night!!

EDIT: grammar (flanflygirl)

Warm-up problems:
PKU 2236 - Wireless Network
PKU 2761 - Feed the dogs
PKU 3419 - Difference Is Beautiful
PKU 3421 - X-factor Chains

Spoiler Ahead!

PKU 2236 - Wireless Network
This is an easy problem (compared to the others). Each time a computer is being repaired, merge this computer with any other computers within range that has been repaired. Repairing a computer twice won’t effect anything, so it will be usefull to remember which computer that has been repaired.

PKU 2761 - Feed the dogs
You can find the k-th element in a range with a proper tree data structure, but marcadian said that he got TLE with this approach. There is a simpler solution using a certain tree stucture to find k-th element in the whole range (timo used to call it “misof-tree”). Notice that there will be no interval that contain another interval completely, we can use this special constraint. Solve the queries based on start-interval in ascending order. By doing so, we can “maintain” our tree structure by window-sliding.

PKU 3419 - Difference Is Beautiful
Yes indeed, difference is beautiful, I like this problem :-). First, precompute A[1..N] where A_i contains the longest extension you can make from data_i, you can do it in O(N). Next, observe the extension’s end that can be made by each data_i. Let the extension of data_i ends at end_i and data_j ends at end_j. If i < j then end_i <= end_j. Now consider an interval (L, R), the extension’s end of each starting point in those intervals will be separated into two types: those which end within the interval, and those which end outside the interval. So? binary search is our friend.

PKU 3421 - X-factor Chains
The time limit for this problem is tight!! A simple O(n.ln(n)) dp solution (precompute the table) will give you TLE. One approach (which I used) to optimize this dp solution is by pruning the search space using prime numbers. You should realize that the length of the longest chain that can be made is equal to the number of it’s prime factors. Another approach (a non dp solution) is by factoring the number and calculate how many different alignment can be made by those prime numbers. Marcadian used this second approach, and his code run faster than mine.