URAL 1252 - Sorting the Tombstones

連結 http://acm.timus.ru/problem.aspx?space=1&num=1252

題目大意︰一個最多130000個elements的array，利用類似shell sort的方法去sort，即是只可以對每隔K個位的element進行swapping。問K最大是多少。

很直觀，只需要比對sort好和未sort的array的index之差，再找它們的共同gcd便可。因為對於每個element，一定要去到和它相差X個位的位置，而每一個element也要附合這個條件，為要達到這個目的，必須找一個共同數K都被每一個X整除，而K便是答案。

唯一一個trick便是題目要求。這題目沒有說明sort要是ascending還是descending，被fake了一次......

URAL 1519 - Formula 1

連結 http://acm.timus.ru/problem.aspx?space=1&num=1519

這條儘管是模板題，但我也卡了很久。

每一個狀態的表示為三進制的列，例如一個m為5的grid的表示方法為(012012)₃，當中0是無插頭，1是左插頭，2是右插頭，詳見cdq的論文。

因m最大是12，即是一個state的memory可以是3¹³這樣大，即是1594323。如果每一次都要clear memory，或者開個12x12x1594323的array，這都是不可能的，因此我用了hash的方法。而因為state的用量不高，因此可以用open addressing。我個人用的hash size是32767。

轉換方法分為三類(假設現在在第1格)︰

0123456             0123456
  _____   -->          ____
_|                  __|

1. 開新插頭，例︰
0000000 -> 0120000

2. 延伸插頭，例︰
0100200 -> 0100200 或 0010200

3. 合併插頭，例︰
Case (a): 0110220 -> 0000120 (1和2是對等的)
Case (b): 1210020 -> 1000020
Case (c): 0120000 -> 0000000 (只會在最後的空格發生)

我用了好一點時間code好了以上的case，卻得到WA的回覆了。放棄了好一陣子，直至今天才去認真debug，結果錯在case 3a︰

由0111222(第一格)，我的錯誤program將它轉成0001122，正確應是0001212。完全miss了論文中12對應的特性。最後終於AC了。