ZJU3280 - Choose The Best

Link: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3280

December ZOJ Monthly problem, the problem is about finding maximum manhattan distance among all pairs of points in m-dimensional space (m<=8).

Cannot solve it in contest, and Hackson solve this afterwards.

The idea is observing that in Manhattan distance, the absolute value |x1-x2| can be rewrite as (x1-x2) or (x2-x1). We can do exhaustion on the sign of each dimension, sum up the value of each dimension, and find the maximum and minimum. The maximum difference between them for all cases would be the answer.

An interesting and useful technique to due with problems with absolute values or manhattan distance.

Topcoder SRM 452, 453.5, 454

SRM 452

入房驚見Petr, tourist, crazyb0y, LayCurse, yiuyuho, 心情有些驚嚇

普通速度完成了250, 得了240.x分, 之後看500, 是有些像dp, 又有些combinatorics的題目, 不懂, 就這樣等完場

challenge的時候, 看到petr出手cha掉幾個, 心中有些淆

大家大部份都只交了250, 500又不懂做, 不知道怎樣cha

唯有手打別人的code到自己機上測試, 試了一個測不出錯誤

打另一個的code, 發現有錯, 看看代碼, 好像沒有打錯, 大膽地challenge, 然後是unsuccessful....

由於只做了250, 由240.x -> 215.x... ranking大跌, 就是這樣由原本應該升rating變為跌rating了

細看發現自己打錯了一個constant, 結果改回後又那人的program果然真的好像沒有錯

之後發現petr把我之前手打測試過別人的code cha掉了 囧

最後我cha不到的code竟然過不到system test.....

這個SRM就在petr的氣勢下頹廢地結束了

============================

SRM453.5

這次入房更驚嚇, 有ACRush, Petr, marek.cygan, ahyangyi, rng_58, hhanger.....

強如ACRush也說了句"wow room 1"

250是典型BFS, 心想這次是發揮我coding能力的好機會, 可惜還是有頹bug, 拿了223.x分

450是有關plannar graph的題目, 首先想知道# of vertex為n的plannar graph, 最多有多少edge

立即想起euler's formula的e <= 3v-6, 但我不肯定是否一個tight的bound

上網找了一找, 找不到, 再想想又沒有其他想法, Petr, ACRush等又開始出題, 於是便開始code了

由於試過dp的complexity大約為3000x50000, 心想可能有些勉強, 於是便code了一個BFS

最後這題只拿了311.x分

1000開了題目看, 是lucky number的東西, 立即想起seerc08的一題, 又是由4和7組成的數字

有想過用inclusion-exclusion, 但lucky number又有>1000個, 2^1000恐怕差太遠了吧

再想了想lcm可能會glow得很快, 太大的可以剪枝剪掉, 又想起由大的開始試可以剪多一些

不過再想無論怎樣剪, 2^1000還是太勉強, 信心不足, 沒有開始寫

challenge的時候看見其他人500都是頹dp, 1000都是inclusion-exclusion......

看別人的250, 發現有人開細了array size, 立即gen了一個50x50的case把他cha掉

補償了500做得很慢的失誤, 挽救了我的rating

很感動地竟然可以在Petr, ACRush等人同房的時候還夠快cha到別人 =]

最後給billy看room summary的時候他還以為是division summary......

============================

SRM454

入房, 終於沒有Petr, 沒有其他target, 是比較和諧的一間房

250一如以往也比較簡單, 拿了240.x分

這是hackson msn傳來一句說winger resubmit了兩次, 叫我小心

於是花了些時間看看, 都覺得沒有甚麼問題

500是有關7-segment digit, 又或者是搬火柴砌數字的題目, noi曾經出過這類題目

不久想到了dp的做法, 一開始想hardcode每數字到每數字所需要移動的火柴數目和要增加的火柴數目

hardcode了1/10覺得實在太煩, 想到了簡單的hardcode方法, 把數字的形狀hardcode再去計算所需的資料也很簡單

寫完過不到sample, 花了一段時間發現自己想sprintf寫成了sscanf

還是過不到sample, 花了非常長的時間發現自己hardcode錯了一個number

還是過不到sample, 又花了非常長的時間發現自己hardcode錯另外一個number

過了sample, 試試速度, submit, 只剩下200.13

challenge phrase前計算過自己有本錢去cha人一次

又發現臨結束前2-3秒時有人提交500, 這題的數據又很容易出

於是一開波便看他的code, 看了10秒覺得沒有可能會正確, 決定challenge

很感動地出了一個challenge successful!!!

又補償了我500做得很慢的分數

之後再看其他500, 又好像沒有甚麼問題

發現有幾個人被cha了250, 但看剩下的又沒有甚麼問題

這樣就結束了, 最後剩下的code也全pass system test

============================

current rating: 1990

下次要上2000!!

回香港前希望可以上紅色

不過高處不勝寒, 還是要加強自己的實力

現在做到500是應該的, 要加強快做500的鬥志和信心

已經越來越難升rating了.....

PKU3420 - Quad Tiling

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3420

Typical DP problem when N is small.

In this problem, N can be as large as 10^9, so matrix multiplication should be used. Unlike the problem I've done before, this time the matrix is as large as 16x16 (because there is 2^4 number of states at each layer). I write code to pre-generate the 16x16 matrix instead of hard-coding the formula, and then do matrix multiplication as usual.

PKU3135 - Polygons on the Grid

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3135

An exhaustion problem.
The solution is well known, but this is a good problem for me to practice my exhaustion skills.

We can pre-compute the all possible placement on the grids for specific length sticks. In the worst case, there is 36 possible placement on the grids, which is small and we can do exhaustion on different placements.

Here is some skills for cut-case:
1. Fix the longest stick to be the first one, and try permutations for other sticks.
2. Check whether the sticks left are not long enough to reach back to the origin. Otherwise, cut this case.
3. After putting n-1 sticks, the length to the origin must be equal to the length of the last stick. Otherwise, cut this case.
4. We can fix the direction to put the first stick to be in the first region (x,y are positive)
5. Because for the first stick, it is symmetric for (y,x) and (x,y) cases arrangement, we can only try one of them.

Another thing is that do not use STL pair when doing these problems.

PKU3471 - Integral Roots

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3471

The problem is given an integral coefficient polynomial, find all integral roots of it.

If there is repeated root, output them repeatedly.

For the integral roots of the polynomial, it must be a factor of the constant term of the polynomial. We then can factorized the constant term and verify the factors to the polynomial one by one.

However, overflow will occur during the verification (the degree of the polynomial may be as large as 100), how should we verify the solution safely?

One method is that you can calculate the polynomial by repeatedly dividing and subtracting each terms. For example, ax^2 + bx + c = 0, it can be rewritten as ax + b = -c/x. As the LHS of the equation is integer, the c/x must be integer. Using this method, we can avoid overflow in our calculation.

This has not solved the problem. We have not identified the repeated roots. One way to find the multiplicity of roots is to check f(x), f'(x), f''(x), and so on, and they should all be zero. But calculating the derivatives of f may again lead to overflow.

The method I finally used is to do polynomial division.

I repeatedly divide the polynomial by (x - c). If that is divisible, then c is a root of it, and use the quotient to continue the process. This can avoid all overflow problems, and find the repeated roots successfully.

Be careful on the cases that zero is the root of the polynomial.

start writing ACM blog

a little bit late, but hopes this can make me write more, and of course, do more problems =)