Ok, back to a technical post.

Here we go.

1. The problem set begins with a short classic question. So short that I’m willing to paste it here 🙂

“There is a snail on the ground. It wants to climb to the top of a wooden pole with the height of V
meters, measuring from the ground level. In one day it can climb A meters upwards, however during
each night it sleeps, sliding B meters back down. Determine the number of days it needs to climb to the
top.”

I ever heard this famous classic problem before. This problem got its fame because of its tricky solution. To solve this puzzle right, just remember that we should not consider the sliding after the last time the snail climbs the wooden pole.

My solution:

int A, B, V;

int main () {
    scanf ("%d%d%d", &A, &B, &V);
    printf ("%d\n", (V - A) / (A - B) + ((V - A) % (A - B) != 0) + 1);
    return 0;
}

2. I was surprised that the second problem was much easier than the first one 🙂 Here is my solution: change all non-digit character to space, parse them using stringstream, and sort the array as what is said in the problem statement.

Here is my code:

int N;
char s[1000];
vector <string> v;

inline bool cmp (const string &a, const string &b) {
    if (a.length () != b.length ()) return a.length () < b.length ();
    return a < b;
}

int main () {
    scanf ("%d", &N);
    
    REP (i, N) {
        scanf ("%s", s);
        for (int j = 0; s[j]; j++)
            if (!isdigit (s[j]))
                s[j] = ' ';
        stringstream ss (s);
        string x;
        while (ss >> x) {
            v.PB (x);
        }
    }
    
    REP (i, SIZE (v)) {
        while (v[i] != "" && v[i][0] == '0')
            v[i].erase (v[i].begin());
        if (v[i] == "") v[i] = "0";
    }
    
    sort (ALL (v), cmp);
    
    REP (i, SIZE (v)) cout << v[i] << endl;
    
    return 0;
}

3. This problem is not hard. It’s a simple greedy problem. After spending some time to prove my greedy solution was right, I code it quite fast. The main idea of the greedy is: in each turn, always take the “smallest” alphabet possible. In case of tie, take the rightmost one. Try to convince yourself that this greedy is right, than the rest is only the matter of coding 🙂 (if you’re still confused on how to implement it efficiently: Try to sort it only once, and memorized every numbers you have deleted so next time when you meet this number, you can skip it as soon as possible)

int N;
char s[100005];
bool del[100005];
vector <PII> daftar;
string a, b;

int main () {
    scanf ("%d", &N);
    scanf ("%s", s);
    
    for (int i = 0; s[i]; i++)
        daftar.PB (MP (s[i], -i));
    
    sort (ALL (daftar), greater <PII> ());
    
    int last = N - 1;
    
    REP (i, N / 2) {
        while (del[last]) last--;
        a += s[last];
        last--;
        while (-daftar.back().S > last) daftar.pop_back ();
        b += daftar.back().F;
        del[-daftar.back().S] = true;
        daftar.pop_back ();
    }
    
    if (a > b) {
        puts ("DA");
    } else puts ("NE");
    
    puts (b.c_str());
    
    return 0;
}

4. The idea is simple. Iterate from the second largest index book to the smallest one. For each book, if it is below the larger one (see that I compare i-th book with (i + 1)-th book only because all book with indices > i have been sorted), move it to the top. Moving a book to the top efficiently probably need some special technique. See below, array A[i] = x means book with indices i is located in the x-th position. When I move it to the top, I change A[i] to the a negative number. Just think a bit about it. It’s a nice technique, isn’t it? 🙂

#define MAXN 300000

int N, A[MAXN + 2];

int main () {
    scanf ("%d", &N);
    
    REP (i, N) {
        int x;
        scanf ("%d", &x);
        A[--x] = i;
    }
    
    int next = -1, ret = 0;
    
    REPD (i, N - 1) {
        if (A[i] > A[i + 1]) {
            A[i] = next--;
            ret++;
        }
    }
    
    printf ("%d\n", ret);
    
    return 0;
}

5. The idea of this problem is not difficult. The challenge came when we try to implement it bug-freely. If any of the number of rows or number of columns is an odd number, the solution should be obvious. However, when both of them are even, it becomes slightly harder. You need to *skip* at least one cell. And it can be proven that in the optimal solution, we always skip exactly one cell. Suppose the cell is in i-th row and j-th column (both indices started from 0). This cell is one of the candidate solutions iff:
((i % 2 == 1 && j % 2 == 0) || (i % 2 == 0 && j % 2 == 1))
Then, try to always move in zig-zag manner, skipping the smallest number cell satisfying the property above.
Here is my solution:

const int MAXR = 1000;
const int MAXC = 1000;

int nrows, ncols;

int main () {
    scanf ("%d%d", &nrows, &ncols);
    
    int mn = -1, tot = 0, r = -1, c = -1;
    
    REP (i, nrows) REP (j, ncols) {
        int x = getInt ();
        tot += x;
        if ((i % 2 == 1 && j % 2 == 0) || (i % 2 == 0 && j % 2 == 1)) {
            if (mn == -1) mn = x;
            else if (x < mn) mn = x;
            if (mn == x) r = i, c = j;
        }
    }
    
    if (nrows % 2 == 0 && ncols % 2 == 0) {
        int cdir;
        if (r == nrows - 1) {
            cdir = nrows - 2;
        } else {
            cdir = r;
        }
        
        int dir = -1;
        REP (i, nrows - 1) {
            if (i) printf ("D");
            dir = -dir;
            if (i != cdir) {
                REP (j, ncols - 1) {
                    if (dir == 1) printf ("R");
                    else printf ("L");
                }
            } else {
                int R = i, C, stat;
                if (dir == 1) {
                    C = 0;
                    stat = 1;
                    int batas = ncols;
                    REP (j, batas) {
                        if (stat == 1) {
                            if (R + 1 == r && C == c) {
                                if (C + 1 > ncols - 1) break;
                                printf ("R");
                                C++;
                            }
                            printf ("D");
                            R++;
                            if (C + 1 > ncols - 1) break;
                            printf ("R");
                            C++;
                        } else {
                            if (R - 1 == r && C == c) {
                                if (C + 1 > ncols - 1) break;
                                printf ("R");
                                C++;
                            }
                            printf ("U");
                            R--;
                            if (C + 1 > ncols - 1) break;
                            printf ("R");
                            C++;
                        }
                        stat = !stat;
                    }
                } else {
                    C = ncols - 1;
                    stat = 1;
                    int batas = ncols;
                    REP (j, batas) {
                        if (stat == 1) {
                            if (R + 1 == r && C == c) {
                                if (C - 1 < 0) break;
                                printf ("L");
                                C--;
                            }
                            printf ("D");
                            R++;
                            if (C - 1 < 0) break;
                            printf ("L");
                            C--;
                        } else {
                            if (R - 1 == r && C == c) {
                                if (C - 1 < 0) break;
                                printf ("L");
                                C--;
                            }
                            printf ("U");
                            R--;
                            if (C - 1 < 0) break;
                            printf ("L");
                            C--;
                        }
                        stat = !stat;
                    }
                }
            }
        }
    } else {
        if (nrows % 2 == 1) {
            int dir = -1;
            REP (i, nrows) {
                if (i) printf ("D");
                dir = -dir;
                REP (j, ncols - 1) {
                    if (dir == 1) printf ("R");
                    else printf ("L");
                }
            }
        } else {
            int dir = -1;
            REP (i, ncols) {
                if (i) printf ("R");
                dir = -dir;
                REP (j, nrows - 1) {
                    if (dir == 1) printf ("D");
                    else printf ("U");
                }
            }
        }
    }
    
    puts ("");
    
    return 0;
}

6. Should be the hardest problem in this contest. I didn’t code it at all (even the brute force one) because I need some rest before the SRM. I haven’t tried to submit this problem, but I have some approach that seems to be correct.

It can be shown that given two rectangles in the grid, we can separate them by using either one vertical line or horizontal line. So, we can divide the area into two and precompute the solution of each side. Dealing with one rectangle is not so difficult, try to think about it 🙂
The most challenging part comes when we realized that in some cases, two rectangles can be separated by BOTH vertical and horizontal line. You need to count this case so you can subtract it from our result, to get the correct one. Iterate through each cells in the grid, count how many rectangles have the bottom-right corner at (r, c) and top-left corner at (i, j) such that i >= r + 1 and j >= c + 1. Don’t forget to precompute those values.

With this approach, O(n^2) solution for this problem is possible. Seems pretty tiring to code ^^

That’s all. The final result can be seen here: http://hsin.hr/coci/results.php?contest=2

Any comment, question, or anything you want to discuss? Drop me a comment below :).

Advertisements